Design & Analysis of Efficient Algorithms— Summer 2022
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
- Students will learn the classic algorithms and their key properties.
- Students will learn the basic techniques to prove properties of algorithm, e.g., proving runtime bounds.
- Students will be able to abstract out the core computational problem and apply existing algorithms to solve them.
- Students will learn how to apply formal methods to practical problems of interest.
- Students will strengthen their problem-solving skills by learning how to tackle new problems with known techniques.
- Students will learn to study new algorithms independently so as to promote career-long learning.
Course Webpage
Course Structure
The course will be run in a hybrid-synchronous manner. All students are expected to attend
lectures (see grading).
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.
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 48 hours of the due date.
I highly recommend you start your work early.)
Office Hours: Tuesdays/Thursdays 1pm–2pm via Zoom. Link will be on Blackboard.
TA Information
Name: Henry Welles
(he/him/his)
Email: hwelles (at) u (dot) r o c h e s t e r (dot) e d u
Lectures
Monday–Thursday from 10:00AM to 12:30PM (EDT) in Goergen 109 or via Zoom. See Blackboard for the Zoom link.
While attendance is not required, the material will be quite hard to grasp, especially in four 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).
Recitations
Thursdays 6–7pm via Zoom. See Blackboard for the Zoom link.
Attendance is not required, but it is strongly recommended as the material is hard and
the homeworks are tricky and Henry is an excellent TA.
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.
- [KT]: Kleinberg J. and Tardos E. Algorithm Design, Addison Wesley, 2005.
- [CLRS]: Cormen T., Leiserson C., Rivest R., and Stein C.
Introduction to Algorithms, 3rd edition.
- Other materials, such as lecture slides, course notes, and homeworks, will be
distributed via myCourses. You are not be allowed to redistribute these without my permission.
Schedule
See here. The schedule is subject to change, depending on the class's pace.
Grading
You will be graded on the following basis:
- Problem-sets → 40%
- In-class exercises → 40%
- Final Project/Presentation → 20%
The different items in each category are equally weighted.
Attendance is mandatory and counts towards your final grade.
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) homeworks in this course (see schedule),
each weighted equally. You are allowed to discuss homeworks with your peers and you can work 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 textbooks, lecture slides, and your course notes
are fair game however).
Homeworks will be released early enough to give students ample time to complete them.
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. You should contact the TA directly, as they are in charge of grading.
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 m 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:
- Often if a problem seems impossible or too hard, you might be overseeing a simplification in the
problem. Other times you might be unintentionally imposing unnecessary restrictions on yourself.
- Short and elegant solutions are always preferred to long and complex ones; if your solution seems overly
complicated, try to see if there's a simpler way.
- Often in life, research, and academics, when a problem seems too hard, it is a good idea to take
a step back and clear your head before returning to it;
endlessly hacking at a problem is not always productive.
- "After solving a challenging problem, I solve it again from scratch, retracing only the
insight of the earlier solution. I repeat this until the solution is as clear
and direct as I can hope for. Then I look for a general rule for attacking similar problems,
that would have led me to approach the given problem in the most efficient way
the first time." – Robert Floyd
- Asking for help (including to the instructor) is never a bad idea.
Disclaimer
This page is subject to change throughout the term. Important changes will be announced in class.