CS344 Spring 2008
01-198-344: Design and Analysis of Computer Algorithms (4 Cr).

Instructor:   Michael D. Grigoriadis, Department of Computer Science,  CoRE 308; (732) 445-2001 Ext 2898;  OHrs:   Tue 11:45-1:45 pm and by appointment. Email:

  • TA (Section 1): Reid Howard   Hill 205, 1-732-445-2001, X9549; reidh@cs.rutgers.edu; O-Hrs: Th & F 12-1:30pm
  • TA (Section 3): Andre Madeirs   Hill 414; 1-732-445-2001, X9507; amadeira@cs.rutgers.edu; O-Hrs: M 9:30-11am and W 1:30-3pm

    Lectures and Recitations. (Attendance required in both. No electronic devices.)
       Lectures: MW 6:40-8:00 pm at Hill-116.
       Recitations:  Sec01-M 8:25-9:20pm at SEC-211;   Sec03-W 5:15-6:10pm at SEC-207.

    Course Objectives: Fundamental techniques for designing efficient combinatorial algorithms. Mathematical methods for analyzing their correctness and complexity.

    Prerequisites: 198:112,  198:206 (and thus Calc II).    We also assume knowledge of basic mathematics, such as  logarithms, proof by induction, series and sums, permutations, asymptotics (big-Oh, big-Omega notation), basics of solving recurrences, as well as concepts of programming and data structures, e.g., linked lists, stacks, queues, trees.

    Topics:  We will cover a large subset of the following algorithmic topics and applications as time permits:
  • Mathematical tools.  Review of mathematical background, basic concepts of algorithm design, complexity, asymptotics, induction.
  • Graph search.  Graph classes and representations; depth first search in undirected and directed graphs; topological search; strongly connected components. Breadth first search and layered DAGs.
  • Shortest Paths (SPs) in digraphs. Single-source SPs for nonnegative edge weights; priority queues and Dijkstra; SPs in DAGs; single-source SPs for general edge weights.
  • Greedy algorithms.  Spanning trees and cuts, union-find and path compression; MST algorithms; randomized algorithm for minimum cuts; approximate set cover.
  • Network flows.  Maximum flows & minimum cuts in digraphs; fast algorithms; bipartite matching; Menger's theorem and disjoint dipaths.
  • Divide and conquer. Fast integer multiplication; recurrences; the master theorem; mergesort; randomized median and selection algorithms; quicksort; fast matrix multiplication.
  • Sorting.    Lower bounds for comparison-based sorting; binsort and radix sort.
  • Dynamic programming; Paradigm of SPs in DAGs; longest increasing subsequence; approximate string matching; knapsack problems; chain matrix multiplicatio; single-pair reliable SPs, all-pairs SPs; independent sets.
  • Elements of NP-completeness. NP-complete problems & reductions. Search and selected approximation algorithms.

    Textbook:   Algorithms,  Dasgupta, Papadimitriou & Vazirani, McGraw Hill, 1st Edn, 2008 (paperback). Get errata here).
       Reference: Introduction to Algorithms, Cormen, Leiserson, Rivest & Stein, McGraw Hill, 2nd Edn, 2001. Get errata here). (On reserve at SERC.)

    Required work:  Assigned reading(1); working on handouts; keeping your own class notes; weekly homework problem sets(2), and pop quizzes. HW sets require individual work. The HW assignments are mathematically oriented and involve derivations of mathematical equations, proofs of combinatorial theorems and running time analyses of combinatorial algorithms. Experience shows that keeping up with the assigned reading and doing the homework diligently is essential to doing well in this course.

    Notes: (1) Source material and reading assignments will be announced in lectures. Refer to the class communications page for additional information.   (2) Submit your homework within the first 5 minutes of our class on the due date. Late homework is not accepted, i.e., a missed homework draws zero credit.  

    Dates:
        First Lecture: 6:40-8:00 pm., Wednesday 1/23, at Hill-116.
        Midterm I: 6:40 pm., Wednesday 2/27, at Hill-116.   No make-ups (1).  
        Spring recess: Tue March 15 through Sunday March 23.
        Midterm II (incremental): 6:40 pm., Monday 4/7, at Hill-116.   No make-ups.  
        Last lecture:   Monday, May 5.
       
    Final (cumulative):  8-11 pm, May 12 (per University schedule).
    EXAM IS AT THE SEC building, ROOM 111.   No make-ups!    (2).
     
    (1) Do not miss Midterm 1 so that you may gauge your progress versus the norm early on, assess how you might improve your standing or, perhaps, to even consider taking a "W" for the course in order to concentrate on your other commitments;  see Registrar links below.
    (2) A missed final examination draws an F grade for the course.   (Medical emergencies will be considered upon submitting University-authorized verification of such emergency to the Instructor; for assistance contact your Dean's Office.)

    Grading guideline:   0.15 (HW & Quizzes) + max {   0.20 MT1 + 0.20 MT2 + 0.45 FIN,   0.26 MT2 + 0.59 FIN }.

    On Academic Integrity Required reading!

    Useful links:
  • RU (most) Academics links
  • RU Academic Calendar
  • RU NB Registrar's Office links
  • Undergraduate Registrar's Spring 2008 Calendar
  • Cancelletion of classes and status.
  • University-wide Spring 2008 Final Exam Schedules.
  • Online schedule of classes.
  • Undergraduate LCSR Web Page, accounts, etc.
  • CS Undergraduate Student Information.