Always remember to check here, or on Muthu's 344 Page
for the homework
Homework 3
CS 344 - Design and Analysis of Algorithms - Fall 2003
SEC 118, MW4 (1:10 -- 2:30)
Prof. M. Farach-Colton, Hill 448, Phone: 732-445-6424
email: farach@cs.rutgers.edu
www: http://www.cs.rutgers.edu/~farach
Office hours: M: 2:30--4:00 PM or by appointment
TAs:
- Lan Yu lanyu@paul.rutgers.edu
- Carlos Diuk cdiuk@paul.rutgers.edu
- Lei Wnag lewang@paul.rutgers.edu www
Text: Baase, Computer Algorithms
Prerequisites: 198:112; 198:206 or Discrete Structures II; Calc
II
Knowledge of basic concepts of programming and data structures is
assumed (e.g. lists, stacks, queues, trees) as well as basic
mathematics (e.g.\ proof by induction, permutations, logarithms,
the basics of solving recurances, and asymptotic (i.e. big-oh,
big-omega) notation).
Course Contents: Fundamental techniques for designing efficient
combinatorial algorithms and mathematical methods for analyzing their
complexity.
Syllabus: The following is a tentative schedule.
- General mathematical background, definition of concepts such as
algorithm correctness, complexity, asymptotics. (1 class. Chapter 1)
- Divide and conquer, recurrences, Strassen's integer
multiplication. (1 classes. Chapter 7.3)
- Sorting: bubblesort, mergesort, quicksort, heapsort, binsort,
radixsort, lower bounds for comparison sorting. (4 classes. Chapter 2)
- Selection (1 class. Chapter 3.4)
- Graphs: directed, undirected, labeled, representations, minimum
spanning trees, shortest path. (5 classes. Chapter 4.1 -- 4.3)
- Graph traversal: breadth first search, depth first search. (2
classes. Chapter 4.4)
- Connected components, strongly connected
components. (2 classes. Chapter 4.6)
- String Algorithms or Miscellaneous other (3 classes. e.g.\ Chapter
5.2, 6.3 )
- NP-completeness (4 classes. Chapter 9)
Grading Policy:
There will be two midterms and a final exam. The midterms are each
worth 25% of the final grade. The final will cover the entire course
contents and will weigh 40% of the final grade. Homework assignments
will constitute the remaining 10% of the final grade. No make-up
will be given for the second
midterm. If a student misses that midterm, she/he will
have the remaining exams and homework weighted proportionally higher.
The homework assignments are mathematically oriented and involve
derivations of mathematical equations, proofs of combinatorial
theorems and running time analysis of combinatorial algorithms. 80%
of the assigned homework will be used to compute the homework grade.
NO LATE HOMEWORK WILL BE ACCEPTED.
You are responcible for forming groups of four students (no more, no
less) 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.
Finally, the first exam is something of a make-or-break situation. If
your score on the first exam is sufficiently low (and the threshold
will be very low), then you fail the class. The first exam will be
earlier enough for you to drop the class.
Schedule:
- 1st Midterm: October 13th
- 2nd Midterm: November 17th
- No class: November 26th
- Final: December 10th