CS 3813/780, Advanced Programming, Spring 2014

Time and Location MW, 9:15 -- 10:30 am, SB A135B
Instructor Prof. Liang Huang (huang@cs)
Teaching Assistant Dr. Lemao Liu (lemaoliu@gmail)
Course Admin Ms. Xiuyi Huang (xiuyi@cs)
Course Homepage http://acl.cs.qc.edu/~lhuang/teaching/advprg/
Office Hours MW, 10:40 -- 11:15 am, SB A227
Additional office hours available before quizzes and exams.
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 homework: 5+6+8+8+8=35%, quizzes: 10+15=25%, final project: 25%.
in-class problem-solving sessions: 2%x5=10%. class participation: 5%.
homework policy: only high-level discussions are allowed; only one HW can be late for 24 hours.


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


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 M 1/27
  • Administrativia
  • Review: quicksort, mergesort, BSTs, memoized Fibonacci (DP)
  • Python Showcase
  • slides for Section 1 (weeks 1-2)
  • HW1 out on T 1/28, due T 2/4: longest path on binary tree; randomized qselect; qsort=>BST, search/insertion on BST; memoized Ackermann
W 1/29
  • Python Tutorial
  • quickselect, randomization
2 M 2/3
  • More on Python Tutorial
  • Discussions of HW1
W 2/5
  • Quiz 1
  • More discussions on HW1
3 M 2/10
W 2/12
4 M 2/17
W 2/19
  • heaps: array representation, bubble-up, bubble-down
  • hw2 problem 1
  • gnuplot demo on O(n^2), O(nlogn), O(n), etc.
Th 2/20
(monday schedule)
  • heapq
  • applications of priority queue: k-way mergesort, choose top k from stream, etc.
  • Dijkstra
5 M 2/24
  • lowest common ancestor
  • first in-class problem solving session
W 2/26
  • help on hw2
  • DP intro: longest increasing subsequence
6 M 3/3
  • DP: knapsack: 0-1 & unbounded
W 3/5
7 M 3/10
W 3/12
  • second in-class problem solving session
8 M 3/17
W 3/19
9 M 3/24
    LCS & KMP
W 3/26
    sample code for DP (0-1 Knapsack): memoized recursion (top-down) vs. bottom-up
    when is top-down faster (sparse), and when is bottom-up faster (dense)?
10 M 3/31
  • miniquiz 3
  • HW3 solutions
W 4/2
  • LICS: O(n^4) -> O(n^3)
  • LCS w/ a query subseq
11 M 4/7
  • Viterbi and topological sort
  • Viterbi vs. Dijkstra
  • LCS w/ a query subseq
W 4/9
  • Viterbi on DAGs: backward vs. forward updates
  • Implementation details of topological sort
  • Matrix-Chain Multiplication
  • Viterbi on Hypergraphs
  • HW4 out
12 M 4/14-T 4/22 SPRING BREAK
12 W 4/23
  • Quiz 2

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