EECS News for 2001

EECS 598-02 Randomized Computation

Winter 2002

Instructor: Satyanarayana V. Lokam (satyalv@eecs.umich.edu)

Time and Place: Tue and Thu 11:30 AM -- 1:30 PM, 3433 EECS.

Credit Hours: 4 CSE students can take this course for 500+ level credit.

Prerequisites: A basic course in algorithms or computational complexity and familiarity with elementary algebra and probability theory.

Description: For several important problems, use of randomness yields the most efficient algorithms known, or the simplest, or both. In fact, randomness is essential for certain tasks in cryptography and distributed computation. As a result, research in randomized algorithms has seen a phenomenal growth in recent years. In the first half of this course, we will study a collection of techniques for effectively using randomization and for analyzing randomized algorithms. We will pick examples from a variety of settings and problem areas.

Given that randomization helps, where do computers get their randomness from? In practice, we often use Pseudo-Random Generators (PRG's). But, when is the output of a PRG ``random enough" to replace a source of pure random bits? How do we construct such good PRG's? Even assuming computers do have access to ``pure randomness," how dramatic a speedup can we achieve using randomness? In the second half of the course, we will study recent results that address such issues. Important results in this area have rigorously established the intimate relations among the notions of randomness, computation,and information.

Attempts to understand some basic scientific questions, use of simple, but elegant, mathematics, and building rigorous foundations for important practical applications are some of the interesting highlights of this course.

Main Topics:

• Background from Probability Theory
• Randomized Algorithms
• Derandomization
• Pseudo-Random Generators
Grading: Homework and term papers/final projects.

Homework: 50%
Term Paper/Final Project: 50%

For more up-to-date information, please visit: http://www.eecs.umich.edu/~satyalv/rand/

EECS 598-07 Nonlinear Fiber Optical Devices

EECS 598 SECTION 7

Description: Study of nonlinear optical devices that operate with multiple nonlinear processes to perform operations including switching, amplification, pulse generation, optical limiting, optical clock recovery and frequency switching. There will be a focus on the nonlinear processes in high energy and high power, ultrafast fiber lasers. There will be a look at the properties of photonic crystals including their nonlinear optical properties. The course requirement will be the design of your own device or the analysis of an existing device.

Prerequisites: EECS 538 or EECS 634 or permission of instructor

Credits: 1 credit

Instructor: EECS Adjunct Dr. Donald J. Harter  dharter@eecs.umich.edu

Golden Apple Award to Elliot Soloway

Congratulations to Professor Elliot Soloway who is this year's recipient of the Golden Apple Award sponsored by Students Honoring Outstanding University Teaching (SHOUT).

The Golden Apple Award honors those teachers who consistently teach each lecture as if it were their last, and strive not only to disseminate knowledge but to inspire and engage students in its pursuit.

Approximately 520 students nominated various professors for the Golden Apple Award this year. Students of Professor Soloway who sent in nominations agreed with his philosophy on teaching and said they were inspired by him.

The concept of the Golden Apple Award was inspired by one of the greatest teachers of the Jewish tradition, Rabbi Eliezer ben Hurkanos, who taught 1900 years ago, "Get your life in order one day before you die." The Award is an annual reminder to the entire University that all of us should always be giving our "last lectures."

In honor of winning the Golden Apple Award, Professor Soloway will give his "ideal last lecture" January 22 at the Lydia Mendelssohn Theater and be awarded \$1,000 cash.

EECS 598-5: Mathematical Modeling and Simulation Techniques for Networking

Instructor: Mingyan Liu

Communication networks have become increasingly complex systems. With the rapid expansion of the Internet, it is important that we are equipped with proper tools to analyze and gain insight on the performance, dynamics, technical and social implications of various mechanisms used in the Internet. In this course we will study two classes of such tools: mathematical modeling and simulation. Both of them are widely used in networking. On the one hand mathematical modeling, via abstraction, can be tractable, fast and intuitive, as well as facilitate optimization and sensitivity analysis. On the other hand simulation can be much more detailed and can handle large-scale systems.

In this course we will review mathematical modeling techniques based on a range of principles and examine their effectiveness, particularly, the relationship between the simplicity of a model and its usefulness. The study will be highly application-oriented, in that there is always a very clear realistic subject to be modeled, be it a protocol, a channel or a policy. Under the second theme of the course we will review the techniques of computer simulation, which is widely used to study complex systems, and also often used to validate mathematical models. We will NOT show how to use a particular simulation tool (e.g.,NS-2, OPNET), but will show the basic statistical and discrete event concepts underlying most simulation tools. We will also discuss how to use simulation in a scientific way.

This course will consist of both lectures (i.e., presentation by the instructor) and discussions (i.e., discussion on assigned papers in class). The subjects covered in this course are as follows (the sequence is subject to change):
- Modeling of multiple access channels (e.g., channel errors, IEEE802.11)
- Optimal routing and blocking probabilities
- Performance modeling of TCP
- Congestion control, rate control and utility maximizing
- Simulation and the Monte Carlomethod
- Internet traffic and self-similarity

For each of these subjects there will be a list of selected papers as reading assignment. The final grade will be based on
- the summary review on paper reading assignment;
- participation in class discussions;
- a term project/paper and presentation

Distinguished Dissertation Awards

I am happy to announce that the University of Michigan Lucent Technologies distinguished dissertaion awards in the area of Mathematical SystemScience have been awarded to the following students:

Christopher Lott, "Optimal Resource Allocation and Routing in Wireless Networks," Advisor D. Teneketzis, Winter 2001.

Navin Kashyap, "Data Synchronization with Timing," Advisor, D. Neuhoff, Fall 2001.

Each student will recieve a certificate and a check for \$500.00.

Congraulations to Christopher and Navin, and to their advisors!

Rich

EECS 684: Query Processing Techniques in Mobile and Distributed Database Systems

Database systems have come along a long way since their inception in the 1970s. Database Management Systems (DBMSs) have been widely successful and are the heart of most information management system. However, there are a number of significant challenges that future DBMSs must meet if they are to continue playing the center role in information processing and management. We are on the verge of a new revolution in ubiquitous computing in which zillions of devices, ranging from small personal digital assistants (PDAs) to “invisible” embedded devices, will demand answers to queries under a wide range of system conditions. These devices will rely on a distributed backend infrastructure to deliver the query results. The data sets in the back-end systems are growing at astonishing rates, demanding scalable distributed data management techniques. Furthermore, the data sets are increasingly complex, and are not limited to the alphanumeric data types, that relational DBMS have proven so effective at managing. Database query processing and database storage techniques that exist today fall far short of meeting the demands of these future systems. What then are the techniques that will deliver this new world to us? This is the question that we will explore in this course. The course will focus primarily on query processing and query evaluation techniques that are likely to be applicable in mobile and distributed database environments of the future.

Since most of the questions in this area are unanswered, this course will be very exploratory. Paper readings and a course project will constitute the main components of this course. For more information, see http://www.eecs.umich.edu/courses/eecs684/

John J. Carey, Emeritus Professor

John Joseph Carey, Emeritus Professor of the Department of Electrical Engineering and Computer Science, has passed away November 10, 2001, at the age of 89. Professor Carey was born in Boston, and received his B.S. and M.S. degrees in Electrical Engineering from MIT in 1934 and 1953. From 1934-41, he worked on the Panama Canal, serving with the Panama Canal Department as Associate Electrical-Mechanical Engineer. He then joined an engineering firm in Boston. He was a Captain in the U.S. Army from 1942-45, serving in the Corps of Engineers 1943-45, and he was awarded the Campaign Star in 1944. During 1945-46, Prof. Carey taught at the Universities of New Mexico and Kansas. In 1946 he was appointed Assistant Professor of Electrical Engineering at the University of Michigan; he was promoted to Associate Professor in 1948 and to Professor in 1957. Prof. Carey retired in 1972. While at the University of Michigan, Prof. Carey was co-director of the Power Systems Laboratory, and taught courses in power systems analysis, electro-mechanical energy conversion, engineering economics, and circuits. He also taught courses in power systems for employees of the Consumers Power Company, the Commonwealth Associates, and the Detroit Edison Company. Throughout his career at Michigan, Professor Carey demonstrated unique capabilities as a teacher, researcher, and consultant in electric power systems and energy conversion. Prof. Carey also gave generously of his time and talents to administrative and University-wide committees. He was very active in the Michigan Society for Professional Engineers, for which he was a past president, and the American Institute of Electrical Engineers; he was also a member of Sigma Xi, Eta Kappa Nu, and IEEE. Prof. Carey spent 10 weeks in India, where he had been stationed in the Army, in 1965 working on curriculum issues under the sponsorship of the Government of India and U.S. Aid. Upon his retirement, Prof. Carey was a frequent consultant in product liability and personal injury lawsuits. Prof. Carey is survived by his wife, Grace; their children, John Jr., Sharon, and Karen; six grandchildren; seven great-grandchildren; one sister Louise; and 16 nieces and nephews. The Department of Electrical Engineering and Computer Science offers its condolences to the family, friends, and colleagues of John Joseph Carey, and expresses its gratitude for his 26 years of distinguished service to the University of Michigan.

EECS 578: Computer-Aided Design Verification of Digital Systems

Instructor: Professor Karem Sakallah, 2213 EECS, karem@umich.edu, 936-1350.

Time and Place: TT 10:30-12:00, 3437 EECS

Credit Hours: 3

Prerequisites: EECS 478 and graduate standing

Overview: In this course we explore how large complex digital systems are verified to ascertain their functional and temporal correctness. Students who enroll can expect to gain proficiency in state-of-the-art informal as well as formal approaches to verification of large-scale systems. Many of these techniques, and the insights that inspired them, can also be adapted to the verification of other large-scale systems, e.g. complex software. Hands-on experience with a variety of verification tools (equivalence checkers, model checkers, SAT solvers, symbolic simulators, etc.) is an integral part of the course.

Catalog Description: Design specification vs. implementation. Design errors. Functional and temporal modeling of digital systems. Simulation vs. symbolic verification techniques. Functional verification of combinational and sequential circuits. Topological and functional path delays; path sensitization. Timing verification of combinational and sequential circuits. Clock schedule optimization.

Course Topics:

Design verification overview; design errors; specification vs. implementation; interfaces.

Functional and temporal modeling of digital systems at various abstraction levels.

Simulation at the gate, register transfer and behavioral levels; Verilog HDL

Symbolic manipulation of Boolean functions; ordered binary decision diagrams.

Circuit satisfiability; conjunctive normal form. Davis-Putnam algorithm and extensions.

Functional verification of combinational circuits; simulation-based; symbolic; formal.

Functional verification of sequential circuits; simulation-based; symbolic; formal.

Timing verification of combinational circuits; topological and functional path delays.

Timing verification of sequential circuits; clock schedule optimization.

Course Assignments and Grading:

Written homework assignments (3 to 4): 30%

Classroom participation: 30%

Term paper/project: 40%

Henry Russel Award Goes to Prof. Clark Nguyen

I am delighted to announce that Clark Nguyen is the 2002 Henry Russel Award winner. This University of Michigan award is given on the basis of "distinguished scholarship ... and conspicuous ability as a teacher." It is a richly deserved honor!

Rich

Distinguished Lecturer

I am very pleased to announce that Prof. Al Hero has been selected by the IEEE Signal Processing Society Education Committee as a Society Distinguished Lecturer (DLs) for 2002. The nomination represents a high recognition of his professional achievement.

As a Distinguished Lecturer, Al is one of six DLs who will give lectures to chapters world-wide on signal processing topics. Congratulations, Al!

Rich
Related Topics:  Hero, Alfred

Professor Kang Shin Awarded O'Connor Chair

Professor Kang Shin was awarded the first Kevin and Nancy O'Connor Professor of Computer Science Chair.

CITI Research Appears in New York Times

Research conducted by Dr. Peter Honeyman from CITI, and one of our graduate students, Niels Provos, is discussed in the following New York Times article. Additional information on the steganography research at UM may be found at: abc.html and faq.html

National Research Council - News Release

Please find the attached news release (pdf format) announcing the National Research Council - 2002 Postdoctoral and Senior Research Associateship Programs.

Application materials and additional information regarding the programs, laboratories, their locations, and areas of research can be found on the Website at: http://www.national-academies.org/rap

Prospective applicants are invited to contact the NRC directly for additional assistance.

National Research Council, Associateship Programs (TJ 2114/D7)2101 Constitution Avenue, NW, Washington, DC 20418
Note - Application deadlines are: January 15, April 15, and August 15, 2002.

Thank you,

Lisa Kendra
______________

Office of the Dean
College of Engineering
Email: lkendra@umich.edu

Elliot Soloway's research on hand-held computers

Professor Elliot Soloway's research on hand-held computers appears in the Detroit News.

The e-commerce of the future

Tech teams gather to compete in designing the e-commerce of the future. Professor Mike Wellman led the effort at Michigan to design the game and the school hosts the servers. See complete article

Professor Steve Reinhardt wins Joel Spira Teaching Award

Professor Steve Reinhardt is this year's recipient of the ASEE's Joel Spira Teaching Award which focuses on outstanding classroom performance, recognizes teachers of engineering and engineering technology students and serves as an incentive to make further significant contributions to teaching.

William G. Dow Distinguished Lecture

SPEAKER: Dr. Robert W. Lucky
WHEN: November 8, 2001 at 4pm
WHERE: Chrysler Chesebrough Auditorium

RECEPTION FOLLOWING THE LECTURE

Handheld Computing: New Best Tech Tool or Just a Fad?

See this news article in Education Week for discussion of the work being done by Dr. Soloway. [Full Story]

Prof. Kang Shin awarded the 2001 Distinguished Faculty Achievement Award

Professor Kang Shin was awarded the 2001 Distinguished Faculty Achievement Award from the University this year.

Keeping Up in Class With Software for a Hand-Held

Elliot Soloway has been mentioned in an article entitled "Keeping Up in Class With Software for a Hand-Held" and is in the NY Times. In addition, a second article for Dr. Soloway, Debating Merits of Palms in Class appeared in Wired News.

Professor Peter Chen awarded the 2001 Amoco Undergraduate Teaching Award

Professor Peter Chen was awarded the 2001 Amoco Undergraduate Teaching Award for his exceptional contributions to undergraduate teaching at the University of Michigan.

Handheld computers in summer science elementary classrooms

Professor Elliot Soloway's work with handheld computers in summer science elementary classrooms appeared in Detroit News, July 23, 2001 [Full Story]

Using a Computer Game to Develop Advanced AI

Appeared in Computer Magazine, July's issue: Laird, J. E. (2001b) Using a Computer Game to Develop Advanced AI, Computer, 34(7), July 2001, pp. 70-75.

Interactive Computer Games: Human-Level AI's Killer Application

Appeared in AI Magazine # 22 Laird J.E. and Van Lent, M. (2001) Interactive Computer Games: Human-Level AI's Killer Application, AI Magazine, 22(2), 15-25.

Palm pilots and Education

Elliot Soloway's work with palm pilots and education appears in Business Week

Dr. Soloway was also interviewed recently by WIRED NEWS. The following Internet radio broadcast is currently being hosted at Wired: Kids Need Hands-On Tech Elliot Soloway is a professor of education at University of Michigan. He discusses the increased presence of technology in education through the use of palm-sized computers in the K-12 classroom and improved integration of curriculum and technology.

Computer Science Gaming Courses

Computer Science Gaming Courses makes the Joystick 101.org News