# CS 325-001, Analysis of Algorithms, Spring 2023

### 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 Homework Quiz/Exam 1 (Tue) Admin Python Tutorial (first 5 pages) quicksort analyses: best-case $$O(n \log n)$$; worst-case $$O(n^2)$$ divide-conquer-combine array concatenation is $$O(n)$$ (Thu) quicksort <-> BST (buggy qsort) mergesort; two-pointers number of inversions using mergesort; recursion with byproduct HW1 (msort, inversions, qsort->bst) 2 (Tue) discussions of HW1 quickselect hints on Quiz 1 (Thu) longest path in binary tree [video 1] [video 2] quiz 1 HW2(qselect, longest) Thu: Quiz 1(covers HW1) 3 (Tue) hand out graded quiz1 discussions of HW2 $$k$$ numbers closest to input query, sorted; Python bisect.bisect $$k$$ numbers closest to input query, unsorted; (Thu) x+y=query: $$O(n^2)$$->$$O(n \log n)$$ x+y=z: $$O(n^3)$$->$$O(n^2 \log n)$$ -> $$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; bubble-up/bubble-down HW3(k-closest, two pointers, kmergesort) 4 priority queue, lowerbound, datastream slides for nbest HW4(priority queue) Thu: Quiz 2 5 dynamic programming (DP): basics [slides] HW5(DP: part 1) 6 dynamic programming (DP): advanced HW6(DP: part 2) 7 midterm review problems [solutions] no HW7 Thu: Midterm 8-9 graph algorithms and their connections to DP; Topological sort Viterbi algorithm Dijkstra algorithm HW8-HW9(graphs) 10 challenge problem and final review full DP slides (pages 11-17) Final Review Questions and Solutions HW10(RNA: connecting all topics) 11 FINAL Wed 6/14 2-4pm same room, closed book, closed notes optional HW11 due Fri 6/16(edit-distance)

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