COSC6111 CSE 6111: Advanced Algorithm Design and Analysis

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.)


Other Stuff:
.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.