01:198:344 (Sections 03&04) Fall 2011
Design and Analysis of Computer Algorithms (4 Cr).

Instructor:   Michael D. Grigoriadis, Department of Computer Science,  CoRE 308; (732) 445-2001, Ext 2898;   Off.Hrs: M 12-1. W: 12-1 and 3:15-4 & by appointment. Email:

TA (Section 03): Rodrigo Franco Toso   1-732-445-2001, Ext 9708; email: rtoso (at) cs (dot) rutgers (dot) edu;   Office: CoRE 346; OffHrs: W 1-2; F 10-11, & by appointment;

TA (Section 04): Amr Naquib Bakry   (732) 445-2001, Ext 9827; email: amrbakry (at) cs (dot) rutgers (dot) edu;   Office: Hill206; OffHrs: Tue 1-2, Thu 6-7, & appointment;

Lectures: MW 6:40-8:00 pm at SEC-210.
Recitations:  Sec03-M 8:25-9:20pm at SEC-210.    Sec04 - T 6:55-7:50pm at ARC-203.
    - No recitations in first week.
    - Lectures & recitations: Attendance is required, with all personal electronics turned off.
    - Student Absence Reporting (NEW!). The SAS Dean's Office now tracks student absences: If you expect to miss one or two classes, please use this secure University Self-Reporting App to indicate the date and reason for your absence. An email is then sent to me by the Dean's Office.

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 elements of discrete 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, 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. Maximum adjacency search.
  • Greedy algorithms.  Spanning trees and cuts, analysis of union-find and path compression; MST algorithms; randomized algorithm for global minimum cuts; approximate set cover.
  • Network flows.  Max flow min cut theorem and integrality; fast algorithms; disjoint (s,t)-dipaths; maximum bipartite matching & minimum vertex cover. 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), supplemented by class notes and handouts. Book at RU bookstore. Errata here!. (Read the Prologue chapter before the first class from the author's public draft.)  
    Reference:   Introduction to Algorithms, Cormen, Leiserson, Rivest & Stein, McGraw Hill, 2nd Edn, 2001, On reserve at SERC, with errata here. (Note: There is a 3rd Edn of this book, 2009.)

    Required work:  Assigned reading; working on handouts and exercises suggested in lectures; keeping your own class notes; weekly or biweekly homework problem sets and pop quizzes, two midterms and a final exam. Come to lectures prepared to participate in class. HW assignments are mathematically oriented and involve derivations of mathematical equations, proofs, and running time analyses of algorithms. HW submissions are by these HW rules, and require individual work.
    N.B.: Experience shows that students who stay engaged, keep up with the suggested or assigned reading, follow up on the practice problems suggested in lectures, participate in class, and diligently do the assigned homework spread over a few days, do well in this course. Remember: Cramming for tests is a losing strategy!

    Dates(University Key Dates)  
  • Lectures: Sep 7,8,12,14,19,21,26,28;                Oct 3,5,10(MT1),12,17,19,24,26,31;
                       Nov 2,7,9, 14(MT2),16,21,28,30;          Dec 5,7,12.
  • Midterm I (1,2) (One hr): Oct 10(new date; was 5), 6:50-7:50pm at Sec210. Closed books/notes. (Optional cheat sheet: 2/3 of one side of an 8.5X11" sheet of your own, legibly handwritten notes. No makeups.
  • Midterm II (2) (incremental; one hr): Monday, Nov 14 6:50-7:50pm at Sec210. Closed books/notes. (Optional cheat sheet: 1 and a 1/3 sides of an 8.5X11" sheet of your own, legibly handwritten notes). No makeups. No makeups.
  • Final Exam (3) (cumulative; three hrs): Dec 19, 8:00-11:00 pm at SEC-210. Closed books/notes. (Optional cheat sheet: both sides of an 8.5X11" sheet). No makeups.

    Grading guideline:   0.15 (HW & Quizzes) + max {   0.25 MT1 + 0.25 MT2 + 0.35 FIN,   0.35 MT2 + 0.50 FIN }.
    (Attendance and class participation are also considered).      

    (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;  double-check the (University Key Dates)
    (2) A missed HW, quizz or midterm draws zero credit.
    (3) A missed final exam draws an F 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. Also, follow the Final Exams Scheduling Conflicts Resolution procedure, when such cases arise).

    On Academic Integrity Required reading!     HW rules.    On handling emails .     Other class admin announcements .

  • HOW TO EFFICIENTLY RESOLVE ANY AND ALL GRADING ISSUES


    Other Useful links:
  • Rutgers Health Services, general page.
  • RU (most) Academics links
  • RU Academic Calendar, and a ( standard 2011 U.S. calendar).
  • RU NB Registrar's Office links
  • University Key Dates)
  • Registrar's page
  • Standard periods
  • Campus status info (weather, cancelletion of classes, etc.)
  • University-wide Fall 2011 Final Exam Schedules.
  • Online schedule of classes.
  • CS Undergraduate program information.
  • Undergraduate LCSR Web Page, accounts, etc.