Syllabus

Basic Information

Instructor Will Rosenbaum

Meetings

• Section 01: M/W/F 11:00–11:50, Mead 115
• Section 02: M/W/F 2:00–2:50, SCCE A131

Evening TA Sessions Sundays and Wednesdays, 7:00-9:00pm, location TBD

Official Course Description

This course addresses the design and analysis of computer algorithms. Topics include: set algorithms such as sorting and searching, graph algorithms, string algorithms, and matrix algorithms. Algorithm design paradigms, including the divide-and-conquer, dynamic programming, and greedy paradigms, will be emphasized. The course will end with a discussion of the theory of NP-completeness and its implications.

Course Goals

The main goal of this course is to develop skills to devise and analyze solutions to novel computational problems. Specifically, you will:

• learn to establish the correctness and analyze the efficiency of procedures;

• develop familiarity with common algorithmic paradigms (divide and conquer, greedy, and dynamic programming) and their applications;

• understand and exploit relationships between computational problems to solve novel problems by applying known techniques;

• clearly communicate your solutions and argue their correctness and efficiency.

Textbooks

There are tree recommended textbooks for the course, though many “standard” algorithms textbooks cover the majority of the material we will discuss in class. While there is no single required text, you will be expected to read from the text of your choosing regularly. Depending on your interest and background, I highly recommend purchasing one of the recommended texts for the course. See below for a description of the two recommended texts and why you might choose one over the other.

Recommended Textbooks

• Algorithms Illuminated (Volumes 1–4), Roughgarden (AI)

  This book was developed for a MOOC on algorithms taught by Tim Roughgarden. It covers almost all of the material we will discuss in class with the exception of network flow (for which supplementary notes will be provided). The book is intended to be accessible for self-study with minimal assumed prerequisite knowledge. Thus, it offers a gentler and perhaps more intuitive reading experience than many standard algorithms text. The trade-off is that the book is wordier and covers the material in less formal detail than other texts. Nonetheless, this is a very carefully written text that might be most appropriate if you have less experience with (mathematical) formalism.

• Algorithm Design Kleinberg and Tardos (KT)

  This text was developed for the course Introduction to Analysis of Algorithms at Cornell. It covers all of the material we’ll discuss in class and much more. The text is more of a traditional-style textbook than AI, but it also provides more conceptual/intuitive explanation than many of its predecessors. Nonetheless, it is a denser read than AI and presumes more familiarity with mathematical concepts and conventions. This text might be most appropriate if you have a bit more mathematical background or are planning to pursue algorithms further (e.g., in industry or graduate school).

  • Four copies of KT are on reserve at the Science Library.

• Algorithms in Action Savvich (AA)

  This text offers a very concise treatement of the material covered in class. It is not as formal or expansive as KT, nor does it provide the context and examples of AI. Instead, the book offers a streamlined and clear exposition of the core concepts and results we will explore in class.

  • Available for online viewing through the Amherst College library.

Other “Classic” Texts

• Algorithms Sedgewick and Wayne

  This book covers much of the material we will discuss in Algorithms as well as material from Data Structures. Unlike the other texts, it includes implementations of the algorithms and data structures in Java. If you’d like to see concrete code for the algorithms we discuss, this text is a good complement to the lecture material.

• Introduction to Algorithms Cormen, Leiserson, Rivest, Stein

  CLRS is probably the most influential algorithms text from the last few decades, but it is challenging to read. It is often used as a graduate-level text, and it assumes significant comfort with mathematical concepts. With that warning, it is still a valuable reference, especially if you plan to engage with primary literature on algorithms in the future.

  • A full digital copy is available through the Amherst College library at this link.

Expected Background

Students are expected to be comfortable expressing algorithms as code in the imperative or object oriented style, i.e., using variables, arrays, iteration, methods/functions, and recursion. Students should also be familiar with fundamental data structures, such as arrays, linked lists, trees, and graphs. Finally, students should have experience using asymptotic (“big O”) notation to describe the theoretical running time of code.

Course Structure

Meetings

The class meets three times a week (M/W/F). The format of the course will be part lecture, part guided discussion. Throughout, you are encouraged to participate by both asking questions and answering questions posed to the class. You are expected to prepare for each class by completing the lecture ticket (see below) and doing any assigned reading before class.

• In order to accomodate absences (see below), all lectures will be recorded and made available on the course Moodle site.

Accounability Groups

In the first week of class, you will be assigned to “accountability groups” of three to four students. You will be expected to meet with your group weekly to discuss the course material (though you may choose to meet more frequently as a study group, etc). Your accountability group should be your first point of contact in case you miss a class or have questions about the course that your peers may be able to answer.

Assignments

There are two types of assignments: lecture tickets and regular assignments. Lecture tickets are short assignments that should be submitted before each lecture (i.e., ~3 times a week). The regular assignments are longer assignments that will be due approximately every two weeks. All assignments should be submitted through Gradescope.

Late Homework Policy

Lecture tickets cannot be submitted late. Instead, your lowest 3 lecture ticket scores will be dropped when calculating final scores in the class.

For regular assignments, you have a total budget of 7 “late days” that can be used for submitting late work at any point in the semester without prior permission. This means, for example, that a single assignment can be submitted 7 days late, or that one assignment submitted 4 days late and another 3 days late, etc. Late work will only be accepted beyond the 7 day budget if there are extenuating circumstances and with prior permission.

Exams

The course will have two in-class midterm exams and one final exam. The midterm exams are scheduled for Friday, October 7th and Wednesday, November 16th. The time and location of the final exam is TBD.

Evaluation

Individual questions will typically be graded on the following three point scale:

• 3 points. Solution clearly describes a correct response with sufficient justification, possibly with a minor technical error.

• 2 points. Solution has the right idea, but has some issues with technical details or clarity of explanation.

• 1 point. Solution says something sensible, but suffers from a larger conceptual issue.

• 0 points. No solution provided, or solution is not understandable.

Final grades will be determined by a weighted average of scores on homework and exams. Both raw scores and relative class ranking will be considered in assigning final letter grades.

Topics and Approximate Schedule

Getting Help

This course is designed to be challenging, and you should expect to exert significant intellectual effort. That being said, if you find yourself struggling with the course, here are some opportunities for help:

• Work with your accountability group. Working collaboratively is often an effective and rewarding way to problem-solve. Additionally, by talking through problems, you will help hone your communication skills.

• Attend the evening TA sessions (time and location TBD). In these sessions, you will have the guidance of experienced TAs who have worked through Algorithms before.

• Attend the professor’s office hours.

If these strategies still seem inadequate and you would benefit from regular one-on-one tutoring, peer tutors are available for the course. Please get in touch with me if you would be interested in having a peer tutor for the course.

Other Course Policies

Communication

The main course materials (slides, assignments, etc.) will be posted to the course website. Class announcements and discussion will be moderated on Moodle. All assignments should be submitted through Gradescope.

If you have clarifying questions about course material, policies, assignments, etc., that might be pertinent to other students in the class, please post your question to the Moodle discussion board. For individual questions, email and/or office hours are the best ways to get in touch with me. Please include the tag [COSC 311] in all emails sent to me.

Collaboration

You are encouraged to discuss homework problems and work on assignments together. However, your submitted work should be your work and yours alone. In particular, simply sharing completed work is not acceptable collaboration.

During exams, any form of collaboration and/or use of outside resources is strictly forbidden. You should not discuss the contents of the exam with anyone until all students (in both lecture sections) have submitted their exams.

Attendance and Illness

While attendance will not be graded, you are expected to attend class regularly and actively participate in class discussion.

All students are expected to follow college guidelines and policies regarding COVID testing and masking.

• Unless you are sick or unable to attend, you should come to class.
• If you are sick, you should not attend class. If you unable to attend an in-class exam due to illness, you will be able to schedule a make-up exam at a later date.
• If you are experiencing any symptoms of illness, please take a COVID test before attending and (if negative) wear a mask at all times in class.

As much as possible, I will make course materials available to help mitigate the effects of absences.

Well-being and Accommodations

If you find that you are struggling due to factors that go beyond academic challenges, the Student Affairs office and Counseling Center have a robust set of options to help with your well-being.

If you require accommodations due to a documented disability, please contact Accessibility Services.

Academic Honesty

All students are expected to uphold the Amherst College Honor Code, in particular the Statement of Intellectual Responsibility:

Every person’s education is the product of their intellectual effort and participation in a process of critical exchange. Amherst College cannot educate those who are unwilling to submit their own work and ideas to critical assessment. Nor can it tolerate those who interfere with the participation of others in the critical process. Therefore, the College considers it a violation of the requirements of intellectual responsibility to submit work that is not one’s own or otherwise to subvert the conditions under which academic work is performed by oneself or by others.

Cases in which intellectual responsibility is violated (such as cheating) will result in loss of credit for an assignment and/or a failing grade in the course. Additionally, all suspected cases of academic dishonesty will be reported to the college, which may result in further disciplinary action by the college.