Online, MW 3:00 -- 4:20

email: martin@farach-colton.com

www: http://www.cs.rutgers.edu/~farach/344.html

Office hours: M: 10:00 -- 11:00 AM or by appointment

TAs:

- Guido Tagliavini
- Hanna Komlos

Please check this page for homework and homework solutions.

Knowledge of basic concepts of programming and data structures is assumed (

Course Contents: Fundamental techniques for designing efficient combinatorial algorithms and mathematical methods for analyzing their complexity.

- General mathematical background, definition of concepts such as algorithm correctness, complexity, asymptotics.
- Divide and conquer, recurrences, Strassen's integer multiplication.
- Sorting: bubblesort, mergesort, quicksort, heapsort, binsort, radixsort, lower bounds for comparison sorting.
- Selection
- Graphs: directed, undirected, labeled, representations, minimum spanning trees, shortest path.
- Graph traversal: breadth first search, depth first search.
- Connected components, strongly connected components.
- String Algorithms or Miscellaneous other
- NP-completeness

The homework assignments are mathematically oriented and involve derivations of mathematical equations, proofs of combinatorial theorems and running time analysis of combinatorial algorithms. The best 80% of the assigned homework will be used to compute the homework grade. NO LATE HOMEWORK WILL BE ACCEPTED.

You are responsible for forming groups of at between three and five students for doing homework. At most one homework assignment will be accepted per group. Please take some care in selecting your homework group. Make sure that your group members have a similar work ethic and talent for math as you.

On any assignment (homework or exam), you can either attempt to answer the question, in which case you will receive betweeen 0 and 100% credit for that question, or you can write "I don't know", in which case you receive 25% credit for that question. Leaving the question blank is the same as writing "I don't know."

Finally, the first exam is something of a make-or-break situation. If your score on the first exam is 25% or less (which amounts to a blank exam) then you fail the class. The first exam will be earlier enough for you to drop the class.

- 1st Midterm: TBA
- 2nd Midterm: TBA
- Final: TBA