CS 344 - Design and Analysis of Algorithms - Fall 2021

Online, MW 3:00 -- 4:20

Prof. M. Farach-Colton, Core 311
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: Get their details here.
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, 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. Grading Policy: 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.

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.

Schedule:
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.