# CS 519-010, Algorithms (MS/MEng-Level), Winter 2018

### Objectives

The purpose of this course is six-fold:
• to teach you the most important algorithms and their implementations in Python
• to equip you with basic algorithm analysis skills (such as time complexity)
• to prepare you for industrial interviews with top firms (Google, Facebook, Microsoft, Amazon, etc)
• to convert you from a conventional C++/Java programmer to an elegant Pythonic programmer
• to prepare you for ACM International Collegiate Programming Contests (ICPC)
• to train you to think like a computer scientist: think recursively, abstractly, and rigorously.

### Topics Covered

1. Python Tutorial, Review of Basic Data Structures, Sorting and Selection
(divide-n-conquer, quicksort/quickselect, mergesort, BSTs, memoization, heaps and heapsort, priority queue, hashing, hashed heap, etc.)
2. Basic Complexity Analysis (Master equation, tree method, amortization, etc.)
3. Dynamic Programming (DP)
4. Graph Algorithms: BFS/DFS, topolsort, Dijkstra, Prim, Kruskal

### Detailed Schedule and Materials

 Week Topics Homework Quiz/Exam 1 (Tue) Admin Python Tutorial quicksort, BST, quickselect (Thu) mergesort, two-pointers, stable sort HW1 (qselect, qsort->bst) 2 (Tue) 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 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 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 x+y=z (Thu) Priority Queue; heap; bubble-up/bubble-down HW3(k-closest, two pointers) 4 (Tue) brief discussions of HW3 heapify is O(n) Python heapq tutorial heapq bubble-down follows Knuth (vol.3) and different from textbooks k-way mergesort data stream (Thu) quiz2 and discussions HW4(priority queues; baby Dijkstra) Thu: Quiz 2(covers HWs1-3/quiz1) 5 (Tue) handout Quiz2 DP 101: Fibonacci, memoization, bitstrings, max. indep. set [slides] (Thu) discussions of HW4 `cache=None` instead of `cache={}` HW5(DP I: memoized Fibonacci, # of BSTs, # of bistrings) 6 (Tue) Knapsack: unbounded and 0-1 (Thu) Knapsack: bounded Discussions for HW5 HW6(DP II: knapsack, unbounded and bounded) 7 (Tue) Midterm Review Solutions Discussions of HW6 (Thu) Midterm 8 (Tue) Discussions of Midterm solutions topological sort (BFS-style) sparse and dense graphs (Thu) Viterbi; Dijkstra HW8(DP III: LIS, Topol, Viterbi) 9 (Tue) Discussions of HW9; TSP (Edmonds-Karp) (Thu) TSP cont'd.; CKY: RNA structure HW9(Dijkstra, TSP) 10 (Tue) Discussions of HW9counting RNA structures; k-best RNA structure (Thu) review problems HW10: Challenge (RNA structure) 11 FINAL Thu 3/22 6pmsame room

### Resources

• leetcode oj (recommended: you can practice "writing on the whiteboard" there)
• zoj (Zhejiang University)
• timus
• project euler (math)
• rosalind (bioinfo)
The last two are different from the rest in the sense that they ask you to submit your output to given testcases rather than programs (so that you can code in any language, and their online judge system is as easy as a diff). There are many other online judge systems that do not support Python (traditionally ACM/ICPC uses C/C++/Java/Pascal), such as the classical uva (Universidad de Valladolid), poj (Peking University), tju, hit, hust, bjtu, etc. (almost all major Chinese universities run their own online judge systems); you can hone your C/C++/Java skills there if you have extra time. Thanks to my former intern Zhuoran Yu for compiling this list.

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).

Liang Huang