cs161-sum18

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

CS 161

Design and Analysis of Algorithms

Summer 2018

Instructor

Teaching Assistants

Schedule

Office Hours