EECS 477: Introduction to Algorithms

Basic information

• Lectures: Tues/Thur. 8:30-10:00, 1003 EECS
• Instructor: Prof. Igor Guskov (office 126 ATL) email: guskov@eecs.umich.edu
  
  • Office Hours: Thursdays 4-5pm (126 ATL)
• GSI: Joel VanLaven, email: jvanlav@umich.edu
  
  • Office Hours: Wed. 3:00-5:00, Sun cluster, third floor of the Media Union, or by appointment
• Discussion section: Wed. 8:30-9:30, 1303 EECS
• Course Web page: http://www.eecs.umich.edu/courses/eecs477/
• Syllabus
• Homework assignments
• Lecture slides
• Final projects page

News and Announcements

12/17: grades are posted (final and projects)
12/12: hw5 and hw6 solutions are posted.
12/8: The project due date is extended till Wednesday night.
11/26: Homework 6 is posted.
11/20: Final exam is scheduled for Monday, December 16th, from 10:30am till 12:30pm in room 1311 EECS

Students can post messages on the newsgroup umich.eecs.class.477 to clarify assignments, dates of exams, grading policies, etc. Messages that discuss solutions to homeworks and messages of personal nature are considered inappropriate and will be removed. Authors of inappropriate messages may be subject to university regulations.

Course Material

• Required text: ``Fundamentals of Algorithms'' by Brassard and Brately, Prentice Hall 1996
  
• Presentation slides from lectures: online
• Recommended online reference: Algorithms and Data Structures with C++ by Bruno Preiss
• 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

Course description

From Catalog: 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. Guskov.

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: 25%
• One project: 25%
• One midterm: 25%
• Final: 25%

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.

Homeworks and Projects

Homeworks assignments will be posted on the Web. Homeworks are usually due on Thursdays at noon in the mailbox in EECS 2420 (GSI room).

LATE HOMEWORK WILL NOT BE ACCEPTED. Please see the GSI about regrades.

Homework assignments and solutions can be found here.

Projects will be assigned individually and to groups of students by instructor. If you have a good/vague idea about what you would like to work on, discuss it with the instructor.

The projects page is here.

Potentially useful code for measuring time and memory consumption is avaiable here

Exam Policies

You are allowed to bring a 4" by 6" notecard with anything you like written on it. You may bring blank scratch paper. (Blue books will not be used.) No other material may be consulted on any of the exams.

Exam dates will be announced on the class Web page.

A sample midterm exam is available in PDF and Postscript.

A sample final exam is available in PDF and Postscript.