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

Coordinates T/Th, 10-11:20am, KEC 1001 [Registrar] [Canvas] [Teams]
Instructor Liang Huang (huanlian@)
TA Sizhen Li (lisiz@)
Office Hours Instructor: T/Th, 11:25am-11:50am (KEC 2069)
TA: M/F 4-5pm (KEC Atrium).
Extra office hours available before exams.
Textbooks [CLRS] Introduction to Algorithms, 4th/3rd/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: 25%; Final: 25%; Quizzes: 8+10=18%; homework: 3x8%+6%=30%. background survey: 2%.
For each HW, any complete submission automatically gets 2%.
The other 1% is based on blackbox testing of the specified coding problem.
Coding must be done in Python 3.
Just finishing the background survey in week1 will get the 2%. no late submission is accepted.

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.
Zoom/Recording Each lecture is recorded and will be uploaded to Canvas the next day. But we do not offer live zoom unless it's a COVID or travel situation. Email the TA for zoom link requests.
Other Policies Canvas is for announcements (you'll receive an email for each announcement I made on Canvas) and checking grades, and Teams is for discussions (we used to use Slack, but the University dropped Slack support).

For technical questions, come to office hours. Otherwise you can raise a question on Teams.
For questions about grading or grades, come to the office hours. Do not email us unless you have a personal issue.

Objectives

The purpose of this course is six-fold:

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

WeekTopics/ReadingsHomeworkQuiz/Exam
1
9/22 		(Thu) Admin
Python Tutorial (first 5 pages required, others recommended)
quicksort, BST, quickselect
HW1
(qselect, qsort->bst)
2
9/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)
3
10/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)
4
10/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)
5
10/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)
6
10/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)
7
11/1,3 		(Tue) Discussions of HW6
Q/A session
(Thu) Midterm 		Thu: Midterm
8
11/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)
9
11/15,17 		(Tue) Dijkstra: decrease-key; hashed heap (heapdict)
KT slides demo
HW8 solutions
(Thu) CKY: RNA structure
KT slides 		HW9
(Dijkstra; TSP)
10
11/22,24 		(Tue) counting and k-best RNA
(Thu) Thanksgiving 		HW10 (RNA structure)
11
11/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:20am
same room, closed book, closed notes

Resources

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