CS 6363: Computer Algorithms (Spring 2008)

Course Syllabus (open with MS word)   Class Log

Announcements

 
* 5/05: Scores for mid-term exams, final and grade have been posted in WebCT.
        If an asterisk appears after your grade, then you got a better grade
        due to extra credit in the homeworks and exams.  For example,
        if your grade is "B*", then it means that a "C" grade was improved
        to a "B" because of extra credit.  This "*" will not appear in
        your transcript.

* 4/30: Solutions to Assignment 9.

* 4/30: Solutions to Assignment 7, Assignment 8.

* 4/30: Topics in exam from Ch 34: 34.2, 34.5 and definitions from 34.3.

* 4/28: This document will be printed and given to you in the exam.
        Exam is closed book/notes otherwise.

* 4/28: Topics for final exam on Friday, May 2 (2:00 - 4: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).
        All-pairs shortest paths (25.1, 25.2),
        Maximum flow problem (26.1, 26.2),
        NP-completeness (34.2, 34.5, definitions from 34.3).

* 4/28: If you need an extension to Assignment 9, you can drop
        it off in my office by this Wednesday at 2pm.

* 4/19: Assignment 9 (due 4/28).
* 4/09: Assignment 8 (due 4/23).
* 3/27: Assignment 7 (due 4/9).

* 3/17: Solutions to Assignment 5, Assignment 6.

* 3/13: Classroom changed to ECSS 2.415 for the rest of the semester.

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

* 03/04: Assignment 6 (due 3/17).

* 02/26: Assignment 5 (due 3/5).

* 02/18: Assignment 4 (due 2/22).

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

* 02/07: Topics for exam 1 on Wed, Feb 13 (closed book/notes):
         Order notation, Growth of functions, Running time analysis,
         Asymptotic notation (Big oh, Theta, Omega) and the limit method
         for determining O/Theta/Omega.  Summations of arithmetic and
         geometric series, Approximation by integrals.
         Recurrences and Solution techniques: Iteration method,
         Substitution method, Recursion tree method, Master method,
         Applications of Master method.
         Divide-and-conquer method: Merge sort and Quick sort algorithms,
         Loop invariants to prove correctness of Merge and Partition functions,
         Finding Min and Max of an array using 1.5n-2 comparisons,
         Multiplication of two n-bit numbers in O(n^{log 3}).
         Sorting networks: 0/1 principle, bitonic sequences,
         bitonic half-cleaner, bitonic sorter, merger, sorting network.
         Polynomial multiplication and FFT algorithm.
         Selection problem of finding the k-th smallest element of a
         given array, O(n) randomized algorithm for Select,
         O(n) deterministic algorithm for Select,
         linear-time sorting algorithms (Counting, Radix, Bucket).
         Dynamic programming (Assembly-line scheduling, MCM, LCS), Memoization.
         Omega(n log n) lower bound for comparison-based sorting.

* 02/06: Solutions to Assignment 1.

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

* 01/18: Teaching Assistants: 
  1. Wenke Zhang (email id: wxz072000).
     Office hours: TR 2:00-4:00pm. 
     Office: ECSS 3.605/3.213(lab).
  2. Shaoyang Liu (email id: sxl048000).
     Office hours: Tues 3:00-5:00pm,  Fri: 3:00-5:00pm
     Office: ECSS 3.232.

* 01/18: Assignment 2 (due 1/30).

* 01/16: Slides used in class for FFT.

* 01/14: Algorithms notes (old) (needs password).
  Userid/password will be announced in class.

* 01/11: Assignment 1 (due 1/16).

* 01/09: Classroom has been changed to ECSS 2.311.

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