Design and Analysis of Computer Algorithms - Fall 2012
01:198:344 Section 01 (4 cr) or 16:711:611 (3 cr).


Instructor:   Michael D. Grigoriadis, Department of Computer ScienceCoRE 308; (732) 445-2001, Ext 2898;   Off.Hrs: T 4-5; Th 12:30-1:30 & by appointment. Email:

TA: Chaolun, Xia,   Department of Computer ScienceHill 486;   Off.Hrs: W&F 9:30-10:30 & by appointment. Email: cx28@cs.rutgers.edu.

Lectures: T 12-3 at SEC-218.       Recitations: -Th 1:55-2:50 at Hill-005.
    - Lectures & recitations: Attendance is required, with all personal electronics turned off.
    - Student Absences are tracked by the SAS Dean's Office:
If you expect to miss one or two classes, use this secure University Self-Reporting App to report the date and the reason for your absence. An email is then sent to me by the Dean's Office.

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

Prerequisites: 198-112,   and   198-206 (or 01:640-477),   (and thus Calc II).    We also assume elements of discrete mathematics, such as  logarithms, proofs 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, and randomization. Fibonacci numbers. Euclidean gcd algorithms. Universal hashing.
  • 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. Linear-time sorting: radix and bucket sorts.
  • 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.
  • 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, 2008 (paperback or download for kindl, etc.), supplemented by class notes and handouts. The book in now 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. The second edition (2001) will be on reserve at SERC, with errata here. The 3rd (2009), is optional for this course.

    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 quite well in this course. Remember: Cramming for tests is a losing strategy!


    Dates ( University Key Dates)
  • Lectures: Sep 4,11,18,25;                Oct 2, 9(MT1), 16, 23 30;
                       Nov 6, 13(MT2), 27 ;          Dec 4,11 (last class).
  • Midterm I (1,2) Oct 9, 12:00-12:45, at SEC-218. 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 (incremental) (2) TUESDAY, Nov 13, 12:00-12:45 at SEC-218. Closed books/notes). (Optional cheat sheet: 1 and 1/3 sides of an 8.5X11" sheet of your own, legibly handwritten notes). No makeups.
  • Final (cumulative): (3) THURSDAY, Dec 20, 8:00-11:00 am at SEC-218. Closed books/notes). (Optional cheat sheet: both sides of an 8.5X11" sheet). No makeups.

    Grading guideline(0) :   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).
     

    (0) How to efficiently resolve grading issues
    (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 deadlines at University Key Dates).
    (2) A missed HW, quizz or midterm draws zero credit. Important HW rules.
    (3) A missed final exam draws zero credit.   (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!    On handling emails .     Frequently check your sakai for all timely class admin announcements and details.

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