EECS 586 - Design and Analysis of Algorithms
Section: 001
Term: WN 2018
Subject: Electrical Engineering and Computer Science (EECS)
Department: CoE Electrical Engineering and Computer Science
Credits:
4
Requirements & Distribution:
BS
Advisory Prerequisites:
EECS 281.
Other Course Info:
W.
BS:
This course counts toward the 60 credits of math/science required for a Bachelor of Science degree.
Repeatability:
May not be repeated for credit.
Primary Instructor:

Audience

In decreasing order of frequency, historically the students in this class have been
  • Gradute students in Computer Science and Engineering: For these students, this class can satisfy the Theory distributional requirements for the MS and PhD degrees, and helps satisfy the 500-level course requirements.
  • Graduate students from other disciplines: For these students, this class can satisfy cognate requirements, and it can satisfy computer science requirements for students in the scientific computing program administered through LaSC (Laboratory for Scientific Computing). If you are interested in this program feel free to talk with me about it.
  • Undergraduate students: For CSE undergraduates it can satisfy computer-oriented technical elective requirements, and can be used to satisfy theory requirements (though this is not recommended unless you are good and you should talk to me before you try this). Students in other majors might also take it, though this is quite rare.
Most of the students enrolled are in the first category. For all students, the course can satisfy that burning desire to learn more about algorithms and computer science.

This is a core graduate computer science course, both here and elsewhere, and I make an attempt to show how algorithms relate to a wide range of software and hardware concerns. You'll find that the material is useful in other courses, in research, and in software projects outside the university. In some cases you'll use specific algorithms from class, while in many other situations you'll need to design a new algorithm using the techniques taught in the class.

Content

We will cover the design and analysis of efficient algorithms to solve fundamental computational problems in searching, sorting, graph theory, geometry, optimization, and decision theory. We cover a variety of algorithmic design principles, such as greedy algorithms, divide-and-conquer, and dynamic programming. We also cover the ways in which one analyzes the efficiency of algorithms, through the use of "generalized O-notation" for worst-case, expected-case, and competitive analyses, and some techniques for proving that an algorithm is an optimal solution to a problem.

Prerequisites

You should be able to program well in some standard procedural language such as C, C++, Fortran, or Java, had experience in data structures at least equivalent to EECS 280, and preferably had at least one class that used 280 as a prerequisite. In class we'll use pseudo-code, so the computer language you've used is not critical.

In terms of mathematical background, you should have had least EECS 203 or its equivalent and done well in it. Any additional upper level courses in theoretical computer science, logic, or discrete mathematics in which you had to do proofs will be helpful. In addition to discrete mathematics we will also make use of calculus and basic probability theory.

Texts

  1. Introduction to Algorithms by Corman, Leiserson, Rivest and Stein. Most of the course will be based on this book.
  2. Computers and Intractability by Garey and Johnson. This will be used near the end of the course.
There will also be additional handouts as the course progresses.

EECS 586 - Design and Analysis of Algorithms
Schedule Listing
001 (LEC)
 
10703
Open
1
 
85
MW 12:00PM - 1:30PM
Note: STUDENTS ARE AUTO-ENROLLED IN LECTURE WHEN THEY ELECT A DISCUSSION.
011 (DIS)
P
17737
Closed
0
 
52
F 1:30PM - 2:30PM
012 (DIS)
P
17738
Closed
0
 
33
F 2:30PM - 3:30PM
NOTE: Data maintained by department in Wolverine Access. If no textbooks are listed below, check with the department.


ISBN: 9780262033848
Introduction to algorithms, Author: Thomas H. Cormen ... [et al.]., Publisher: MIT Press 3rd ed. 2009
Required
Syllabi are available to current LSA students. IMPORTANT: These syllabi are provided to give students a general idea about the courses, as offered by LSA departments and programs in prior academic terms. The syllabi do not necessarily reflect the assignments, sequence of course materials, and/or course expectations that the faculty and departments/programs have for these same courses in the current and/or future terms.

No Syllabi are on file for EECS 586. Click the button below to search for a different syllabus (UM login required)

Search for Syllabus
The CourseProfile (ART) system, supported by the U-M Provost’s 3rd Century Initiative through a grant to the Digital Innovation Greenhouse, provides additional information about: course enrollments; academic terms and instructors; student academic profiles (school/college, majors), and previous, concurrent, and subsequent course enrollments.

CourseProfile (ART)