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


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 metaalgorithm 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 subinstances.)
Unit 6:
Reductions and NPCompleteness
(HTA 20; CLRS 34) (3 hours)
(Reductions involve writing an algorithm for one problem from that for
another. NPCompleteness give strong evidence that most search
problems that industry cares about are believed to not have polytime
algorithms.)
Review
Topics not covered:
Yes covered a lot In fact, most of the book
Topics that we did not cover:
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.