**
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 Science, CoRE
**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 Science, Hill
**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.