101S17day27b

Date Lecture Title Links HW
Week 1
Mon 4/3  1(RI)  Intro/Time Analysis (0)  101S17day1
Tue 4/4  1(MJ)  Intro/Time Analysis (0)  day1(A00)
Wed 4/5 2(RI)  Time analysis/Graph Search (0, 3.1)  101S17day2
Thu 4/6  2(MJ)  Time analysis/Graph Search day2_annotated
Fri 4/7 3(RI)  Graph search, reductions (3.2)(4.1,4.2)  101S17day3ri
Week 2
Mon 4/10  4(RI)  DFS/DAGs (3.3-3.4) day4/annot
Tue 4/11  3(MJ)  DFS/DAG  day3/annot
Wed 4/12 5(RI)  SCC  day5/annot HW1
Thu 4/13  4(MJ)  SCC/BFS  day4/annot
Fri 4/14 6(RI)  Dijkstra’s/Data Structures day6
Week 3
Mon 4/17  7(RI)  Dijkstra’s(4.1-4.5)  101S17day7ri (1)
Tue 4/18  5(MJ)  Dijkstra’s  day5(mj)/annot
Wed 4/19 8(RI)  Why being greedy is dangerous  101S17day8B  HW2
Thu 4/20  6(MJ)  Greedy  day6(MJ)/C00
Fri 4/21 9(RI)  Greedy correctness  proofs templates  101Sp17day9B
Week 4
Mon 4/24  10(RI)  Achieves-the-bound proofs, Minimum spanning tree  101sp17day10ri
Tue 4/25  7(MJ)  Greedy/MST  day7(MJ)/annot  HW3
Wed 4/26 11(RI)  First Midterm (up to end of week 2)
Thu 4/27  8(MJ)  First Midterm (up to end of week 2)
Fri 4/28 12(RI) MST (chapter 5.1): Using Disjoint sets data structure to implement Kruskal’s algorithm  101sp17day12ri
Week 5
Mon 5/1  13(RI)  Disjoint sets data structures 101sp17day13ri
Tue 5/2  8(MJ)  Greedy/MST  day8(MJ)/annot
Wed 5/3 14(RI) Approximation algorithms  101S17day14
Thu 5/4  9(MJ)  UnionRank/Approximate Greedy  day9(MJ)/annot  HW4
Fri 5/5 15(RI) Divide and Conquer (Ch. 2): Master  Theorem, Karatsuba algorithm  101s17day15
Week 6
Mon 5/8  16(RI) Divide and conquer (Ch. 2):  101sp17day16ri
Tue 5/9  10(MJ)  day10(MJ)/annotated
Wed 5/10 17(RI)  Divide and conquer (Ch. 2):Cook-Toom algorithm  101s17day17
Thu 5/11  11(MJ)  day11(MJ)/annotated
Fri 5/12 18(RI)  D/C :FFT  101s17day18ri
Week 7
Mon 5/15  19(RI) Selection, Quicksort 101s17day19
Tue 5/16  12(MJ)  day12(MJ)/annotated
Wed 5/17 20(RI)  Backtracking  101s17day20ri  HW5
Thu 5/18  13(MJ)  day13(MJ)/annotated
Fri 5/19 21(RI) Backtracking  101S17day21b
Week 8
Mon 5/22  22(RI)  Dynamic programming  101S17day22b
Tue 5/23  14(MJ)  day14(MJ)/annotated
Wed 5/24 23(RI)  2nd Midterm (greedy, d&c)
Thu 5/25  2nd Midterm (greedy, d&c)
Fri 5/26 24(RI)  Dynamic programming  101S17day24d
Week 9
Mon 5/29  ****Memorial Day****
Tue 5/30  15(MJ)  101S17day15(MJ)annotated
Wed 5/31 25(RI)  Dynamic programming: shortest paths  101S17day25b  hw6
Thu 6/1  16(MJ)  101S17day16(MJ)/annotated
Fri 6/2 26(RI)  DP: genomics  101S17day27b
Week 10
Mon 6/5  27(RI)  Network flow and reductions  101sp17day28b
Tue 6/6  17(MJ)  day17(MJ)/annotated
Wed 6/7 28(RI)  Reductions and NP completeness  101S17day29b
Thu 6/8  18(MJ)  101S17day18(MJ)/annotated  HW7
Fri 6/9 29(RI)  Review  101S17day30b
Finals
Final