CS 161

Design and Analysis of Algorithms

Summer 2018

Instructor

david
David Eng

Teaching Assistants

edward
Edward Gan
braden
Braden Hancock
james
James Hong
edward
Nishith Khandwala
kexin
Kexin Rong

Schedule

Event Date Description Course Materials
Lecture 1 6/26 Algorithmic Analysis
Concepts: Techniques to analyze correctness and runtime
Problems: Comparison-sorting
Algorithms: Insertion sort
Reading: CLRS 2.1, 2.2, 3
[Slides]
[Slides (Condensed)]
[Lecture Notes 1-2]
Lecture 2 6/28 Divide and Conquer
Concepts: Proving correctness and runtime, proving the Master Theorem
Problems: Comparison-sorting
Algorithms: Mergesort
Reading: CLRS 2.3, 4.3-4.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: Comparison-based sorting lower bounds
Problems: O(n)-sorting
Algorithms: Counting sort, bucket sort, radix sort
Reading: CLRS 8.1-8.2
[Slides]
[Slides (Condensed)]
[Lecture Notes 4]
Tutorial 2 7/6 Algorithmic Analysis, Divide and Conquer
3:30-4: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: Comparison-sorting, 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: Direct-address tables, hash tables, hash functions, universal hash families, open-addressing
Reading: CLRS 11
[Slides]
[Slides (Condensed)]
[Lecture Notes 6]
Tutorial 3 7/13 Randomized Algorithms
3:30-4: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: Red-Black 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:30-4: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: Single-source shortest path
Algorithms: Dijkstra's, Bellman-Ford
Reading: CLRS 24.1-24.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: All-pairs shortest path, rod-cutting
Algorithms: Floyd-Warshall
Reading: CLRS 25.2, 15.1
[Slides]
[Lecture Notes 10]
Midterm 7/26 Midterm
6:30-8 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, minimum-spanning 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:30-4: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: Vertex-covering, traveling-salesman, set-covering
Reading: CLRS 35.1-35.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:30-4:50 p.m. in STLC 115
[Tutorial 7] Released on 8/10
[Solutions] released on 8/12
Lecture 15 8/14 Advanced Algorithms
Concepts: Min-cut, Max-flow
Algorithms: Karger's algorithm, Ford-Fulkerson
Reading: CLRS 26.1-26.3
[Slides]
[Lecture Notes 15]
Lecture 16 8/16 Final Review [Slides]
Final 8/17 Final
8:30-11: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

Office Hours