EECS3101 EECS 3101: Design and Analysis of Algorithms

Readme, Course Information, Course Description, Policies, Video Dates, Photo, Fun, Your Marks, Forum, Class

Material/Units 0 1 2 3 4 5 6
Slides
Recording S14
Recording F14 /
Recording S15
Steps
Assignments
Assignment Solutions
Practice Tests
Practice Solutions
Unit Tests (dates)
Units:


About Course:
     This course teaches how to think about algorithms in an abstract way
     so that one can talk about them, design new ones, and know that they
     are correct. Though Jeff will cover various algorithm as examples,
     the goal really is to teach the students to think abstractly about the
     key meta-algorithm techniques that everyone should know. These
     techniques are abstract enough to apply to most any problem that you
     will face in your job and in your life. Jeff has had many graduated
     students tell him that his courses were the most useful they had ever
     taken.

Request:
     Jeff tends to talk too fast. Please help him go pole pole slowly.

Readings:

Introduction (ppt) (1 hour)

Unit 0: Relevant Mathematics (0 hours: blended with in)
           (Before a student can understand or prove anything in mathematics, it
           is essential to first be able to res present it in first order
           logic. Hence, Jeff reviews it in each of his courses. We also look at
           asymptotic of running times, solving recurrence relations, and
           summations.)

Unit 1: Loop Invariants for Iterative Algorithms (6 hours)
           (Jeff strongly believes that this is the most important topic in
           Algorithms. Instead of worrying about the entire computation, only
           worry about one step at a time - make progress while maintaining the
           loop invariant.)

Unit 2: Recursive Algorithms (6 hours)
           (Again do not try to understand the entire computation. Trust your
           friends to solve a smaller instances of your problem and use these to
           the solve your own instance.)

Unit 3:

Relevant Mathematics (see unit 0)

Graph Search Algorithms (4.5 hours)
           (Graphs, ie nodes and edges, are very useful for representing
           data. The first task on them is to search through the nodes. )

Network Flow (3 hours)
           (This is how to best transport goods from factories to stores. We
           briefly mention Linear Programing which is extremely useful in
           industry, eg What ingredients put in your hamburger today to minimize
           its cost.)

Unit 4: Greedy Algorithms Methods (4.5 hours)
           (These are the simplest possible algorithms. Proving they work,
           however, is hard.)

Unit 5: Dynamic Programming (6 hours)
           (A harder instance is solved by filling out a table of solutions for
           easier sub-instances.)

Unit 6: Reductions and NP-Completeness  (HTA 20; CLRS 34) (3 hours)
           (Reductions involve writing an algorithm for one problem from that for
           another. NP-Completeness give strong evidence that most search
           problems that industry cares about are believed to not have poly-time
           algorithms.)

Review

Topics not covered: Yes covered a lot In fact, most of the book
Topics that we did not cover:

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.