Readme, Course Information, Course Description, Dates, Photos Fun, Your Marks, Forum, Solutions
Topics | Slides | Key Notes | Questions |
Intro | |||
Quantifiers | |||
Loop Invariants | |||
Recursion | |||
Network Flow | |||
Linear Programming | |||
Randomized Algorithms | |||
Entropy | |||
Greedy Algorithms | |||
Algebra | |||
FFT | |||
Common Knowledge | |||
Dynamic Programming | |||
Approximation Algorithms | |||
NP-completeness | |||
Computability | |||
Other Stuff |
About Course:
Most all of our grad students are not interested in theoretical
computer science, but they each must take a course in it. This course
that caters to them. Every two weeks we cover a new topic in
theoretical computer science. It would be an embarrassment to graduate
a student if he did not know the foundations of these topics. Despite
how much they struggle with it, they seem to enjoy it and think that
it is useful. I am embarrassed at times, however, how similar it is to
3101.
These courses teach 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.
Quantifiers:
(Steps,
ppt,
Questions)
(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.)
Loop Invariants: (1.5 classes)
(Steps,
ppt,
Questions)
(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.)
Recursion: (4 classes)
(Steps,
ppt,
pdf,
Questions)
(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.)
Network Flow: (2 classes)
(ppt,
Questions)
(This is how to best transport goods from factories to stores.)
Linear Programming: (ppt)
(Extremely useful in industry, eg What ingredients put in your
hamburger today to minimize its cost.)
Randomized Algorithms: (3 class)
(pdf,
Rudich1.pptx,
Rudich2.pptx,
Questions)
(Surprisingly when computing, it sometimes helps to flipping coins.)
Greedy Algorithms: (2 classes)
(Steps,
ppt
Questions)
(These are the simplest possible algorithms. Proving they work,
however, is hard.)
Algebra: (3 class)
(ppt,
Questions)
(A quick introduction)
More Recursion - Fast Fourier Transformations: (3 class)
(ppt,
Questions)
(Used for processing signals, compressing images, and quickly
multiplying integers.)
Distributed Systems: mud on forehead & common knowledge:
(1 class)
(ppt,
Questions)
(Fun information theory. I know that my mom knows that my father loves me.)
Dynamic Programming: (2 classes)
(ppt,
Questions)
(A harder instance is solved by filling out a table of solutions for
easier sub-instances.)
Approximation Algorithms: (1 class)
(ppt)
(The problems that do not have quick algorithms can sometimes be
solved approximately.)
NP-completeness::
(ppt,
pdf,Questions)
(Most search problems that industry cares about are believed to not
have poly-time algorithms.)
Computability: (3 classes)
(ppt,
Questions,
ppt)
(Some computational problems are solved by NO algorithms.)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.