CS 325-001, Analysis of Algorithms, Spring 2023

Coordinates T/Th, 10-11:20am, LINC 302 [Registrar] [Canvas] [Slack]
Instructor Liang Huang (huanlian@)
TAs Tianshuo Zhou (zhoutian@), Apoorv Malik (malikap@)
Office Hours Instructor: T/Th, 11:30-11:50am (KEC 2069)
TAs: M 4-5pm & 5:30-6:30pm; W 5:30-6:30pm; F 4-5pm & 5:30-6:30pm (KEC Atrium).
Extra office hours available before exams.
Textbooks [CLRS] Introduction to Algorithms, 3rd or 2nd edi. (default reference).
[KT] Kleinberg and Tardos, Algorithm Design (DP chapter online, all slides online)
[R] Roughgarden, Algorithms Illuminated (videos and 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 (Thu, week 7): 25%+4%, Final: 25%+5%, Quizzes (Thu, weeks 2 & 4): 8+2+8+3=16%+5%; background survey: 2%.
picking up graded papers: 1%; post-midterm survey: 3%. optional HW11: +3%.
Weekly homework (1-6, 8-10): 3x8%+4%+2%=28%+2%.
Total extra credit: 19%.
For HW1-9, 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.
no late submission is accepted.

Grading Curve: (>90 OR top 25%): A/A-; (<70 AND bottom 25%): C+ or lower; others: B+/B/B-. (i.e., at least 1/4 will get A/A- and at most 1/4 will get C+ or lower).

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.
Other Policies Canvas is for announcements (you'll receive an email for each announcement I made on Canvas) and checking grades, and Slack is for discussions.

For technical questions, come to office hours. Otherwise you can raise a question on Slack.
For questions about grading or grades, come to the office hours. Do not email us unless you have a personal issue, in which case please email all three of us.

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

WeekTopicsHomeworkQuiz/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

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