Coordinates  T/Th, 1011:20am, LINC 210 [Registrar] [Canvas] [Slack] 
Instructor 
Liang Huang (huanlian@)

TAs  Sizhen Li (lisiz@), Liang Zhang (zhanglia@), and Renjie Zheng (zhengr@) 
Office Hours  Instructor: T/Th, 11:30am12pm (KEC 2069) TAs: M: 34pm and 56pm; W: 46pm; F: 46pm (KEC Atrium). Extra office hours available before exams. 
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%, Quizzes: 8+8=16%; Weekly homework: 3x8%+6%=30%, Class Participation: 2%. For each HW, any complete submission automatically gets 2%. The other 1% is based on blackbox testing of the specified coding problem. Remaining 7%: everybody gets full marks. Coding must be done in Python 3. no late submission is accepted.
Class participation: we reward the following: Grading Curve: A/A: [90,100]; B+/B/B: [60,90); C: [50,60); F: [0,50). 
Prerequisites  Students are assumed to be familiar with Data Structures (CS 261) and fluent in at least one mainstream language (C/C++, Java, Python). We'll start with a brief review of Data Structures integrated with a Python tutorial. 
Other Policies 
Canvas is for announcements (you'll receive an email for each announcement I made on Canvas)
and checking grades,
and Slack is for discussions.
For technical questions, come to office hours.
Otherwise you can raise a question on Slack. 
Week  Topics  Homework  Quiz/Exam 
1  (Thu) Admin Python Tutorial (first 5 pages) quicksort, BST, quickselect  HW1 (qselect, qsort>bst)  
2  (Tue)
brief discussions of HW1 tail recursion; nonrecursive qselect dividenconquer: quicksort vs. mergesort merging two sorted lists via twopointers stable sort; motivations: sorting with multiple keys stable: mergesort, insertion sort, nonrandomized quicksort not stable: randomized quicksort, selection sort (but can be made stable) insertion/selection sort are "slow": O(n^2) insertion sort with binary search: n x (O(logn) + O(n)) = O(n^2) still
(Thu)
dividenconquer: number of inversions  HW2 (msort, inv, longest)  Thu: Quiz 1 (covers HW1) 
3  (Tue)
hand out graded quiz1 insertion sort can be made O(nlogn) by balanced BST discussions of HW2: qsort with randomized pivot made stable by 3way partition generic way to stablize sort: decoratesortundecorate mergesort implementation: mergesorted(a[1:], b) is O(n^2) k numbers closest to input query, sorted (Thu) k numbers closest to input query, unsorted; bisect.bisect x+y=query: O(n^2)>O(nlogn) x+y=z: O(n^3)>O(n^2 logn) > O(n^2) x+y=z: hashing (python set): O(n^2) Priority Queue (emergency room) slow implementations: sorted list, reversely sorted list, sorted linkedlist fast implementation: binary heap; bubbleup/bubbledown  HW3 (kclosest, two pointers)  
4  (Tue)
brief discussions of HW3 heapify is O(n) Python heapq tutorial heapq bubbledown follows Knuth (vol.3) and different from textbooks kway mergesort (Thu) data stream quiz2 and discussions  HW4 (priority queues; baby Dijkstra)  Thu: Quiz 2 (covers HWs13/quiz1) 
5  (Tue) handout Quiz2 discussions of HW4 heapify is O(n) (Thu) DP 101: Fibonacci, memoization, bitstrings, max. indep. set [slides]  HW5 (DP I: memoized Fibonacci, # of BSTs, # of bistrings)  
6  (Tue) Knapsack: unbounded and 01 KT slides (pp. 3037) (Thu) Knapsack: bounded Discussions for HW5 Midterm Review problems [solutions]  HW6 (DP II: knapsack, unbounded and bounded)  
7  (Tue) Discussions of HW6 Q/A session (Thu) Midterm  Thu: Midterm  
8  (Tue) Discussions of Midterm solutions graphs: intro topological sort (BFSstyle) handout graded midterms (Thu) inclass coding session: topol sort: stack and queue Viterbi Dijkstra intro  HW8 (Topol, Viterbi)  
9  (Tue) Dijkstra: decreasekey; hashed heap (heapdict) KT slides demo HW8 solutions (Thu) CKY: RNA structure KT slides  HW9 (Dijkstra; redo one midterm question)  
10  (Tue) counting and kbest RNA (Thu) Thanksgiving  HW10 (RNA structure)  
11  (Tue)
inclass coding session: kbest RNA (Thu) Review problems updated solutions  optional hw11 (editdistance)  
12 
FINAL Fri 12/13 9:30am11:20am same room, closed book, closed notes 
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).