Introduction to Algorithms

Thinking like a computer scientist

• Preamble: course logistics, information, etc.
• The stable matching algorithm
• Pset 1 released due Apr 9th

Literature

• K&T: 1

The stable matching algorithm

• Continuation of stable matching algorithm
• The RAM model for computation

Literature

• K&T: 1.2-2.4

Overview and stable matchings

Graph traversal

• Overview of the course
• Introduction to greedy algorithms

Literature

• K&T: 3-3.2, 4.1

Graph traversal

• Breadth- and depth-first search
• Pset 2 released due Apr 16th

Literature

• K&T: 3.3-3.6, DPV: 4.2-4.3

Topological sort and greedy algorithms

• Topological sort
• Principles of greedy algorithms
• Exchange principle, greedy algorithm proof techniques
• Minimum lateness problem

Literature

• K&T: 4-4.2, DPV: 5-5.1

Graph Traversal and Algorithm Proofs

Greedy approximation and graph algorithms

• Max cut problem and greedy approximation algorithm
• Shortest path problem, Dijkstra's

Literature

• K&T: 12.4,4.4-4.7, DPV: 4.4-4.7

Minimum spanning trees

• Minimum spanning trees
• Prim's and Kruskal's algorithms
• k-clustering of datapoints
• Pset 3 released due Apr 23rd

Literature

• K&T: 12.4,4.4-4.7, DPV: 4.4-4.7

Divide and conquer algorithms

• Binary search and mergesort
• 2D Euclidean shortest distance
• The master theorem

Literature

• K&T: 5-5.4, DPV: 2.2-2.4

Greedy algorithms

Multiplication

• Matrix, integer, and polynomial multiplication
• Strassen's algorithm
• Karatsuba's algorithm
• Fast Fourier Transform
• Convolution, Image processing

Literature

• K&T: 5.5-5.6, DPV: 2.5-2.6

Randomized divide and conquer

• Median, Selection, and Quicksort
• Derandomization
• Pset 4 released due Apr 30th
• Pset 4 ¾ released due May 7nd

Literature

• K&T: 13.5, DPV: 2.4

Dynamic programming I

• Principles of dynamic programming
• Tribonacci numbers
• Edit distance

Literature

• K&T: 6,6.2,6.6, DPV 6.3

Divide and Conquer

Dynamic programming II: The Knapsack problem

• Brute force algorithm
• Dynamic programming algorithm
• Approximation algorithm

Literature

• K&T: 6.4, 11.8, DPV 6.4

Dynamic programming III

• Space complexity
• RNA secondary sequences
• Top-down vs bottom-up

Literature

• K&T: 6.1-6.3, 6.5, 6.8, DPV 6.6

Dynamic programming IV

• Bellman-Ford algorithm
• Applications

Literature

• K&T: 6.8-9, DPV 6.6

Midterm review

Question & Answer

• With Professor Nirkhe. Location: CSE2 G01. Time: 5:30pm-7:30pm.
• No planned topic. Bring any questions you have or topics you want clarified.
• Recording quality may be wanting as it will be on whiteboard.

Negative cycles and network flow

• Detecting negative cycles with Bellman-Ford
• Definition of max flow and min cut
• Value of a flow, equivalent definitions
• Greedy flow algorithm: Ford-Fulkerson

Literature

• K&T: 7-7.2

Midterm

• Location: Lecture Hall CSE2 G20
• Time: 1 Hour. Starts exactly at 3:30 and ends exactly at 4:30.
• Disability Requests that are approved will be in CSE2 345 starting at 3:30 as well.
• Contact head TAs to arrange your specific requirements. Otherwise we assume you are taking standard exam despite your disability requests.
• You may bring 1 8.5x11 page of notes (both sides); see the midterm coversheet for details.

Max flow/min cut

• Max flow/min cut duality
• Augmenting paths algorithm
• Ford-Fulkerson algorithm
• Application to bipartite matching

Literature

• K&T: 7.2-7.5

Dynamic programming and midterm postmortum

Network flow in polynomial time

• Finding better augmenting paths
• The Edmonds-Karp algorithm
• Hall's theorem
• Edge disjoint paths

Literature

• K&T: 7.5-7.7,7.12

Flow algorithm applications

• Network connectivity
• Capacity demands
• Baseball winner problem

Literature

• K&T: 7.5-7.7,7.12

Linear programming I

• Linear algebra/geometry review
• Optimization problems
• Definition ofa linear program
• Max flow as a linear flow

Literature

• DPV 7-7.3

Network Flow/Linear Programming

Linear programming II

• Linear programming example
• Max flow as a linear program
• Linear programming duality

Literature

• DPV 7.4-7.5

Linear programming III

• Linear programming duality
• Max flow/min cut

Literature

• DPV 7.6

Linear programming IV

• Simplex method
• Interior point and ellipsoid methods
• Boolean functions as LPs

Literature

• DPV 7

Linear Programming/Final Prep

P vs NP and problems that are just too hard

• Definitions of P, NP, EXP
• Definition of a reduction
• Examples of problems in NP

Literature

• K&T 8.1-8.4, DPV 8.1-8.3

Non-deterministic polynomial time II

• NP-completeness and the first NP-complete problem

Literature

• K&T 8.1-8.4, DPV 8.1-8.3

NP-Completeness

Non-deterministic polynomial time III

• 3-SAT is NP-complete
• Vertex Cover and 3-Color are NP-complete

Literature

• K&T 8.1-8.4, DPV 8.1-8.3

Non-deterministic polynomial time IV

Literature

Recap Lecture

Literature

Question & Answer

• With Professor Nirkhe. Location: CSE2 G01. Time: 5:30pm-7:30pm.
• No planned topic. Bring any questions you have or topics you want clarified.
• Recording quality may be wanting as it will be on whiteboard.

Beyond 421

Literature

Final

• Location: Lecture Hall CSE2 G20
• Time: 2 Hour. Starts exactly at 2:30 and ends exactly at 4:30.
• Disability Requests that are approved will be in TBD starting at 2:30 as well.
• Contact head TAs to arrange your specific requirements. Otherwise we assume you are taking standard exam despite your disability requests.
• You may bring 1 8.5x11 page of notes (both sides); see the final coversheet for details.