# 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 (Wed) Admin Python Tutorial quicksort, BST (Fri) quickselect, mergesort, two-pointers, stable sort HW1 (qselect, qsort->bst) 2 (Mon) 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 x+y=z HW2(msort, inv, longest) Fri: Quiz 1(covers HW1) 3 (Mon) 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 x+y=z (Fri) Priority Queue; heap; bubble-up/bubble-down HW3(k-closest, two pointers) 4 (Mon) 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 k-way mergesort data stream (Fri) quiz2 and discussions HW4(priority queues; baby Dijkstra) Fri: Quiz 2(covers HWs1-3/quiz1) 5 (Mon) Discussions of HW4 and Quiz2 (Wed) DP 101: Fibonacci and memoization (Fri) Maximum Independent Set memoization wrapper `cache=None` instead of `cache={}` HW5(DP I: memoized Fibonacci, # of BSTs, # of bistrings) 6 (Mon) Help with HW5: backtracing, bitstrings, and BSTs `ipython %memit` (`sudo pip install memory_profiler; %load_ext memory_profiler`) (Wed) Discussions of HW5Knapsack: unbounded (Fri) Knapsack: 0-1 HW6(DP II: knapsack, unbounded and bounded) 7 (Mon) Discussions of HW6 `defaultdict` (Wed) Review Problems Solutions (Fri) Midterm (no HW; review problems I) Office Hours W/Th 4-6pm in KEC 2057 Midterm 11/4(covers HWs1-6) 8 (Mon) Discussions of Midterm solutions (Wed) LIS, TSP (Fri) Veteran's Day 11/11; NO CLASS HW8(DP III: LIS, TSP) 9 (Mon) TSP; sparse vs. dense graphs (Wed) BFS topolsort; Viterbi (Fri) Discussions of HW8DFS topolsort; Dijkstra HW9(BFS-Topol/Viterbi/Dijkstra) 10 (Mon) CKY: RNA structure (Wed) Discussions of HW9; k-best RNA structure (Fri) THANKSGIVING Challenge problem (RNA structure) 11 (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:50pmsame room

Summary: what I learned from you, and what you should have learned from me.

### Resources

• codeforces (recommended: each problem has annotated tags such as "dp", "dfs", etc.)
• 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 details on analysis of complexity).

Liang Huang