Course Description:

Analysis of Algorithms focuses on classic algorithms in computer science, their design, and the analysis of their correctness and efficiency. Algorithms covered include sorting, searching, and other problem solving with various data structures, including arrays, lists, trees, and graphs. Major categories of algorithm design are discussed, including the iterative, divide-and-conquer, dynamic programming, and greedy paradigms. Intractable problems are also discussed, as is the role of NP-completeness.

Desired Course Outcomes:

• Students understand and can calculate the time and space efficiency of algorithms, including big-O, big-Omega, and Theta notations.
• Students understand and can employ conventional approaches to demonstrate algorithm correctness.
• Students understand and can analyze classic sorting, searching, and graph algorithms, and their advantages and disadvantages in various contexts.
• Students understand and can design and analyze algorithms in various categories, including iterative, divide and conquer, dynamic programming, and greedy.
• Students understand the concept of NP-Completeness and its significance in studying the time efficiency of algorithms.
• Students can clearly and rigorously communicate the analysis of an algorithm, both in writing and out loud.

Professor Details:

• Name: Max Bender
• Office: Davis 203
• Office Hours: My Schedule
• Email: mbender@... (usual Colby email)

Course Text:

We will largely follow the following two texts in this class:

• Introductions to Algorithms, Fourth Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (commonly referred to as CLRS). It is freely available for download from the Miller library.
• Jeff Erickson's Algorithms, which is also freely available.

CLRS is often considered the book on algorithms. I don't necessarily disagree with this assertion, but I imagine many of you will struggle to read it efficiently. Erickson's book is much more down to Earth and accessible (although it does assume some familiarity with induction, which it covers early on in the text), at the cost of a little rigor at times.

Grading:

• Assignments (15%): Starting from our very first class, a short assignment will be given out at the end of every single class period (so, roughly 24 over the course of the semester) and will be due at the start of the next class period. See the assignments page for the running list. These are graded entirely on completion, not correctness — my graders are simply checking that you gave it an honest, good-faith attempt. To be clear about what that means: turning one of these in is not me certifying that your answer is right, it's your own signature to yourself that you actually sat down and gave the material real, honest consideration. Getting a question wrong costs you nothing here; not seriously attempting it is the only way to lose credit.
• Participation (20%): Participation is broken down into the following categories:
  • Scribing, which has two components: (a) taking very extensive notes for a given class period and sending me a legible image / scan that I can upload to our website, and (b) co-hosting (and therefore attending) the very next evening TA session that follows that class. There is exactly one TA session between every pair of consecutive classes: the one following a Monday class is always on Tuesday evening; the one following a Wednesday class is on a second weekly night that I'm still finalizing. I expect that these sessions will mostly be just working on the assignments.
  • Being active in class or active in the TA sessions. The TA sessions will have a sign-in sheet to let me know who's attending: if you're the type who prefers to participate in a more group focused way, this is reasonable.
• Quizzes (20%): Starting with our 3rd class (Sept. 16), every class period will end with a short (∼5-10 minute) quiz. These are typically low-stress by design: expect a rephrasing of a previous assignment question, a question about the previous lecture, or something of similarly reasonable difficulty. Your lowest 3 quiz scores are automatically dropped.
• Exams (45%): There are 4 required midterms for this course, plus a cumulative final exam that is entirely optional. The course is organized into 5 conceptual areas, and each midterm covers the material from one stretch of the schedule (the first two areas are combined into a single midterm, since Introduction is largely just setup for the proof techniques Greedy relies on):

  Exam	Date	Covers
  Midterm 1	Thu, Oct. 1	Introduction + Greedy
  Midterm 2	Thu, Oct. 22	Divide and Conquer
  Midterm 3	Thu, Nov. 12	Dynamic Programming
  Midterm 4	Thu, Dec. 10	Reductions and P vs. NP

  • All 4 midterms are proctored evening exams. Locations are TBD. My default exam window is 6:30–10:00 PM, with the expectation that most people will be reasonably finished in the 7:30–8:00 range; the extra time in the window is there so no one has to stress about the clock. If you'd like some reassurance on this point, feel free to ask around with students who've taken this course before; time has not historically been a real obstacle on these exams.
  • Rather than a simple average, your 4 midterm scores are combined using a weighted scale that counts your stronger exams for more than your weaker ones.
  • The final exam is optional. If you choose to sit it:
    • If your final exam score is better than your (weighted) midterm score, the final counts as 22.5% of your overall course grade, and the weight of the midterm block is halved to 22.5% (still using the same weighted scaling among your 4 midterms).
    • If your final exam score is not better than your weighted midterm score, it's simply folded in as a 5th score into the same weighted scaling.
  • If you don't sit the final, your 4 weighted midterm scores simply count for the full 45%.
  Exam locations will be posted here as soon as they're finalized. It is your responsibility to reach out to me ASAP if a date isn't going to work for you so we can figure out a reasonable work-around.

Late Policy:

• Assignments: I feel like these are low stakes enough that you really shouldn't be stressing over these if you get sick etc. As a result, you are forgiven 3 missed assignments. I will not accept late assignments.
• Quizzes: Your lowest 3 scores are automatically dropped, which is intended to cover ordinary absences and off days. If something larger comes up (illness, emergency, etc.) that costs you more than that, just let me know and we can discuss.
• Midterms: Reach out to me as far in advance as possible if a scheduled date is a genuine conflict. I make no guarantees for being able to handle a scheduling problem the day of.

Policy on Collaboration and Academic Integrity:

You are permitted to discuss assignments with each other in this course, but the work you turn in (assignments, quizzes, and exams alike) should be your own and written/worked in your own words. One of the core objectives in this course is to learn how to analytically communicate in the space of algorithms, which is a skill you have likely had minimal practice in before, and that only develops by actually doing the writing yourself.

Your professor reserves the right to ask students to verbally explain the reasoning behind any answer or code that they submit and to modify grades based on the answers. It is vitally important that you turn in work that is your own! Reports of academic dishonesty are handled by an academic review board and a finding of academic dishonesty may result in significant sanctions. For more details on Colby's Academic Integrity policies and procedures, see https://www.colby.edu/academicintegrity/.

The Colby Affirmation:

Colby College is a community dedicated to learning and committed to the growth and well-being of all its members. As a community devoted to intellectual growth, we value academic integrity. We agree to take ownership of our academic work, to submit only work that is our own, to fully acknowledge the research and ideas of others in our work, and to abide by the instructions and regulations governing academic work established by the faculty. As a community built on respect for each other and our shared physical environments, we recognize the diversity of people who have gathered here and that genuine inclusivity requires active, honest, and compassionate engagement with one another and surrounding communities. We agree to respect each other, to honor community expectations, and to comply with College policies. As a member of this community, I pledge to hold myself and others accountable to these values wherever I may find myself.

Statement regarding Academic Accommodations:

The following is the standard suggested language regarding Academic Accommodations at Colby. It applies to this course. I am available to discuss academic accommodations that any student with a documented disability may require. Please note that you'll need to provide a letter from the Dean of Studies Office documenting your approved accommodations. Please meet with me within two weeks of the start of the semester to make a request for accommodations so that we can work together with the College to make the appropriate arrangements for you.

Mental health:

I care about our students' well-being and understand they may face mental health challenges. Students are encouraged to seek support from the College's available resources, including your advising dean and Counseling Services. (For immediate care, please call 207-859-4490 and press "0" to reach the on-call counselor.) I am willing to discuss reasonable accommodations during a crisis, but to fulfill our educational mission, students are expected to adhere to the attendance policy. Failure to do so because of mental health challenges may require consultation with the Dean of Studies Office.