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

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

Section

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

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

Multiplication

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

Literature

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

Randomized divide and conquer

• Median, Selection, and Quicksort
• Derandomization

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

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

Dynamic programming IV

• Bellman-Ford algorithm
• Applications

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.

Network flow

• 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
• 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). We will provide all definitions and remind you on necessary theorems.

Max flow/min cut

• Ford-Fulkerson algorithm

Literature

Network flow in polynomial time

Literature

Flow algorithm applications I

Literature

Flow algorithm applications II

Literature

Linear programming I

Literature

Linear programming II

Literature

Non-deterministic polynomial time I

Literature

Non-deterministic polynomial time I

Literature

Non-deterministic polynomial time II

Literature

Non-deterministic polynomial time III

Literature

Algorithms for linear programming

Literature

Approximation algorithms

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.

Parametrized complexity, SAT solvers, quantum computing

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 CSE2 345
• 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). We will provide all definitions and remind you on necessary theorems.