COSC6111 CSE 6111: Advanced Algorithm Design and Analysis

 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

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

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

(The basic math needed to understand machine learning)

One Hour Intro
Magic
Overview
Training Data
Machine
Error Surface
Learning
Generalizing
Singularity
EECS2001 Topics
Magic, Importance, Applications
Genetic Algorithms
Linear Regression, Neural Networks
X Matrix Multiplication
X Generalizing from Training Data
Review
X Back Propagation
X Example, Convolutional, Recurrent
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

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

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

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.