CS 3813/780, Advanced Programming, Fall 2014

Time and Location MW, 9:15 -- 10:30 am, SB A135B
Instructor Prof. Liang Huang (huang at cs)
Teaching Assistants Dr. Feifei Zhai (ffzhai2012 at gmail) and Lei Jiang (jlwatereast at gmail)
Course Admin Ms. Xiuyi Huang (xiuyi@cs)
Course Homepage http://acl.cs.qc.edu/~lhuang/teaching/advprg/
Textbooks [CLRS] Introduction to Algorithms, 3rd or 2nd edi. (default reference).
[KT] Kleinberg and Tardos, Algorithm Design (also recommended)
How to Think Like a Computer Scientist: Learning Python (also recommended)
Grading weekly homework: 30%, quizzes: 10+15=25%, final project: 20%.
in-class miniquizzes: 15%. class participation: 10%.
homework policy: HW is graded only by completeness, not by correctness. Therefore, no late HW is accepted.


The purpose of this course is five-fold, with the first three being more important: We assume you have already taken both Datastructures and Algorithms, though the latter can be taken in parallel with this course upon instructor approval. The focus of this course is not on theoretical aspects such as complexities and proofs, but a solid understanding of theory is assumed, though we'll review them along the way.

Topics Covered and High-Level Schedule

  1. Python Tutorial, Review of Basic Data Structures and Sorting
  2. Dynamic Programming
  3. Graph Algorithms: Dijkstra, Prim, Kruskal


HW0 and HW1 will be trivial (to get you familiarized with Python while reviewing datastructures). HW2 will be more interesting, and HW3-5 will be challenging, with the use of those Online Judge Systems supporting Python, such as: 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 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 an algorithms class I taught before (at USC), see here (lots of details on analysis of complexity).

Have fun in lectures and HWs!

Detailed Schedule and Materials

WeekDateTopics and Readings (CLRS and KT)
1 W 9/3
  • Administrativia
  • Brief Review: topological sort, priority queue, Dijkstra
  • Python Intro
  • slides for Section 1 (weeks 1-3)
  • HW0 out on W 9/3, due Su 9/7: dollar words
2 M 9/8
  • HW0 discussions; Pythonic style (sum/max: list comprehension)
  • Python Tutorial: quicksort
2 W 9/10
  • More on Python Tutorial
  • quicksort vs. binary search tree; inorder/insertion/deletion on BST
3 M 9/15
  • More on Python Tutorial
  • quickselect (CLRS 9.2, KT 13.5)
  • HW1 out
4 M 9/22
  • Discussions of HW1 solutions
  • Quiz 1
5 M 9/29
  • Discussions of Quiz 1: qselect on BSTs; best-case: O(1), worst-case: O(n)
  • lowest common ancestor
  • HW2 out
5 W 10/1
  • lowest common ancestor (cont'd)
  • top k numbers closest to a query x (unsorted and sorted)
  • triples x+y=z (hash and sweeping; O(n^2))
6 M 10/6
  • lowest common ancestor: feifei's nicer solution and liang's further embellishment
  • top k numbers closest to a query x (unsorted and sorted)
6 W 10/8
  • triples x+y=z (hash and sweeping; O(n^2))
  • heap: push (bubble-up) and pop (bubble-down): O(logn)
  • heapify: n bubble-ups: O(nlogn)
  • heapify: n bubble-downs: O(n)
    1/2 + 2/4 + 3/8 + ... = (1/2 + 1/4 + 1/8 + ...) + (0 + 1/4 + 2/8 + 3/16 + ...)
    = 1 + (1/4 + 1/8 + 1/16 + ...) + (1/8 + 2/16 + 3/32 + ...) = 1 + 1/2 + ... = 2.
    intuition: n bubble-down: the majority of nodes are cheap (from lower-levels downto leaves: ~1);
    n bubble-ups: the majority are expensive (from leaves upto root: ~logn)
  • hw3 out

Liang Huang
Last modified: Wed Jan 18 23:31:27 PST 2012