College of LS&A

Fall '01 Graduate Course Guide

Note: You must establish a session for Fall Academic Term 2001 on wolverineaccess.umich.edu in order to use the link "Check Times, Location, and Availability". Once your session is established, the links will function.

Courses in Computer Science


This page was created at 9:14 AM on Thu, Oct 11, 2001.

Fall Academic Term, 2001 (September 5 December 21)

Open courses in Computer Science
(*Not real-time Information. Review the "Data current as of: " statement at the bottom of hyperlinked page)

Wolverine Access Subject listing for CMPTRSC

Fall Term '01 Time Schedule for Computer Science.

To see what graduate courses have been added to or changed in Computer Science this week go to What's New This Week.

Search the LS&A Course Guide (Advanced Search Page)

CMPTRSC 470 / EECS 470. Computer Architecture.

Section 001.

Instructor(s):

Prerequisites: CS 370. (4). CAEN lab access fee required for non-Engineering students.

Credits: (4).

Lab Fee: CAEN lab access fee required for non-Engineering students.

Course Homepage: http://www.eecs.umich.edu/courses/eecs470/

Course Synopsis: This course provides a broad introduction to computer architecture. The course covers a large amount of material in moderate depth, giving the student a good understanding of the basic issues in computer system design. Specifically, the course covers instruction set design, pipelining, the memory hierarchy, I/O systems, and current research topics. Example systems include the Intel PIII, Alpha 21264 processors.

Check Times, Location, and Availability Cost: No Data Given. Waitlist Code: 1

CMPTRSC 477 / EECS 477. Introduction to Algorithms.

Section 001.

Instructor(s): Igor Markov (imarkov@umich.edu)

Prerequisites: CS 281. (4). CAEN lab access fee required for non-Engineering students.

Credits: (4).

Lab Fee: CAEN lab access fee required for non-Engineering students.

Course Homepage: http://www.eecs.umich.edu/courses/eecs477/

Fundamental techniques for designing efficient algorithms and basic mathematical methods for analyzing their performance. Paradigms for algorithm design: divide-and-conquer, greedy methods, graph search techniques, dynamic programming. Design of efficient data structures and analysis of the running time and space requirements of algorithms in the worst and average cases. Instructor's note: This is not a programming class. We will focus on the analysis of algorithms and situations where it is useful. If you are looking to learn C++/STL, EECS 280 or EECS 281 are relevant classes. If you are looking for programming experience, EECS 281 is the right class to take (but you can also opt for a coding-heavy project in EECS 477).

Prerequisites
Students must have taken EECS 203 (Discrete Structures) and EECS 380(281) (Algorithms and Data Structures), or equivalents. Programming experience in C or C++ is required. Some assignments in this class may require the understanding of C++/STL, but not necessarily designing large programs in C++. If you only know Pascal or Java (or some other language), talk to Prof. Markov.

Grading
Final grades will be based on the total points earned on the projects and exams. Grading will be on the curve. Factors such as class participation may be used to adjust your final grade, especially if it falls on a borderline. The tentative point breakdown is as follows:

  • Homework: 10%
  • One project: 30%
  • One midterm: 30%
  • Final: 30%

    There will be a number of "extra credit" questions, especially on exams. You do not need to solve those to get an A, and other students' "extra credit" will not affect the curve. However, those can lift your grade above the curve (so, in theory, everyone can get an A). Extra credit questions will not count if the regular part of your assignment is done poorly.

    Course Material

  • Required text: Fundamentals of Algorithms by Brassard and Brately, Prentice Hall 1996
  • Recommended additional text: Introduction to Algorithms by Cormen, Leiserson, Rivest (and Stein 2nd ed.), all editions are ok.
  • If you have your book from EECS 380 it can be useful too. The book used in the Winter 2001 semester was: Algorithms in C++, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching, 3rd edition by Robert Sedgewick. Part 5 (second volume) "Graph Algorithms" came out in August it's quite good.
  • Additional handouts (typically made from the recommended books).
  • For references on C++, STL, etc (including online refs), see refs from EECS 380

    Check Times, Location, and Availability Cost: No Data Given. Waitlist Code: 1

    CMPTRSC 478 / EECS 478. Logic Circuit Synthesis and Optimization.

    Section 001.

    Instructor(s): Marios C Papaefthymiou (marios@umich.edu)

    Prerequisites: CS 270 and 203, and senior or graduate standing. (4). CAEN lab access fee required for non-Engineering students.

    Credits: (4).

    Lab Fee: CAEN lab access fee required for non-Engineering students.

    Course Homepage: http://www.eecs.umich.edu/courses/eecs478/

    Course Overview: This course covers digital logic synthesis and its underlying theory from an advanced perspective. Topics include: combinational logic optimization (two-level and multilevel minimization), sequential logic optimization (state assignment, FSM minimization, retiming), timing analysis and optimization, technology mapping, scheduling, allocation, and verification. Emphasis will be placed on algorithmic techniques that are currently used in the design of integrated systems with millions of transistors.

    Textbook: Logic synthesis and verification algorithms, G. Hachtel and F. Somenzi, Kluwer Academic Publishers.

    Supplementary textbook: Synthesis and optimization of digital circuits, G. DeMicheli, McGraw-Hill.

  • Both textbooks have been placed on reserve in the Media Union Library.

    Check Times, Location, and Availability Cost: No Data Given. Waitlist Code: 1

    CMPTRSC 481 / EECS 481. Software Engineering.

    Section 001.

    Instructor(s): John Sayler (jhsayler@umich.edu)

    Prerequisites: CS 281. (4). CAEN lab access fee required for non-Engineering students.

    Credits: (4).

    Lab Fee: CAEN lab access fee required for non-Engineering students.

    Course Homepage: http://www.eecs.umich.edu/courses/eecs481/

    Pragmatic aspects of the production of software systems, dealing with structuring principles, design methodologies and informal analysis. Emphasis is given to development of large, complex software systems. A term project is usually required.

    Check Times, Location, and Availability Cost: No Data Given. Waitlist Code: 1

    CMPTRSC 482 / EECS 482. Introduction to Operating Systems.

    Section 001.

    Instructor(s): Peter Chen (pmchen@umich.edu)

    Prerequisites: CS 370 and 281. (4). CAEN lab access fee required for non-Engineering students.

    Credits: (4).

    Lab Fee: CAEN lab access fee required for non-Engineering students.

    Course Homepage: http://www.eecs.umich.edu/~pmchen/eecs482/

    Course Overview: EECS 482 is an introductory course in operating systems at the senior undergraduate level or first-year graduate level. The objective of the course is to familiarize you with the issues involved in the design and implementation of modern operating systems. The concepts in this course are not limited to any particular operating system or hard-ware platform. We will discuss examples that are drawn from historically significant and modern operating systems. We will cover topics such as processes and threads, concurrency and synchronization, CPU scheduling, virtual memory management, communication in distributed systems, secondary-storage management, file systems, and security. In order to more fully understand operating systems, you will implement several projects that expose you to much of the core functionality in modern operating systems. These projects will give you practical exposure to topics such as threads, efficient resource usage, caching, and client-server systems. To further your understanding of other topics, we will provide practice questions that will be presented in the discussion sections. In discussion sections, we will also present material on the practice of programming, including elegance in design and coding, the process of testing and debugging, and how to effectively work in teams.

    Prerequisites: Students must have obtained a grade of C or better in each of EECS 370 and EECS 380, or have equivalent knowledge of computer architecture, data structures, and C/C++ programming. Students are expected to have had extensive C/C++ programming experience and to be familiar with UNIX. Students with questions about whether they have sufficient preparation for this course should speak with the instructors as soon as possible. Due to the overwhelming number of students interested in this course, we will strictly enforce the prerequisites.

    Check Times, Location, and Availability Cost: No Data Given. Waitlist Code: 1

    CMPTRSC 482 / EECS 482. Introduction to Operating Systems.

    Section 006.

    Instructor(s): Atul Prakash (aprakash@umich.edu)

    Prerequisites: CS 370 and 281. (4). CAEN lab access fee required for non-Engineering students.

    Credits: (4).

    Lab Fee: CAEN lab access fee required for non-Engineering students.

    Course Homepage: http://www.eecs.umich.edu/~pmchen/eecs482/

    EECS 482 is an introductory course in operating systems at the senior undergraduate level or first-year graduate level. The objective of the course is to familiarize you with the issues involved in the design and implementation of modern operating systems. The concepts in this course are not limited to any particular operating system or hardware platform. We will discuss examples that are drawn from historically significant and modern operating systems. We will cover topics such as processes and threads, concurrency and synchronization, CPU scheduling, virtual memory management, communication in distributed systems, secondary-storage management, file systems, and security.

    In order to more fully understand operating systems, you will implement several projects that expose you to the core features of modern operating systems. These projects will give you practical exposure to topics such as threads, efficient resource usage, caching, and client-server systems. To further your understanding of other topics, we will provide practice questions that will be presented in the discussion sections. In discussion sections, we will also present material on the practice of programming, including elegance in design and coding; the process of testing and debugging; and how to effectively work in teams.

    Prerequisites Students must have obtained a grade of C or better in each of EECS 370 and EECS 380/281. Graduate students must have equivalent knowledge of computer architecture, data structures, and C/C++ programming. Students are expected to have had extensive C/C++ programming experience and to be familiar with UNIX. Students with questions about whether they have sufficient preparation for this course should speak with the instructors as soon as possible. Due to the overwhelming number of students interested in this course, we will strictly enforce the prerequisites. We will also give priority to senior students who need the course to graduate in May and have declared their major. Undeclared majors will not be accepted into this course because of high enrollment.

    Check Times, Location, and Availability Cost: No Data Given. Waitlist Code: 1

    CMPTRSC 483 / EECS 483. Compiler Construction.

    Section 001.

    Instructor(s): Trevor N Mudge

    Prerequisites: CS 281 and 376. (4). CAEN lab access fee required for non-Engineering students.

    Credits: (4).

    Lab Fee: CAEN lab access fee required for non-Engineering students.

    Course Homepage: http://www.eecs.umich.edu/~tnm/483/483.htm

    Introduction to compiling techniques including parsing algorithms, semantic processing, and optimization. Students implement a compiler for a substantial programming language using a compiler generating system.

    This is a fair description of what we will be covering, but the subject of compiler construction is a large one, and time limitations mean that we will not cover everything mentioned in the description in great depth. The goal will be to introduce the basics of compiler construction with an emphasis on using tools to construct a simple compiler.

    Homework: Homework will be set on a regular basis. It will not be graded. The solutions will be discussed in class. The homework material will be typical of the questions that will be on the exams.

    Exams: There will be two written exams, but no final.

    Projects: The main grade will come from five projects that will require you to write parts of a compiler.

    Books: There are two books that you should purchase. The first one is a classic, which is often referred to as the dragon or dinosaur book (I think it's a dragon on the cover).

    • Title: Compilers: Principles, Techniques, and Tools Authors: Aho, Sethi, and Ullman. Publisher: Addison-Wesley Pub Co ISBN: 0201100886
    • The second book is: Title: Lex & Yacc Authors: John R. Levine, Tony Mason, Doug Brown. Publisher: O'Reilly & Associates ISBN: 1565920007

    Check Times, Location, and Availability Cost: No Data Given. Waitlist Code: 1

    CMPTRSC 484 / EECS 484 / IOE 484. Database Management Systems.

    Section 001 Relational Database Management Systems (DBMSs)

    Instructor(s): Jignesh Patel (jignesh@umich.edu)

    Prerequisites: CS 281. (4). CAEN lab access fee required for non-Engineering students.

    Credits: (4).

    Lab Fee: CAEN lab access fee required for non-Engineering students.

    Course Homepage: http://www.eecs.umich.edu/courses/eecs484/

    EECS 484 provides basic introduction to relational database management systems (DBMSs). This course is designed to provide you with both an external and an internal view of relational DBMSs. Topics related to the external view will cover concepts that will allow you to use a relational DBMS. Topics related to the internal view will allow you to better understand how a relational DBMS works, making you more sophisticated (and perhaps higher paid) database users/administrators. The course has a group course project in which you will build a simple, but fairly complete, single-user relational database engine. Note, in this course you will not learn the details of how to use any specific commercial database system, or the intricacies of SQL programming. This course is designed to cover the fundamental database concepts and the implementation techniques that are used in relational database engines. Using the course project, you will actually build a few key components of a database engine. If you are interested in the details of SQL programming, or the operation of a specific commercial database system, you will be able to pick this up very easily after you have taken this course.

    Prerequisites EECS 380: Data Structures and Algorithms or equivalent. WARNING: The course project is programming intensive and requires that you be comfortable programming in C++. For most of you, the course project will be the largest and most complex software project that you have built so far. If you are not comfortable programming in C++, you should take a lower-level course to build these skills, and take 484 in a later academic term.

    Text: Database Management Systems (2nd edition) by Raghu Ramakrishnan and Johannes Gehrke, McGraw Hill 1999.

    Check Times, Location, and Availability Cost: No Data Given. Waitlist Code: 1

    CMPTRSC 486 / EECS 486. Object-Oriented Software Development.

    Section 001.

    Instructor(s):

    Prerequisites: CS 281. (4). CAEN lab access fee required for non-Engineering students.

    Credits: (4).

    Lab Fee: CAEN lab access fee required for non-Engineering students.

    Course Homepage: http://www.eecs.umich.edu/eecs/courses/eecs486/

    No Description Provided.

    Check Times, Location, and Availability


    CMPTRSC 487 / EECS 487. Interactive Computer Graphics.

    Section 001.

    Instructor(s): Jon W Harris (harrisjw@umich.edu), Timothy J Hoffman

    Prerequisites: CS 281 and senior standing. (3). CAEN lab access fee required for non-Engineering students.

    Credits: (3).

    Lab Fee: CAEN lab access fee required for non-Engineering students.

    Course Homepage: http://www.eecs.umich.edu/courses/eecs487/f01/index.html

    The course will have four major focus areas:

    • Mathematics for Computer Graphics
      This includes the representation and manipulation of points, lines, planes, and vectors; 2-D and 3-D coordinate transformations, and their representation as matrices; 3-D viewing and perspective.
    • Geometric Modeling
      Includes the modeling hierarchy, facets, polygons, curves, splines, and solids models (combinatoric solid geometry CSG).
    • Rendering
      Including scan line and ray tracing techniques, camera models, illumination and reflection models for surfaces, shadowing, texture mapping, and anti-aliasing.
    • Applications
      Graphical User Interfaces, Visualization, Animations

    While not a formal prerequisite, familiarity with simple trigonometry and linear algebra concepts will make the course material easier to understand and comprehend. Likewise, familiarity with object oriented programming techniques is a plus in developing programs driven by graphical user interfaces.

    Programming exercises will use the C (or C++) language for general-purpose programming; Tcl/Tk, for UI development, and OpenGL for 3-D graphics. We will review Tcl/Tk and OpenGL in class and discussion; you are assumed to know C or C++. Extensive information about Tcl/Tk and OpenGL is available on the web. Check the class web page for links.

    You will undertake written assignments and programming assignments to explore and increase your understanding of the concepts covered in this course. Final course grades will be based on the total points earned on the homework, computer programming projects, and the two exams.

    Class Text: Computer Graphics; Donald Hearn, M. Pauline Baker Source Code Link: http://www.ncsa.uiuc.edu/Vis/Graphics/code.html Interactive Computer Graphics, A Top-Down Approach with OpenGL; Edward Angel. Source Code Link: http://thelma.cs.unm.edu/~angel/BOOK/SECOND_EDITION/

    Check Times, Location, and Availability Cost: No Data Given. Waitlist Code: 1

    CMPTRSC 489 / EECS 489. Computer Networks.

    Section 001.

    Instructor(s): Sugih Jamin (jamin@umich.edu)

    Prerequisites: CS 482. (4). CAEN lab access fee required for non-Engineering students.

    Credits: (4).

    Lab Fee: CAEN lab access fee required for non-Engineering students.

    Course Homepage: http://irl.eecs.umich.edu/jamin/courses/eecs489/

    Protocols and architectures of computer networks. Topics include client-server computing, socket programming, naming and addressing, media access protocols, routing and transport protocols, flow and congestion control, and other application-specific protocols. Emphasis is placed on understanding protocol design principles. Programming problems to explore design choices and actual implementation issues assigned.

    If you want to learn how to design way-cool Web pages, how to build and maintain a killer Web site, or how to setup, administer, and engineer a LAN, this course is not for you. In this course we do not study how modem works, nor do we study how ISDN works. We do not study Novell Netware Administration and we do not learn how to use Adobe Photoshop. We do not learn how to set up a chat room, nor how to set up an electronic guest book. We do try to understand how networks operate and how network applications are written. We study the workings of the Ethernet and the Internet: how packets are routed, how packets are transmitted, and what to do when there is network congestion. We look at packet headers and routing and transmission protocols. We learn what sockets are and how to use them. And we write code. We write code to implement various routing and transmission protocols. We write code to build client-server applications. There will be a lot of programming. You should know what processes and threads are and be familiar with concurrency and interprocess communication. EECS 482 (Introduction to Operating Systems) is a strict prerequisite. You must also have good working knowledge of C and UNIX. An introduction to probability course such as EECS 401, EECS 501, Math 425, Math 525, or Stat 412 is highly recommended as a co-requisite.

    Textbooks: Kurose and Ross, Computer Networking: A Top-Down Approach, Addison-Wesley, 2001. ISBN 0-201-4711-4. W.R. Stevens, UNIX Network Programming, vol. 1: Networking APIs: Sockets and XTI, 2nd. ed., Prentice-Hall, 1997. (Don't buy the first edition!)

    Check Times, Location, and Availability Cost: No Data Given. Waitlist Code: 1

    CMPTRSC 492 / EECS 492. Introduction to Artificial Intelligence.

    Section 001.

    Instructor(s): William Birmingham (wpb@umich.edu)

    Prerequisites: CS 281. (4). CAEN lab access fee required for non-Engineering students.

    Credits: (4).

    Lab Fee: CAEN lab access fee required for non-Engineering students.

    Course Homepage: http://ai.eecs.umich.edu/people/wpb/492.f.2001/

    Course Objectives:
    The purpose of this course is to introduce the student to the major ideas and techniques of Artificial Intelligence, as well as to develop an appreciation for the engineering issues underlying the design of intelligent, computational agents. The successful student will finish the course with specific modeling and analytical skills (e.g., search, logic, probability), knowledge of many of the most important knowledge representation, reasoning, and machine-learning schemes, and a general understanding of AI principles and practice. The course will serve to prepare the student for further study of AI, as well as to inform any work involving the design of computer programs for substantial application domains.

    Textbook:
    Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach, Prentice-Hall, 1995.

    Prerequisites:
    EECS 380, or equivalent experience. We assume programming experience and knowledge of programming language concepts, and familiarity with algorithmic concepts, such as graph search and computational complexity. We will not hesitate to employ mathematics where appropriate.

    Grading:
    Problem sets 60% (10% each); Exams 40% (exams 10% each; final 20%); (subject to slight adjustments at the discretion of instructor).

    Check Times, Location, and Availability Cost: No Data Given. Waitlist Code: 1

    CMPTRSC 494 / EECS 494. Computer Game Design and Development.

    Section 001.

    Instructor(s): John E Laird (laird@umich.edu)

    Prerequisites: CS 281. (4). CAEN lab access fee required for non-Engineering students.

    Credits: (4).

    Lab Fee: CAEN lab access fee required for non-Engineering students.

    Course Homepage: http://ai.eecs.umich.edu/soar/Classes/494/

    In this course we will study the technology, science, and art involved in the creation of computer games. The course will emphasize hands-on development of games. We will study a variety of software technologies relevant to games including programming languages, scripting languages, operating systems, file systems, networks, simulation engines, and multi-media design systems. We will also study some of the underlying scientific concepts from computer science and related fields including: simulation and modeling, graphics, artificial intelligence, real-time processing, and game theory. Finally, we will study the art and design principles for developing useable and engaging games including: software engineering, human computer interaction, thematic structure, graphic design, choreography, music and sound effects, and game aesthetics.

    The course will include visiting lectures and a variety of group projects. The group projects will involve system implementation, but emphasize design and use of existing tools. The final group project will require the students to go through all phases of system conceptualization, specification, design, implementation, and evaluation.

    Required texts: Tricks of the Windows Game Programming Gurus, Andre LaMothe, SAMS publishing. Game Architecture and Design, Rollings & Morris, Coriolis. Coursepack Available from Dollar Bill Copying ($61.28)

    Check Times, Location, and Availability Cost: No Data Given. Waitlist Code: 1

    CMPTRSC 498 / EECS 498. Special Topics.

    Section 001 Introduction to Micro Electro Mechanical Systems (MEMS)

    Instructor(s): Khalil Najafi

    Prerequisites: (1-4). CAEN lab access fee required for non-Engineering students.

    Credits: (1-4).

    Lab Fee: CAEN lab access fee required for non-Engineering students.

    Course Homepage: No homepage submitted.

    Micro Electro Mechanical Systems (MEMS) are miniature devices (with micron size tolerances) that are created using various techniques including many similar to those used to manufacture integrated circuits, and are capable of performing many tasks and functions that involve mechanical, electrical, optical, fluidic, and other types of signals. MEMS and Integrated Microsystems are increasingly finding applications in many areas including automotive, health care, industrial processing, environmental monitoring, biomedical systems, chemical analysis, energy sources, telecommunication, aerospace systems, consumer appliances, and many others. This course introduces students to this rapidly emerging, multi-disciplinary, and exciting filed. It will cover thin-film process technologies, photolithographic techniques, deposition and etching techniques, and the other technologies that are central to MEMS fabrication. A designer of MEMS requires knowledge and expertise across several different disciplines. Therefore, this course will pay special attention to teaching of fundamentals necessary for the design and analysis of devices and systems in mechanical, electrical, fluidic, and thermal energy/signal domains, and will teach basic techniques for multi-domain analysis (e.g., electromechanical, electrothermal). Fundamentals of sensing and transduction mechanisms (i.e., conversion of non-electronic signals to electronic signals), including capacitive and piezoresistive techniques, and design and analysis of micromachined miniature sensors and actuators using these techniques will be covered. Many examples of existing devices and their applications will be reviewed.

    Course Organization and Format:
    This course is intended for undergraduate seniors and first year-graduate students, and is the first in a series of four MEMS courses to be offered as part of a comprehensive MEMS educational program within the NSF-ERC WIMS Center. It is an introductory course designed for those students who are not familiar with MEMS, microfabrication technologies, integrated circuits, or non-electrical devices and systems. Therefore, the course pre-requisites are selected to allow students from MANY engineering or science disciplines, including mechanical, electrical, chemical, aerospace, biomedical, and materials engineering to take the course. Therefore, the course is organized into lectures and recitations. The lectures present material that ALL students need to learn. Recitations are intended to teach students from different disciplines in areas where they may need additional training, including the fundamentals and basics of heat transfer, mechanics (statics, and dynamics) basics of RLC circuit analysis, analysis of second-order systems in the frequency domain, etc. This course is being offered as a multi-institutional course and in partnership with Michigan Technological University (MTU) and Michigan State University (MSU). The course is taught over the instructional networks of these universities, and students will have access, on-demand, to all lecture materials, assignments, etc. over the Internet via video streaming.

    Prerequisites: Senior standing, engineering, math, chemistry, physics, and differential equations.

    Check Times, Location, and Availability Cost: No Data Given. Waitlist Code: No Data Given.

    CMPTRSC 498 / EECS 498. Special Topics.

    Section 004 Special Topics in Embedded Control Systems

    Instructor(s): James S Freudenberg

    Prerequisites: (1-4). CAEN lab access fee required for non-Engineering students.

    Credits: (1-4).

    Lab Fee: CAEN lab access fee required for non-Engineering students.

    Course Homepage: http://www.eecs.umich.edu/courses/eecs498-02/

    No Description Provided.

    Check Times, Location, and Availability


    CMPTRSC 498 / EECS 498. Special Topics.

    Section 005.

    Instructor(s):

    Prerequisites: (1-4). CAEN lab access fee required for non-Engineering students.

    Credits: (1-4).

    Lab Fee: CAEN lab access fee required for non-Engineering students.

    Course Homepage: No homepage submitted.

    No Description Provided.

    Check Times, Location, and Availability


    CMPTRSC 543 / EECS 543. Knowledge-Based Systems.

    Section 001.

    Instructor(s): Martha Pollack (pollackm@umich.edu)

    Prerequisites: CS 281 and graduate standing. (3). CAEN lab access fee required for non-Engineering students.

    Credits: (3).

    Lab Fee: CAEN lab access fee required for non-Engineering students.

    Course Homepage: http://www.eecs.umich.edu/~pollackm/eecs543fall01/index.html

    Knowledge-based systems (also called just knowledge systems) are sophisticated AI programs that solve complex problems. These programs have found considerable use in industry, and are finding exciting new applications in cyberspace (e.g., as intelligent agents). Knowledge-based systems are particularly suited to these kinds of applications because they help users define and modify knowledge for tasks in a way that users are comfortable with, and then use this knowledge based on complex inference techniques.

    The goal of this class is provide students with an understanding of the principles and system-building experience needed to create a knowledge system by introducing the student to programming languages and techniques that promote a knowledge-based, or declarative, approach to software development. Although a rigorous characterization of what this means is elusive (though we will attempt to accomplish this in the course), what it amounts to practically is emphasis on programming constructs that facilitate:

    • building levels of abstraction and interpretation
    • modular specification of functionality (e.g., object orientation)
    • representations of propositions and inference (e.g., logic)

    Historically, researchers in the field of Artificial Intelligence have identified these properties as important for development of "intelligent" (whatever that means) programs, and thus have developed languages embodying them. We will explore this "knowledged-based" programming methodology through substantial exercises in three "AI" languages:

    1. Common Lisp (including its object-oriented extension, CLOS)
    2. Prolog
    3. SOAR (a problem solving architecture based on production rules)

    Successful students will complete the course with a working knowledge in each of these languages, and more importantly, with a broader perspective on programming itself.

    Check Times, Location, and Availability Cost: No Data Given. Waitlist Code: 1

    CMPTRSC 570 / EECS 570. Parallel Computer Architecture.

    Section 001.

    Instructor(s): Steven K Reinhardt

    Prerequisites: CS 470. (3). CAEN lab access fee required for non-Engineering students.

    Credits: (3).

    Lab Fee: CAEN lab access fee required for non-Engineering students.

    Course Homepage: http://www.eecs.umich.edu/courses/eecs570/

    Pipelining and operation overlapping, SIMD and MIMD architectures, numeric and non-numeric applications, VLSI, WSI architectures for parallel computing, performance evaluation. Case studies and term projects.

    Course Objectives:

    • understand the fundamental issues of parallel computation (communication, synchronization, naming, etc.)
    • understand the various ways in which hardware and software can interact to address these issues in parallel systems
    • understand the basic cost, performance, and programmability tradeoffs involved in these interactions

    Prerequisites: EECS 470 (Computer Architecture). In particular, you should feel comfortable with caches, virtual memory, dataflow concepts, and instruction-level parallelism.

    Check Times, Location, and Availability Cost: No Data Given. Waitlist Code: 1

    CMPTRSC 571 / EECS 571. Principles of Real-Time Computing.

    Section 001.

    Instructor(s): Kang Geun Shin

    Prerequisites: CS 470 and CS 482. (3). CAEN lab access fee required for non-Engineering students.

    Credits: (3).

    Lab Fee: CAEN lab access fee required for non-Engineering students.

    Course Homepage: http://www.eecs.umich.edu/courses/eecs571/

    Principles of real-time computing based on high performance, ultra reliability, and environmental interface. Architectures, algorithms, operating systems, and applications that deal with time as the most important resource. Real-time scheduling, communications, and performance evaluation.

    Textbook: C. M. Krishna and Kang G. Shin, Real-Time Systems, McGraw Hill 97. Errata are maintained at http://www.ecs.umass.edu/ece/gradfac/krishna.html

    Check Times, Location, and Availability Cost: No Data Given. Waitlist Code: No Data Given.

    CMPTRSC 574 / EECS 574. Theoretical Computer Science I.

    Section 001.

    Instructor(s): Kevin J Compton

    Prerequisites: CS 376. (4). CAEN lab access fee required for non-Engineering students.

    Credits: (4).

    Lab Fee: CAEN lab access fee required for non-Engineering students.

    Course Homepage: http://www.eecs.umich.edu/~kjc/eecs574.html

    Fundamentals of the theory of computation and complexity theory. Computability, undecidability, and logic. Relations between complexity classes, NP-completeness, P-completeness, and randomized computation. Applications in selected areas such as cryptography, logic programming, theorem proving, approximation of optimization problems, or parallel computing.

    Text: Theory of Computational Complexity, Ding-Zhu Du and Ker-I Ko, Wiley.

    Homework is due in class one week after it is assigned. No late homework will be accepted. I will pick one or two problems from each assignment to grade. Your homework score will be based on the best 6 scores (out of 8) throughout the semester. You may work with others in the class on homework and consult any source you like, but the answers you turn in must be written (or typed) in your own hand. There will be three take-home exams handed out in class Oct. 6, Nov. 3, and Dec. 11. They will be due one week after they are handed out. You may use the textbook and course notes on these exams, but no other source. In particular, there may be no collaboration between students on the take-home exams.

    Grade: Exam 1 28%; Exam 2 28%; Exam 3 28%; Homework (best 6 of 8) 16%.

    Check Times, Location, and Availability Cost: No Data Given. Waitlist Code: 1

    CMPTRSC 579 / EECS 579. Digital System Testing.

    Section 001.

    Instructor(s): John Patrick Hayes

    Prerequisites: Graduate standing. (3). CAEN lab access fee required for non-Engineering students.

    Credits: (3).

    Lab Fee: CAEN lab access fee required for non-Engineering students.

    Course Homepage: http://www.eecs.umich.edu/courses/eecs579/index.html

    This course examines in depth the theory and practice of fault analysis, test generation, and design for testability for digital integrated circuits and systems. The topics to be covered include: circuit and system modeling; fault sources and types; the single stuck-line fault model; fault simulation methods; test generation algorithms for combinational and sequential circuits, including PODEM; testability measures; design-for- testability techniques; scan design; test compression methods; logic-level diagnosis; self-checking circuits; built-in self- testing (BIST); system-level diagnosis; processor and memory testing; VLSI and system-on-a-chip (SOC) testing; design verification and its relation to physical fault testing. A term paper or small experimental/research project will be part of the course. Current research issues, including topics suitable for M.S. or Ph.D. thesis research, will be discussed.

    Text: Digital System Testing and Testable Design, by M. Abramovici, M. A. Breuer and A. D. Friedman, New York, IEEE Press, 1990. (Required text). Additional reference material will be placed on reserve in the Media Union (Engineering) Library.

    Check Times, Location, and Availability Cost: No Data Given. Waitlist Code: No Data Given.

    CMPTRSC 584 / EECS 584. Advanced Database Systems.

    Section 001.

    Instructor(s): Hosagrahar V Jagadish

    Prerequisites: CS 484. (3). CAEN lab access fee required for non-Engineering students.

    Credits: (3).

    Lab Fee: CAEN lab access fee required for non-Engineering students.

    Course Homepage: http://www.eecs.umich.edu/~jag/eecs584/

    Survey of advanced topics in database systems. Distributed databases, query processing, transaction processing. Effects of data models: object-oriented and deductive databases; architectures: main-memory and parallel repositories; distributed organizations: data management for emerging areas: Internet applications, OLAP, data mining. Case studies of existing systems.

    This is an advanced database course that will give you a good understanding of the pieces of a database system and what is involved in building one. I will also try to give you a feeling for the role of databases in today's computing infrastructure and how this has evolved. This is NOT a course on how to use databases, though you will arguably be a better user if you have an understanding of what is going on "under the hood". Also, this is NOT a course on XML, even though XML and the inernet will be mentioned frequently.

    2 midterm exams. Both in-class. No make-ups for missed midterm exams. No final exam. Term Project: A course project is required.

    Check Times, Location, and Availability Cost: No Data Given. Waitlist Code: No Data Given.

    CMPTRSC 587 / EECS 587. Parallel Algorithms.

    Section 001 Parallel Computing

    Instructor(s): Quentin F Stout (qstout@umich.edu)

    Prerequisites: CS 281 and graduate standing. (3). CAEN lab access fee required for non-Engineering students.

    Credits: (3).

    Lab Fee: CAEN lab access fee required for non-Engineering students.

    Course Homepage: http://www.eecs.umich.edu/~qstout/587/

    This class is intended for students with diverse backgrounds, introducing them to the concepts of parallel computing. The emphasis is on developing efficient progrms using commercially available hardware (such as IBM, SGI, and Bewulf systems here on campus) and software standards (such as MPI and OpenMP). We'll cover topics such as speedup, domain decomposition, load balancing, synchronization, and shared vs distributed memory. You'll learn why it is fairly easy to get a couple or processors to work efficiently together, but very hard to get a hundred to do so.

    Work will involve a mix of written homeworks, programming projects, and a term project. Term projects can cover a wide range of topics as long as they are relevant to parallel computing. Graduate and advanced undergraduate students in many different departments have used these projects to start on a research topic or to incorporate parallelism into research already started. Many have gone on to jobs in parallel or scientific computing.

    Prerequisites: Fluency in Fortran or C, ability to analyze the running time of an algorithm, willingness to rethink how a problem should be solved.

    Check Times, Location, and Availability Cost: No Data Given. Waitlist Code: 1

    CMPTRSC 591 / EECS 591. Distributed Systems.

    Section 001.

    Instructor(s):

    Prerequisites: CS 482 and graduate standing. (4). CAEN lab access fee required for non-Engineering students.

    Credits: (4).

    Lab Fee: CAEN lab access fee required for non-Engineering students.

    Course Homepage: No homepage submitted.

    Principles and practice of distributed systems design. Computations, consistency semantics, and failure models. Programming paradigms including group communication, RPC, distributed shared memory, and distributed objects. Operating system kernel support; distributed system services including replication, caching, file system management, naming, clock synchronization, and multicast communication.

    Check Times, Location, and Availability Cost: No Data Given. Waitlist Code: 1

    CMPTRSC 595 / EECS 595 / LING 541. Natural Language Processing.

    Section 001 Meets with Information 661.001.

    Instructor(s): Dragomir Radev (radev@umich.edu)

    Prerequisites: Senior standing. (3). CAEN lab access fee required for non-Engineering students.

    Credits: (3).

    Lab Fee: CAEN lab access fee required for non-Engineering students.

    Course Homepage: http://perun.si.umich.edu/~radev/NLP/

    An introduction to computational linguistics, stressing the processing of written language but with supplementary discussion of topics relating to spoken language. The course will be based on the following textbook: Daniel Jurafsky and James H. Martin, Speech and Natural Language Processing, Prentice Hall, 1999.

    Topics covered in this course will include: finite state automata and finite state techniques for processing words, language models, tagging corpora for part-of-speech, context-free grammars, parsing techniques, unification grammars and unification-based parsing, probabilistic parsing, semantics, discourse modeling, word sense disambiguation and information retrieval, natural language generation, and (if time permits) machine translation.

    There will be a midterm and a final examination, as well as a course project and regularly assigned exercises. Non-CS students without strong programming experience will not have to do a project that requires programming.

    This course is the normal introduction to computational linguistics for advanced undergraduates or graduate students in Computer Science, the School of Information, or Linguistics, and normally is a prerequisite for more advanced courses in the area at the University of Michigan. For linguistics students, Linguistics 513 and any other 400- or more advanced level linguistics course are prerequisites. Computer literacy is essential; some programming experience would be helpful. Students in Computer Science or the School of Information should take the versions of this course offered in those units.

    Check Times, Location, and Availability Cost: No Data Given. Waitlist Code: 1

    CMPTRSC 598 / EECS 598. Special Topics in Electrical Engineering and Computer Science.

    Section 001 Quantum Computing Circuits

    Instructor(s): John Hayes, Igor Markov

    Prerequisites: Permission of instructor or advisor. (1-4). CAEN lab access fee required for non-Engineering students. May be repeated for credit.

    Credits: (1-4).

    Lab Fee: CAEN lab access fee required for non-Engineering students.

    Course Homepage: http://vlsicad.eecs.umich.edu/Quantum/EECS598/

    This special-topics course is intended to explore the area of quantum computation, focusing on the design and analysis of quantum logic circuits. No prior knowledge of quantum computing or quantum physics is required, but participants will be expected to read and present papers on topics of interest. After some introductory lectures on basic principles, the course will cover the following topics: quantum circuit synthesis, simulation and testing, matrix methods, algorithm implementation, error-correction techniques, experimental systems, research problems.

    1. Part I. Introduction
      • Brief Overview of Quantum Computing
      • Basics of Quantum Mechanics and Mathematical/CS Background (2 lectures)
      • Classical vs Quantum: positive and negative results; sample algorithms
      • Basic examples of Quantum Circuits: adders, etc
      • An overview of implementation technologies and implied constraints
    2. Part II. Classical circuits
      • Brute-force Synthesis of Optimal Classical Circuits; Basic Heuristics
      • BDD-based Synthesis with Implicit representations
      • Basic ideas in circuit testing, ATPG, D-algorithm, redundancies, etc
      • Don't cares in classical circuits, SPFDs and related
      • Spectral ideas in circuit synthesis
      • Fault-tolerance, ECC....
      • Reversible circuits
    3. Part III. Quantum Circuits
      • The pivotal role of the Fourier transform in quantum computing
      • Circuits for the Quantum Fourier transform
      • Gate Libraries for Quantum Circuits
      • Straighforward synthesis of quantum circuits (following Cybenko)
      • Heuristics for minimization of quantum circuits
      • Quantum Measurement and don't cares of quantum circuits
      • Errors in quantum circuits, fault-tolerance, ECC
    4. Part IV. Simulation of quantum circuits/algorithms
      • Notations for quantum circuits and algorithms
      • Basic challenges, best-case vs worst-case
      • FFT-based and BDD-based simulation
    5. Part V. Research topics explored via student term projects. Each project will include a written report, a 30-min presentation as well as the design of software or logic circuits.

    Required textbook: Quantum Computation and Quantum Information by Michael A. Nielsen, Isaac L. Chuang Amazon Price: $47.95 (ships in 24 hours) Paperback 675 pages (September 2000) Cambridge Univ Pr (Pap Txt); ISBN: 0521635039;

    Check Times, Location, and Availability Cost: No Data Given. Waitlist Code: No Data Given.

    CMPTRSC 598 / EECS 598. Special Topics in Electrical Engineering and Computer Science.

    Section 002 Issues in High-Performance Deep-Submicron Design

    Instructor(s): David Blaauw (blaauw@umich.edu)

    Prerequisites: Permission of instructor or advisor. (1-4). CAEN lab access fee required for non-Engineering students. May be repeated for credit.

    Credits: (1-4).

    Lab Fee: CAEN lab access fee required for non-Engineering students.

    Course Homepage: http://www.eecs.umich.edu/courses/eecs598/eecs598.html

    As process technology has entered into deep-submicron dimensions, feature sizes of 0.15 and 0.13 micrometers are now common, resulting in a number of new challenges in the implementation of large designs. These issues are particularly critical in high performance designs, which are reaching multiple Giga Hertz today, and design and CAD engineers need to reckon with them. In this course, we will examine a number of the issues that the deep submicron designer has to face in order to implement high-performance circuits in the latest CMOS technologies.

    We will examine 5 topics that cover some of the key issues in the design of deep submicron ICs. These are:

    1. on-chip signal net noise,
    2. on-chip power supply integrity,
    3. on-chip inductance effects, and
    4. standby leakage current.
    5. implementation issues in silicon-on-insulator (SOI) technology,

    For each topic, we will first study applicable analysis and modeling techniques and then examine the impact of these phenomena on VLSI design. We will cover both the fundamental principles involved as well as practical issues based on industrial case studies.

    Course Credit and Grade: The course can be taken for 1, 2 or 3 credits, with associated expectation as follows:

    1. 1 credit option: the student must complete the paper review homework and present two papers to the class over the course of the term. Class grade will be determined as follows: paper presentations (45%), paper review homework (35%), and class participation (20%)
    2. 2 credit option: In addition to the requirements for the 1 credit option, the student must complete a survey paper at the end of the course. The topic of the survey paper will be selected by the student in consultation with the instructor. The survey paper must consist of an in-depth review of the publications and current approaches in the selected topic. Class grade will be determined as follows: paper presentations (30%), paper review homework (20%), and class participation (10%), survey paper (40%)
    3. 3 credit option: In addition to the requirements for the 1 credit option, the student must complete a final project at the end of the course. The topic of the final project will be selected by the student in consultation with the instructor. The final project must consist of a new analysis or solution method to a specific deep submicron issue. The quality of the class project is expected to be of a level suitable for submission to a workshop conference. Class grade will be determined as follows: paper presentations (30%), paper review homework (15%), and class participation (10%), class project (45%)

    Prerequisites: Familiarity with elementary circuits, circuit analysis techniques, device physics, logic design, and CMOS integrated circuit design techniques is assumed. Graduate level standing is required.

    Check Times, Location, and Availability Cost: No Data Given. Waitlist Code: No Data Given.


    Undergraduate Course Listings for CMPTRSC.


    Page


    This page was created at 9:14 AM on Thu, Oct 11, 2001.


    LSA logo

    University of Michigan | College of LS&A | Student Academic Affairs | LS&A Bulletin Index | Department Homepage

    This page maintained by LS&A Academic Information and Publications, 1228 Angell Hall

    Copyright © 2001 The Regents of the University of Michigan,
    Ann Arbor, MI 48109 USA +1 734 764-1817

    Trademarks of the University of Michigan may not be electronically or otherwise altered or separated from this document or used for any non-University purpose.