|Coordinates||MWF, 10-10:50am, GLSN 200 [Registrar] [Canvas]|
Mingbo Ma (lead)
|Office hours||W/Th 5-6pm, KEC 2048 (Mingbo, grading questions welcome).|
Th 9:10-10am, KEC 2069 (Liang, grading questions welcome).
F 5-6pm, KEC 2048 (Dezhong, no grading questions allowed).
|Textbooks||[CLRS] Introduction to Algorithms, 3rd or 2nd edi. (default reference).
[KT] Kleinberg and Tardos, Algorithm Design (DP chapter online, all slides online)
[DPV] Dasgupta, Papadimitriou, and Vazirani (DPV). Algorithms (full text online via berkeley)
[E] Jeff Erickson. Algorithms, Etc. (full text online)
How to Think Like a Computer Scientist: Learning Python (full text online)
|Grading (tentative)||midterm: 20%, final: 25%, four quizzes: 5x4=20%;
weekly homework: 3x10=30%, class participation: 5%.
any complete HW submission automatically gets 2%.
the other 1% is based on blackbox testing of the specified coding problem.
no late submission is accepted.
For questions, come to the office hours.
If you are unable to come, you can raise a question on Canvas.|
If you have a personal (non-grading) question, send it here which will reach the instructor and all TAs.
Do not email us individually. For grading questions, please come to W/Th office hours.
(Fri) quickselect, mergesort, two-pointers, stable sort
divide-n-conquer: number of inversions|
longest path in binary tree
(Wed) brief discussions of HW1
k numbers closest to input query, unsorted and sorted
(Fri) quiz1 and discussions
(msort, inv, longest)
|Fri: Quiz 1|
hand out graded quiz1|
insertion sort can be made O(nlogn) by balanced BST
discussions of HW2:
qsort with randomized pivot can be made stable by 3-way partition
selection sort (in-place) is not stable
generic way to stablize sort: decorate-sort-undecorate
mergesort implementation: mergesorted(a[1:], b) makes it O(n^2)
(this "beautiful" style only works for linkedlist or functional languages)
(Wed) cont'd discussions of HW2
Python lazylists (yield)
longest path implementation
(Fri) Priority Queue; heap; bubble-up/bubble-down
(k-closest, two pointers)
heapify is O(n)|
Python heapq tutorial
empirical difference b/w heapify and n heappushes
(sorted array is best-case (where heapify is slower);
reverse-sorted is worst-case; use random list for avg-case)
heapq bubble-down follows Knuth (vol.3) and different from textbooks
(Wed) brief discussions of HW3
(Fri) quiz2 and discussions
(priority queues; baby Dijkstra)
|Fri: Quiz 2|
||(Mon) Discussions of HW4 and Quiz2|
(Wed) DP 101: Fibonacci and memoization
(Fri) Maximum Independent Set
(DP I: memoized Fibonacci, # of BSTs, # of bistrings)
||(Mon) Help with HW5: backtracing, bitstrings, and BSTs|
(Wed) Discussions of HW5
(Fri) Knapsack: 0-1
(DP II: knapsack, unbounded and bounded)
||(Mon) Discussions of HW6|
(Wed) Review Problems Solutions
|(no HW; review problems I)|
Office Hours W/Th 4-6pm in KEC 2057
||(Mon) Discussions of Midterm solutions|
(Wed) LIS, TSP
(Fri) Veteran's Day 11/11; NO CLASS
(DP III: LIS, TSP)
||(Mon) TSP; sparse vs. dense graphs|
(Wed) BFS topolsort; Viterbi
(Fri) Discussions of HW8
DFS topolsort; Dijkstra
||(Mon) CKY: RNA structure|
(Wed) Discussions of HW9; k-best RNA structure
|Challenge problem (RNA structure)
||(Mon) Hints on RNA structures: total and kbest|
(Challenge problem due Tue)
(Wed) Discussions of Challenge problem
(Fri) Final Review Problems
|(no HW; review problems II)
||FINAL M 12/5 12pm-1:50pm|
To prepare for coding interviews, you have to practice on some of the above (say, solving at least 20 problems on codeforces, with at least two from each topic). To prepare for ACM/ICPC, you have to practice a lot (solving at least 100 problems on zoj/poj).
For another MS/MEng-level algorithms class I taught before (at USC), see here (with lots of details on analysis of complexity).