# CS 514-001, Algorithms: Design, Analysis, and Implementation, Fall 2022

### 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, recursion tree method, amortization, etc.)
3. Dynamic Programming (DP)
4. Graph Algorithms: BFS/DFS, topological sort, Dijkstra, Viterbi, Prim, Kruskal, TSP
5. NP-Completeness

### Detailed Schedule and Materials

 Week Topics/Readings Homework Quiz/Exam 19/22 (Thu) Admin Python Tutorial (first 5 pages required, others recommended) quicksort, BST, quickselect HW1 (qselect, qsort->bst) 29/27,29 (Tue) brief discussions of HW1 divide-n-conquer: quicksort vs. mergesort vs. quickselect vs. binary search master equation merging two sorted lists via two-pointers multitasking recursion: # of inversions and longest path in binary tree stable sort; motivations: sorting with multiple keys mergesort and non-randomized quicksort are stable, but randomized quicksort is not (Thu) selection sort: $$O(n^2)$$; not stable, but can be made stable insertion sort: $$O(n^2)$$. stable. insertion sort with binary search: still $$O(n^2)$$; bisect.bisect insertion sort with balanced BST: $$O(n\log n)$$ why (internal) sorting can't be faster than $$O(n \log n)$$? $$O(\log n^n) = O(n\log n)$$ k numbers closest to input query, unsorted k numbers closest to input query, sorted; quiz1 HW2(msort, inv, longest) Thu: Quiz 1(covers HW1) 310/4,6 (Tue) brief discussion on Quiz1 (10 min). brief discussion on HW2 (10 min). mergesort implementation: mergesorted(a[1:], b) is $$O(n^2)$$ Priority Queue (emergency room) slow implementations: sorted list, reversely sorted list, sorted linkedlist fast implementation: binary heap complete binary tree (also balanced); array representation. heap: bubble-up and bubble-down. hand out graded quiz1 (Thu) mistake in Quiz1 heap: decreaseKey operation heapify: divide-n-conquer vs. iterative heapify is $$O(n)$$ [see here; also CLRS Appendix A (integrating and differentiating series)]) Python heapq tutorial k-way mergesort: $$T(n) = k T(n/k) + O(n\log k) = O(n\log n)$$ regardless of $$k$$ HW3(k-closest, two pointers) 410/11,13 (Tue) brief discussions of HW3 x+y=query: $$O(n^2) \Rightarrow O(n\log n)$$ x+y=z: $$O(n^3) \Rightarrow O(n^2 \log n) \Rightarrow O(n^2)$$ heapq bubble-down follows Knuth (vol.3) and different from textbooks (Thu) k-best from cross-product (baby Dijkstra). data stream quiz2 and discussions HW4(priority queues; baby Dijkstra) Thu: Quiz 2(covers HWs1-3/quiz1) 510/18,20 (Tue) discussions of HW4 DP 101: Fibonacci, memoization, bitstrings, max. indep. set [slides] handout graded Quiz2 (Thu) DP: backtracing the optimal solution DP: LIS DP: unbounded knapsack HW5(DP I: memoized Fibonacci, # of BSTs, # of bistrings) 610/25,27 (Tue) DP: 0-1 and bounded knapsack KT slides (pp. 30-37) (Thu) Discussions for HW5 Midterm Review problems [solutions] HW6(DP II: knapsack, unbounded and bounded) 711/1,3 (Tue) Discussions of HW6 Q/A session (Thu) Midterm Thu: Midterm 811/8,10 (Tue) Discussions of Midterm solutions graphs: intro topological sort (BFS-style) handout graded midterms (Thu) in-class coding session: topol sort: stack and queue Viterbi Dijkstra intro HW8(Topol, Viterbi) 911/15,17 (Tue) Dijkstra: decrease-key; hashed heap (heapdict) KT slides demo HW8 solutions (Thu) CKY: RNA structure KT slides HW9(Dijkstra; TSP) 1011/22,24 (Tue) counting and k-best RNA (Thu) Thanksgiving HW10 (RNA structure) 1111/29;12/1 (Tue) hypergraphs and generalized Viterbi k-best Viterbi k-best generalized Viterbi (RNA) DP summary slides (Thu) Final review problems and solutions optional HW11 (edit distance, just for practice) 12 FINAL EXAM Thu 12/8 9:30am-11:20amsame room, closed book, closed notes

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

Liang Huang