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.

Professor Details:

• Name: Max Bender
• Website: cs.colby.edu/mbender
• Office: Davis 115
• Office Hours:
  • Monday: 2:30 - 4:00 PM
  • Tuesday: --
  • Wednesday: 2:30 - 4:00 PM
  • Thursday: 9:30AM - 12:00 PM, and 2:30 - 4:00 PM
  • Friday: 12:00 - 2:00 PM
• Email: mbender@... (usual Colby email)

TA Details:

• Names: Di Luo and Vincent Pak
• Times: 7PM - 9PM in Davis 122 on following days:
  • On weeks with Problem Sets due: Monday and Wednesday
  • Other weeks: just Tuesday

Course Text:

The text we will be following is Introductions to Algorithms, Third Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (commonly referred to as CLRS). However, I will avoid assigning specific problems out of the text, so that the text will not be required for purchase. However, it does appear to be available for free online at the colby library, so I'll point to relevant sections as they come up so that students can follow along as they would like.

Grading:

• Assignments (20%): These will be assigned every class and are designed to familiarize yourself with the material. Your three lowest scores will be dropped.
• Problem Sets (40%): These will be assigned every 2 weeks and are designed to challenge you with more in depth critical thinking problems. You can turn in one problem sets one class-meeting late without penalty.
• Exams (30%): There will be two exams, each worth 15% of the overall grade. Material in these types of classes tends to build upon itself, so while the second exam will not be "cumulative" in the usual sense, forgetting all the material from the first half of the class would be unadvised.
• 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.

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.

Policy on Collaboration and Academic Integrity:

Assignments should be completed without collaboration, except from your TAs and myself.

I recommend forming groups for problem sets, though I will not explicitly require it. If groups are formed, they should be at most 3 people per group unless given explicit permission by the instructor.

Your professor reserves the right to ask students to verbally explain the reasoning behind any answer or code that they submit and to modify project 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. Kate McLaughlin, Associate Director of Access and Disability Services (kmclaugh@colby.edu), is the primary contact for accommodations and any questions related to educational testing and documentation.

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.