Design & Analysis of Efficient Algorithms— Summer 2023

Course Description (from CDCS)

How does one design programs and ascertain their efficiency? Greedy algorithms, dynamic programming, divide-and-conquer techniques, string processing, graph algorithms, mathematical algorithms. Introduction to NP-completeness and linear programming. Online version available for remote learners. Prerequisites: (CSC 172 and MATH 150) or MATH172 or mathematical maturity.

Course outcomes

Course Structure

The course will be run in a hybrid-synchronous manner. All students are expected to attend lectures. Class sessions will not always be one-directional lectures and will often comprise of in-class exercises or activies to reinforce learning, so please be ready to be asked to participate. On that note, I may call on students during class lectures in a rotational manner (different students every time). This is not to put you on the spot, but rather to keep everyone included. If that makes you uncomfortable, please let me know ahead of time. To aid with discussions and collaborations, I have set up a course Piazza. You can access it via Blackboard.

Instructor Information

Name: Michael C. Chavrimootoo (he/him/his)
Email: michael (dot) chavrimootoo (at) r o c h e s t e r (dot) e d u (Students can generally expect a response within 48 hours on weekdays. This does not apply to homework questions sent within 24 hours of the due date. I highly recommend you start your work early.)
Office Hours: See Blackboard. Link will be on Blackboard.

Lectures

MTWF from 2PM to 3:35PM (EDT) in Hylan 201 or via Zoom. See Blackboard for the Zoom link. While attendance is not required, the material will be quite hard to grasp, especially in six weeks, if you don't attend the lectures. You must request special accommodation if you cannot attend lectures synchronously (and there are few reasons that apply for such accommodations).
Note: If you are sick or feeling unwell, especially with symptoms relating to COVID-19, I ask that you please attend virtually until you feel better or are no longer contagious, as the safety of those in the classroom is of utmost importance. You will not be penalized for attending virtually. On a similar note, masking is optional (per current guidelines), but you are more than welcome to wear one if you want.

Course Material

The following textbooks are recommended, but not required. I personally prefer [CLRS] (and it is far more common), but consulting [KT] first will likely be more productive (and easier). Both books are excellent and the schedule will contain suggested readings from both.

Schedule

See here. The schedule is subject to change, depending on the class's pace.

Grading

You will be graded on the following basis: The different items in each category are equally weighted. Most of the material is quite abstract and to aid in your learning doing in-class exercises is most productive.
Life happens and you may sometimes need to miss class. I will automatically give everyone two (2) "free passes." What that means is that you can miss up to two (2) class sessions without affecting your "In-class exercises" grade. You don't have to explain yourself, just take them. I will not give more of those (unless there are extenuating cirumstance such as sickness, death, among others).
Additional guidelines may be provided in class.

Homework Rules

You can expect four (4) pre-homeworks, and four (4) homeworks in this course (see schedule), each weighted equally. You should not lookup homework answers. You are allowed to discuss homeworks with your peers and you can work on them together, but you must write your answers individually, i.e., when you write your solutions, it must be without any external help (such as notes from discussing with a friends, the internet, or AI-based toolls; the textbooks, lecture slides, and your own course notes are fair game however).
Pre-homeworks are released at the same time as homeworks and are meant to get you thinking before the homeworks are actually due. Many of the homeworks problems require quite some time to think through.
Homeworks will be released early enough to give students ample time to complete them. You will submit homeworks to Gradescope (see Blackboard). Late homeworks will receive a grade of zero (0), unless you have received an extension from me (all extensions must be requested well in advance, e.g., asking for an extension 20 minutes before the deadline is not "well in advance"). I strongly recommend students to always submit something, even if it's partly done, rather than submit nothing. Partial credit can sometimes add up quite nicely.

Grade Disputes

All grade disputes must be submitted within two (2) business days from when the grade was assigned. (And those requests can be made via Gradescope.)

Disabilities and/or Accommodations

Please reach out to the relevant office and have them inform me if you need any accommodations, so that I can provide them properly.

Academic Integrity

UR's academic honesty policy will be strictly enforced. You should only submit work that is completely your own. Failure to do so counts as academic dishonesty and so does being the source of such work. Submitting work that is in large part not completely your own work is a flagrant violation of basic ethical behavior and will minimally be punished with failing the course.

If you're worried about your performance in the course, reach out to me before considering academic dishonesty. If you're facing a grey area and aren't sure if you might do something dishonest, reach out to me. At the end of the day, I care about your success and wish to help to you.

Zoom/Class Etiquette

Lectures will be recorded. Office hours will not be recorded. You are expected to show mature and respectful behavior both in lectures and in office hours. Do not hesitate to add your preferred name and pronouns in your Zoom name.

Some tips:

Disclaimer

This page is subject to change throughout the term. Important changes will be announced in class.