CS 344 - Design and Analysis of Algorithms - Fall 2021
Online, MW 3:00 -- 4:20
Prof. M. Farach-Colton, Core 311
Office hours: M: 10:00 -- 11:00 AM or by appointment
Get their details here.
- Guido Tagliavini
- Hanna Komlos
Please check this page for homework and homework solutions.
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,
Course Contents: Fundamental techniques for designing efficient
combinatorial algorithms and mathematical methods for analyzing their
Syllabus: The following is a tentative schedule.
There will be two midterms and a final exam. The midterms are each
worth 30% of the final grade. The final will cover the entire course
contents and will weigh 35% of the final grade. Homework assignments
will constitute the remaining 5% 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.
- General mathematical background, definition of concepts such as
algorithm correctness, complexity, asymptotics.
- Divide and conquer, recurrences, Strassen's integer
- Sorting: bubblesort, mergesort, quicksort, heapsort, binsort,
radixsort, lower bounds for comparison sorting.
- Graphs: directed, undirected, labeled, representations, minimum
spanning trees, shortest path.
- Graph traversal: breadth first search, depth first search.
- Connected components, strongly connected
- String Algorithms or Miscellaneous other
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
Rutgers CS Diversity and Inclusion Statement
Rutgers Computer Science Department is committed to creating a
consciously anti-racist, inclusive community that welcomes diversity
in various dimensions (e.g., race, national origin, gender, sexuality,
disability status, class, or religious beliefs). We will not tolerate
micro-aggressions and discrimination that creates a hostile atmosphere
in the class and/or threatens the well-being of our students. We will
continuously strive to create a safe learning environment that allows
for the open exchange of ideas while also ensuring equitable
opportunities and respect for all of us. Our goal is to maintain an
environment where students, staff, and faculty can contribute without
the fear of ridicule or intolerant or offensive language. If you
witness or experience racism, discrimination micro-aggressions, or
other offensive behavior, you are encouraged to bring it to the
attention to the undergraduate program director, the graduate program
director, or the department chair. You can also report it to the Bias
Incident Reporting System.