|Coordinates||TR, 10-11:20am, GLSN 200 [Registrar] [Canvas]|
|TAs||He Zhang (zhangh7@) and Yilin Yang (yangyil@)|
|Office hours||Liang: T/Th, 11:25-11:55am (KEC 2069); TAs: M/T/Th/F, 4-5pm (KEC Atrium).|
|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%, three quizzes: 7x3=21%;
weekly homework: 3x10=30%, class participation: 4%.
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.
Grading Curve: A/A-: 40-45%, B+/B/B-: 45-50%, the rest is C+/C/C- (very rare).
For technical questions, come to office hours.
Otherwise you can raise a question on Canvas.|
(answering other people's questions correctly will be rewarded for class participation).
For grading questions, come to office hours. Do not email us unless you have a personal issue.
Python Tutorial (first 5 pages)
quicksort, BST, quickselect
(Thu) mergesort, two-pointers, stable sort
divide-n-conquer: number of inversions|
longest path in binary tree
brief discussions of HW1
(Thu) k numbers closest to input query, unsorted
quiz1 and discussions
(msort, inv, longest)
|Thu: Quiz 1|
hand out graded quiz1|
insertion sort can be made O(nlogn) by balanced BST
discussions of HW2:
qsort with randomized pivot 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) is O(n^2)
k numbers closest to input query, unsorted
(Thu) Priority Queue; heap; bubble-up/bubble-down
(k-closest, two pointers)
brief discussions of HW3|
heapify is O(n)
Python heapq tutorial
heapq bubble-down follows Knuth (vol.3) and different from textbooks
(Thu) quiz2 and discussions
(priority queues; baby Dijkstra)
|Thu: Quiz 2|
||(Tue) handout Quiz2|
DP 101: Fibonacci, memoization, bitstrings, max. indep. set [slides]
(Thu) discussions of HW4
(DP I: memoized Fibonacci, # of BSTs, # of bistrings)
||(Tue) Knapsack: unbounded and 0-1|
(Thu) Knapsack: bounded
Discussions for HW5
(DP II: knapsack, unbounded and bounded)
||(Tue) Midterm Review Solutions|
Discussions of HW6
||(Tue) Discussions of Midterm solutions|
topological sort (BFS-style)
sparse and dense graphs
(Thu) Viterbi; Dijkstra
(DP III: LIS, Topol, Viterbi)
||(Tue) Discussions of HW9; TSP (Edmonds-Karp)|
(Thu) TSP cont'd.; CKY: RNA structure
||(Tue) Discussions of HW9|
counting RNA structures; k-best RNA structure
(Thu) review problems
|HW10: Challenge (RNA structure)
||FINAL Thu 3/22 6pm|
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 complexity analysis).