InstructorDavid Eng

Teaching AssistantsEdward Gan
Braden Hancock
James Hong
Nishith Khandwala
Kexin Rong

Event  Date  Description  Course Materials 

Lecture 1  6/26 
Algorithmic Analysis
Concepts: Techniques to analyze correctness and runtime Problems: Comparisonsorting Algorithms: Insertion sort Reading: CLRS 2.1, 2.2, 3 
[Slides]
[Slides (Condensed)] [Lecture Notes 12] 
Lecture 2  6/28 
Divide and Conquer
Concepts: Proving correctness and runtime, proving the Master Theorem Problems: Comparisonsorting Algorithms: Mergesort Reading: CLRS 2.3, 4.34.6 
[Slides]
[Slides (Condensed)] 
Tutorial 1  6/29  No Tutorial the first week  
Lecture 3  7/3 
Divide and Conquer
Concepts: More proving correctness and runtime Problems: Median finding Algorithms: Select Reading: CLRS 9 
[Slides]
[Slides (Condensed)] [Lecture Notes 3] 
HW 0 "Due"  7/3 
Homework #0 "due" at 5 p.m.
Review No submission is required; worth 0% of your grade 
[hw0.zip] Released on 6/25
Solutions [pdf, tex] released on 7/3 
Lecture 4  7/5 
Sorting Lower Bounds
Concepts: Comparisonbased sorting lower bounds Problems: O(n)sorting Algorithms: Counting sort, bucket sort, radix sort Reading: CLRS 8.18.2 
[Slides]
[Slides (Condensed)] [Lecture Notes 4] 
Tutorial 2  7/6 
Algorithmic Analysis, Divide and Conquer
3:304:50 p.m. in STLC 115 [RSVP here] 
[Tutorial 2] Released on 7/5
[Solutions] released on 7/6 
Lecture 5  7/10 
Randomized Algorithms
Concepts: Proving correctness and runtime for Las Vegas, recognizing and designing a randomized solution Problems: Comparisonsorting, median finding Algorithms: Bogosort, Quicksort, Randomized Quicksort, Quickselect, Lazy select Reading: CLRS 5, 7 
[Slides]
[Slides (Condensed)] [Lecture Notes 5] 
HW 1 Due  7/10 
Homework #1 due at 5 p.m.
Divide and Conquer 
[hw1.zip] Released on 7/2, Updated on 7/4
Solutions [pdf, tex] released on 7/12 at 5 p.m. 
Lecture 6  7/12 
Randomized Algorithms
Concepts: Directaddress tables, hash tables, hash functions, universal hash families, openaddressing Reading: CLRS 11 
[Slides]
[Slides (Condensed)] [Lecture Notes 6] 
Tutorial 3  7/13 
Randomized Algorithms
3:304:50 p.m. in STLC 115 [RSVP here] 
[Tutorial 3] Released on 7/12
[Solutions] released on 7/13 
Lecture 7  7/17 
Tree Algorithms
Concepts: Notational basics, binary search trees Algorithms: RedBlack Trees Reading: CLRS 12, 13 
[Slides]
[Lecture Notes 7] 
HW 2 Due  7/17 
Homework #2 due at 5 p.m.
Randomized Algorithms 
[hw2.zip] Released on 7/9, Updated on 7/15 (see Piazza @183 for details)
[Solutions] released on 7/19 at 5 p.m. 
Lecture 8  7/19 
Graph Algorithms
Concepts: Notational basics, proving correctness and/or runtime of graph algorithms Problems: Topological sorting, testing for bipartitness, finding strongly connected components Algorithms: BFS, DFS, Kosaraju's algorithm Reading: CLRS 22 
[Slides]
[Lecture Notes 8a] [Lecture Notes 8b] 
Tutorial 4  7/20 
Tree Algorithms, Graph Algorithms
3:304:50 p.m. in STLC 115 [RSVP here] 
[Tutorial 4] Released on 7/19
[Solutions] released on 7/20 
Lecture 9  7/24 
Graph Algorithms
Concepts: Recognizing and designing a graph solution Problems: Singlesource shortest path Algorithms: Dijkstra's, BellmanFord Reading: CLRS 24.124.3 
[Slides]
[Slides (Condensed)] [Lecture Notes 9] 
HW 3 Due  7/24 
Homework #3 due at 5 p.m.
Tree Algorithms, Graph Algorithms Since solutions must be released before the midterm, you cannot use late days for this assignment. 
[pdf, tex]Released on 7/16
[Solutions] released on 7/24 at 5 p.m. 
Lecture 10  7/26 
Dynamic Programming
Proving correctness and runtime of dynamic programming Problems: Allpairs shortest path, rodcutting Algorithms: FloydWarshall Reading: CLRS 25.2, 15.1 
[Slides]
[Lecture Notes 10] 
Midterm  7/26 
Midterm
6:308 p.m., Hewlett 200 Covers material up to and including 7/19 
[Practice Midterm] released on 7/21
[Solutions] released on 7/21 [Midterm Review Slides] [Midterm] released on 7/31 [Solutions] released on 7/31 
Tutorial 5  7/27  No Tutorial after Midterm  
Lecture 11  7/31 
Dynamic Programming
Concepts: Recognizing and designing a dynamic programming solution Problems: Longest common subsequence, Knapsack, independent sets Reading: CLRS 15.4 
[Slides]
[Lecture Notes 11] 
Lecture 12  8/2 
Greedy Algorithms
Concepts: Proving correctness and runtime, optimal substructure, minimumspanning trees Problems: Lilypads Algorithms: Kruskal's algorithm, Prim's algorithm Reading: CLRS 16.2, 23 
[Slides]
[Lecture Notes 12a] [Lecture Notes 12b] 
HW 4 Due  8/2 
Homework #4 due at 5 p.m.
Dynamic Programming 
[pdf, tex] Released on 7/26
[Solutions] released on 8/4 at 5 p.m. 
Tutorial 6  8/3 
Dynamic Programming, Greedy Algorithms
3:304:50 p.m. in STLC 115 [RSVP here] 
[Tutorial 6] Released on 8/2
[Solutions] released on 8/3 
Lecture 13  8/7 
Greedy Algorithms
Concepts: Recognizing and designing a greedy solution Problems: Activity selection Reading: CLRS 16.1, 16.3 
[Slides]
See Lecture 12 for notes 
Lecture 14  8/9 
Advanced Algorithms
Concepts: Approximation algorithms Problems: Vertexcovering, travelingsalesman, setcovering Reading: CLRS 35.135.3 
[Slides]
No Lecture Notes 
HW 5 Due  8/10 
Homework #5 due at 5 p.m.
Greedy Algorithms 
[pdf, tex] Released on 8/2
[Solutions] released on 8/12 at 5 p.m. 
Tutorial 7  8/10 
Advanced Algorithms
3:304:50 p.m. in STLC 115 
[Tutorial 7] Released on 8/10
[Solutions] released on 8/12 
Lecture 15  8/14 
Advanced Algorithms
Concepts: Mincut, Maxflow Algorithms: Karger's algorithm, FordFulkerson Reading: CLRS 26.126.3 
[Slides]
[Lecture Notes 15] 
Lecture 16  8/16  Final Review  [Slides] 
Final  8/17 
Final
8:3011:30 a.m., Bishop Auditorium Covers all material 
[Practice Final] released on 8/12
[Solutions] released on 8/12 [Final] released on 8/20 [Solutions] released on 8/20 