Readme, Course Information, Course Description, Mental Health, Dates, Fun, Your Marks, Forum, Solutions

Topics	Slides	Key Notes	Questions
Intro
(3101) Quantifiers
(3101) Loop Invariants
(3101) Recursion
(3101) Network Flow
Linear Programming
Machine Learning
Randomized Algorithms
Entropy
(3101) Greedy Algorithms
Algebra
FFT
Common Knowledge
(3101) Dynamic Programming
Approximation Algorithms
(3101) NP-completeness
(2001) 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.)

Existential and Universal quantifiers
Fun

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

Proof of Correctness
More of Input vs Output
Two Graph Path Problems (pdf)
X Lower Bounds (pdf)
X Amortized Analysis (Create-Delete, Trits)
X Maximal Rectangles ppt

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

X-> Friends
Derivatives of Functions
Recursive multiplication
Recursive Pictures
Multiply two integers by cutting into d pieces (assignment)
Parsing (pdf, Java)
Ackermann's Function
Fast Fourier Transformations

Network Flow: (2 classes) (ppt, Questions)
           (This is how to best transport goods from factories to stores.)

X-> The Primal-Dual Hill Climbing Method
The Steepest Ascent Hill Climbing Algorithm (pdf)
Bipartite Matching

Linear Programming: (ppt)
           (Extremely useful in industry, eg What ingredients put in your
           hamburger today to minimize its cost.)

X-> What to put in a hotdog
Primal Dual

Machine Learning Made Easy:
           (The basic math needed to understand machine learning)

One Hour Intro
Magic
Overview
Training Data
Machine
Error Surface
Learning
Gradient Descent
Generalizing
Singularity
EECS2001 Topics
Magic, Importance, Applications
Genetic Algorithms
Linear Regression, Neural Networks
X Matrix Multiplication
X Gradient Descent, Steepest Direction
X Generalizing from Training Data
Review
More Advanced Topics
X Back Propagation
X Example, Convolutional, Recurrent
Generative Adversarial Networks
Clustering
Maximum Likelihood
Dimension Reduction
Reinforcement Learning

Randomized Algorithms: (3 class) (pdf, Rudich1.pptx, Rudich2.pptx, Questions)
           (Surprisingly when computing, it sometimes helps to flipping coins.)

Random variables, random walks, Chernoff bounds.
Las Vegas & Monte Carlo Algorithms, primes.
Calculating probabilities differently to handle causality
Max Cut, Expander Graphs.
Choose a new door & Driver's Licenses in Lockers (board)
Gambling Dice html
Yao's Min-Max (board)
Entropy
Komorgove Complexity: A string if "random" if the smallest TM to output it has a large description.

Greedy Algorithms: (2 classes) (Steps, ppt Questions)
           (These are the simplest possible algorithms. Proving they work,
           however, is hard.)

Interval Point Cover
Lower Bounds ppt

Algebra: (3 class) (ppt, Questions)
           (A quick introduction)

Fields
      GCD
      Powers mod p
      Fermat Little Theorem, Roots of Unity, & Generators
      Z mod p vs Complex Numbers
      Cryptography (Josh's, Rudich.pptx)
      Other Finite Fields
Vector Spaces
      Degrees of Freedom
      Colour
      Error Correcting Codes
      Euclidean Spaces
Linear Transformations
      Integrating
      Classical vs Quantum Probabilities
Changing Basis
      Fourier Transformations (sine)
      Fourier Transformations (JPEG)
      Fourier Transformations (Polynomials)
Other Algebra
      X Taylor Expansion
      X Counting with Generating Functions
      X Primes Numbers

More Recursion - Fast Fourier Transformations: (3 class) (ppt, Questions)
           (Used for processing signals, compressing images, and quickly
           multiplying integers.)

Change from Time to Polynomial Basis
Evaluating & Interpolating
FFT in nlogn Time
Roots of Unity
Same FFT Code & Butterfly!
Inverse FFT
Polynomial Multiplication
Integer Multiplication

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

Knowing Mud Problem
Boys Learn Common Knowledge
Formal Definition of "Knowing"
Applying Formal Definition to Mud Problem

Dynamic Programming: (2 classes) (ppt, Questions)
           (A harder instance is solved by filling out a table of solutions for
           easier sub-instances.)

Skip most of slides & start with Knapsack
Could do Event Scheduling Problem, Parsing, & Satisfiability if desired.
Bird-Friend Method & Shortest Path Method (pdf)
Pebbles (pdf)

Approximation Algorithms: (1 class) (ppt)
           (The problems that do not have quick algorithms can sometimes be
           solved approximately.)

Knapsack
Clique
Max Cut

NP-completeness:: (ppt, pdf,Questions)
           (Most search problems that industry cares about are believed to not
           have poly-time algorithms.)

History
Course vs Schedule
Circuit vs Airplane
Circuit vs 3-Colouring
Non-Deterministic Poly-Time
Reductions
K-Clique vs K-Independent Set
12 Steps
Any P <= Sat
3-Col <= 3-Sat
Sat <= 3-Col
More Problems
12 Steps in More Depth
Making Change scan
Embedding points with distortion pdf

Computability: (3 classes) (ppt, Questions, ppt)
           (Some computational problems are solved by NO algorithms.)

Diagonalization & Uncomputability
Halting Problem
Time Hierarchy
Godel's Incompleteness Theorem

Other Stuff:

Intro to Quantum: Shor's factoring (1 class) (stuff)
Concurrency Theory:
Structural Complexity: polytime hierarchy, P-space, Exp-time
Data Structures: dynamic perfect hashing
Rudich's course

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.