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 work in teams to understand, describe, and analyze algorithms.

Professor Details:

• Name: Max Bender
• Office: Davis 203
• Office Hours: See Schedule
  • Mon/Wed: 2:30 - 4
  • Tue/Thu: 10 - 12
• Email: mbender@... (usual Colby email)

Course Text:

The text we will be following is 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, so I'm going to assign reading and problems out of it occasionally.

Another text that I will probably assign readings out of is 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:

• Small Assignments (10%): These will be assigned roughly every class and are designed to familiarize yourself with the material. Your three lowest scores will be dropped; they will be graded out of 2 points (basically: satisfactory, unsatisfactory, and unsubmitted). I expect there will be around 15 of these.
• Problem Sets (40%): These will be assigned roughly every 2 weeks and are designed to challenge you with more in depth critical thinking problems. You can turn in one problem set one class-meeting late without penalty.
• Project Assignments (40%): These will also be assigned roughly every 2 weeks and are somewhat like problem sets, but are intended to be group work and will be somewhat more applied. I expect there will be around 5 of these.
• Participation (10%): Every day before class I print out a random ordering of the roster and use that random ordering to ask questions as they come up in class. The questions are chosen to not put you on the spot, but rather just to get your thoughts and to make sure everyone is understanding the material. The questions will serve as attendance for the class (even if you don't know the answer you will still be marked as having answered it). Each class after the 3rd missed will deduct a point from your participation. If you need to miss class, just let me know ahead of time if possible.

Late Policy:

In return for the lack of exams in this course, there will be a nontrivial amount of work. Accordingly, I want to be lenient where possible with deadlines, with the understanding that deadlines do matter.

• Small Assignments: I feel like these are low stakes enough that you really shouldn't be stressing over these if you get sick. As a result, your 3 lowest are automatically dropped.
• Problem Sets and Projects: These ones matter. Due to their infrequency, I'm imposing the following rules: if you turn it in within 3 days from the deadline I'll give up to a 95%, within a week an 85%, but after that the maximal score will be a 65% (but can be turned in any time).

Policy on Collaboration and Academic Integrity:

You are permitted to discuss any assignments with each other in this course. In fact, for project assignments you are encouraged to work in groups and submit one submission for the whole group. However, small assignments and problem sets should be written and submitted alone. 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.

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.