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

REMINDER: FINAL EXAM 8 - 11 AM, TUESDAY MAY 12, HILL 116

SERU: AN IMPORTANT SURVEY TO COMPLETE.

Instructor:   Michael D. Grigoriadis, Department of Computer Science,  CoRE 308; (732) 445-2001 Ext 2898;  OHrs:   W 4:45-5:45 pm; Th. 3:15-4:15 pm, and by appointment. Email:

  • TA (Section 1): Sergio de Biasi   Hill 416.   732-445-2001, Ext 9691; sdebiasi (at) cs (dot) rutgers (dot) edu; OffHrs: M 2-3pm and T 4-5pm and by appointment.
  • TA (Section 2): Imdad Khan   Hill 405;   1-732-445-2001, Ext. 9558; imdadk (at) rci (dot) rutgers (dot) edu; OffHrs: Th 4:45-5:45 pm and F: 2:30-3:30 pm. and by appointment.

    Lectures and Recitations. (Attendance is mandatory. No electronic devices.)
       Lectures: TTh 1:40-3:00 pm at HILL-116.
       Recitations:  Sec01-T 5:15-6:10pm at ARC-105.    Sec02-Th 3:35-4:30pm at ARC-108.

    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 and possibly some new 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; a randomized algorithm for minimum cuts; approximate set cover.
  • Network flows.  Max flow min cut theorem; fast algorithms; bipartite matching; Menger's theorem and disjoint dipaths. Global minimum cuts.
  • 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; integer and (0,1) knapsack problems; chain matrix multiplication; single-pair reliable SPs, all-pairs SPs; independent sets.
  • Elements of NP-completeness & problem reductions.
  • NP-hard problems. Search and selected approximation algorithms.

    Textbook:   Algorithms,  Dasgupta, Papadimitriou & Vazirani, McGraw Hill, 1st Edn, 2008 (paperback), ISBN-10: 0073523402; ISBN-13: 978-0073523408, presently available at the RU bookstore. In the meanwhile read the Prologue! Get the errata here).
    Reference: Introduction to Algorithms, Cormen, Leiserson, Rivest & Stein, McGraw Hill, 2nd Edn, 2001, ISBN-10:0-262-03293-7; ISBN-13:978-0-262-03293-3. Get errata here). (Will be placed on reserve at SERC.)

    Required work:  Assigned reading(1); working on handouts and suggested exercises; keeping your own class notes; weekly or biweekly homework problem sets(2), and pop quizzes. HW sets require individual work. HW assignments are mathematically oriented and involve derivations of mathematical equations, proofs, and running time analyses of combinatorial algorithms. Come to lectures prepared to pose and respond to questions when you're called upon.

    N.B.: Experience shows that staying engaged with the course, keeping up with the suggested or assigned reading and practice problems, as well as doing the homework diligently, is essential to doing well in this course. Cramming for exams is a losing strategy!

    Notes: (1) Source material, reading assignments and practice exercises will be announced in lectures and on-line: Frequently check the class communications page!!   (2) Submit your homework within the first 5 minutes of the lecture on the due date. Late homework is not accepted.

    Dates:
        First Lecture: 1:40-3:00 pm., Tuesday 1/20, at Hill-116.
        Midterm I: 1:40-3:00 pm., March 10, 2009, at Hill-116.   No make-ups (1).  
        Spring recess: Sat March 14 through Sunday March 22.
        Midterm II (incremental): 1:40 pm., Tuesday, April 14, at Hill-116.   No make-ups.  
        Last lecture:   Thursday April 30.
       
        Final (cumulative):  8-11 AM, Tuesday, May 12 (per University schedule),
        at Hill 116, but stay tuned for last minute changes.   No make-ups!    (2).
     
    (1) Do not miss the early HW and Midterm 1 so that you may gauge your progress versus the norm early on, assess how you might improve your standing in class, or, even consider taking a "W" for the course in order to concentrate on your other commitments;  see The Registrar's links below.
    (2) A missed HW, quizz or midterm draws zero credit. A missed final exam draws an F grade for the course.   (Medical emergencies will be considered upon submitting a University-issued written verification 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.25 MT2 + 0.60 FIN }.

    On Academic Integrity Required reading!    On handling emails

    Useful links:
  • RU (most) Academics links
  • RU Academic Calendar, and a (standard year 2009 U.S. calendar).
  • RU NB Registrar's Office links
  • The RU Registrar's Add-Drop rules (BE SURE TO CHECK THE APPLICABLE 2009 DEADLINES!)
  • Registrar's page
  • Campus status info (weather, cancelletion of classes, etc.)
  • University-wide Spring 2009 Final Exam Schedules.
  • Online schedule of classes.
  • Undergraduate LCSR Web Page, accounts, etc.
  • CS Undergraduate Student Information.