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

Latest Admin Announcements

ABOVE ALL, ABOUT YOUR HEALTH -- and the H1N1 influenza virus!
(Quick link to Info for students.)

Instructor:   Michael D. Grigoriadis, Department of Computer Science,  CoRE 308; (732) 445-2001 Ext 2898;  Off.Hrs: Wed 1:30-3:30 pm (tentative) and by appointment. Email:

  • TA (Section 1): Devendra Desai   1-732-445-2001, Ext. 9542; E-mail: devdesai [at] cs [dot] rutgers [dot] edu. Office: Hill 268. OffHrs: M&Thu 11-12 (tentaive) and by appointment.
  • TA (Section 2): Rodrigo Franco Toso   1-732-445-2001, Ext 9708; email: rtoso (at) cs (dot) rutgers (dot) edu; Office: CoRE 346; OffHrs: T&F 2-3pm (tentative) and by appointment.

    Lectures and Recitations. (Attendance is mandatory. No electronic devices.)
       Lectures: MW 6:40-8:00 pm at SEC-210.
       Recitations:  Sec01-M 8:25-9:20pm at SEC-210.    Sec02-T 6:55-7:50pm at ARC-203.

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

    Prerequisites: 198-112,   198-206 (or 640-477),   (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, binary search, recursion, hashing, priority queues, graph algorithms, sorting.

    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 (also see Class Calendar in the Latest Admin Announcements):
        1st Lecture: Wed Sept 2. 2nd Lecture: Tue Sept 8. 3rd Lecture: Wed Sept 9.
        1st Recitaton for Section 2: Tue Sept 1 has been cancelled. Next one is on Tue Sept 15 !
        1st Recitaton for Section 1: Tue Sept 8. Next one is on Tue Sept 14.
        That is, there is NO CLASS OR SECTION 1 RECITATION on Mon Sept 7 (Labor Day) BUT BOTH will be HELD ON TUE SEPT 8 instead.

        Midterm I: Oct 7 (tentative) ==> Monday, OCT 12 (firm).   No make-ups (1).  
        Thanksgiving recess: Wed Nov 25 through Sun Nov 29.
        Midterm II (incremental) Monday, Nov 23:   No make-ups.  
        Last lecture:   Wed Dec 9.
       
        Final (cumulative):  8-11 PM, Wed, Dec 16 (fixed, per University schedule),
        at our regular classroom, but stay tuned for last minute changes.   No make-ups!     (2,3).
     
    (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.)
    (3) Resolution of final exam scheduling conflicts

    Grading guideline:   0.15 (HW & Quizzes) + max {   0.20 MT1 + 0.20 MT2 + 0.45 FIN,   0.25 MT2 + 0.60 FIN }.
    (Class and recitation attendance and class participation will also be taken into account in assessing your grade in this course.)

    On Academic Integrity Required reading!    On handling emails

    Partial list of links mentioned above:

  • ON ACADEMIC INTEGRITY: Required reading!!. (And what is meant by individual work for HWs.)
  • Final exam date&time (8-11 pm, Wed Dec 16) is FIXED. Rules for Resolution of Scheduling Conflicts
  • Stay engaged with classwork -- cramming for exams is a losing strategy!
  • How to make sure your CS344-related emails are not overlooked.
  • Latest Admin Announcements.
  • The H1N1 influenza and us :)
  • Make sure to get the errata for DPV. Those for CLRS, 2nd edition are here.

    Other Useful links:

  • Rutgers Health Services, general page.
  • RU (most) Academics links
  • RU Academic Calendar, and a (standard year 2009 U.S. calendar).
  • RU NB Registrar's Office links
  • The SAS page on Add-Drop rules and deadlines
  • Registrar's page
  • Campus status info (weather, cancelletion of classes, etc.)
  • University-wide Fall 2009 Final Exam Schedules.
  • Online schedule of classes.
  • CS Undergraduate program information.
  • Undergraduate LCSR Web Page, accounts, etc.