CS 4349.501: Advanced Algorithm Design and Analysis (Spring 2008)

Course Syllabus (open with MS word), Class log

Announcements

* 5/9: Final exam scores and your final grades have been posted in WebCT.
       Send me email asap if there are any errors/omissions in the scores.

* 5/02: Solutions to selected problems in Assignment 8.

* 4/30: Solutions to Assignment 7.

* 4/28: You are allowed to bring up to 4 handwritten pages of notes
        to the final exam.  Information on the paper should be written
        in normal size (10 point font or bigger), about 30-40 lines to
        a page with about 8-14 words to a line.  No printed or
        photocopied pages are allowed.

* 4/08: Assignment 8 (due on 4/23).

* 4/08: Topics for final exam on Wednesday, May 7 (5:00 - 7:00 PM):

        Dynamic programming (as applied to shortest path problems).
        Representation of graphs (22.1), Breadth-first search (22.2),
        Depth-first search and its applications (22.3, 22.4, 22.5),
        Minimum spanning trees (23), Implementation of Kruskal's
        algorithm using Union-Find data structure (23.2, 21.3),
        Single-source shortest paths (24, 24.4 excluded, parts of
        24.5 done in class are included: triangle inequality,
        upper-bound property),  All-pairs shortest paths (25.1, 25.2),
        Maximum flow problem (26.1, 26.2), NP-completeness (34).

* 3/27: Assignment 7 (due on 4/7).

* 3/11: Solutions to Assignment 6.

* 3/06: Topics for Mid-term exam 2: Dynamic programming, Greedy algorithms,
        Graphs: definitions, storage techniques, DFS, BFS.

* 3/06: Solutions to Assignment 4, Assignment 5.

* 3/4: Assignment 6 (due on 3/17).

* 2/27: If you got less than 10/10 in Assignment 4, give the exam
        back to me for regrading on Monday.

* 2/21: Assignment 5 (due on 3/3).

* 2/19: Typo in HW4 corrected (i++ should be k++ in k's for loop).

* 2/18: Assignment 4 (due on 2/20).

* 2/11: Solutions to Assignment 2, Assignment 3.

* 2/07: Topics for exam on Feb 13 (closed book/notes):
        Order notation, Growth of functions, Running time analysis,
        Asymptotic notation (Big oh, Theta, Omega), summations.
        Recurrences and Solution techniques: Iteration method,
        Substitution method, (Simplified) Master method,
        Applications of Master method.  Proof techniques.
        Proofs of correctness of loops using loop invariants,
        Divide-and-conquer method: Merge sort, quick sort.
        Correctness of Merge (in Merge sort) and Partition (in Quick sort)
        procedures.  Correctness and Running time analysis of Merge sort.
        Selection problem (finding kth smallest element): DAC algorithm
        using Partition of Quick sort.
        Overview of sorting, Linear time sorting algorithms for
        special inputs (Counting sort, Radix sort, Bucket sort),
        n log n lower bound for comparison based sorting using decision trees.
        Dynamic programming (Assembly-line scheduling, MCM, LCS), Memoization.

* 2/06: Solutions to Assignment 1.

* 2/03: Assignment 3 (due on 2/11).

* 1/23: Teaching Assistant: Zhongnan Zhang (email id: znzhang).
        Office hours: Tue/Thu 4:00-6:00 PM.  Office: ECSS 3.605.

* 1/18: Typographical error in Problem 6 of Assignment 2 corrected.
        The objective is to find a subarray whose sum is maximum.

* 1/16: Assignment 2 (due on 1/30).

* 1/11: Assignment 1 (due on 1/16).
        Scanned from book for Q1 of A1.

* 01/10: Simpler master method for solving recurrences.

* 01/09: Algorithms notes (needs password). 

* 01/07: Try out a quiz for testing your background.