Design and Analysis of Algorithms

Course Goals

By the end of this course, you will have developed the following knowledge and skills:
  • You will know how to design and analyze algorithms, and clearly explain the steps of your design and analysis, justifying your claims with formal proof.
  • You will learn and understand several standard algorithmic design techniques, including greedy algorithms, divide and conquer, and dynamic programming.
  • You will be able to apply standard algorithmic design techniques to solve computational design problems of moderate difficulty. You will be able to describe and use these techniques in clear write-ups.
  • You will be able to identify problems that are computationally intractable and argue why these problems might be hard to solve efficiently.
  • You will learn how to design randomized and/or approximation algorithms, and determine when approximation and/or randomization are useful for a problem.
Above all, the goal of this course is to instill a deep understanding of how to think algorithmically about problems.

Student Responsibilities

CS41 covers material that is similar to what you saw in CS35 or CS21. However, the perspective is much different, and what you will be learning is different too. This course is much more about learning how to solve computational problems and analyze your solution(s), and less about implementing algorithms that we've gone over in class. To succeed in this course, you should consistently do the following:

  • Attend class and lab sessions.
    The primary introduction to course material is through class instruction. Attending class is essential for understanding the subject. Lab sessions provide additional time to work on solutions. Lab attendance is mandatory.
  • Participate actively in the learning process.
    The best way to learn algorithms material is through constant effort. During class we will often derive solutions collaboratively. Labs provide additional time to experiment with algorithmic solutions. There is a very strong correlation between students that ask questions and students that do well in this class.
  • Start the homework assignments early.
    CS41 homeworks are typically not coding assignments. It is extremely difficult to bang out algorithmic solutions at the last minute. I understand that it is not always possible to put serious time into an assignment early. However, even 30-60 minutes will be helpful, to ensure that you understand what the problems ask of you and you start thinking about how to solve them early.
  • Seek help early.
    It is essential in this class that you not fall behind. If you find yourself falling behind, or if you're having trouble grasping a concept, come to office hours. Ask (and answer!) questions on EdStem. Set up an appointment to talk with me.

Partner Etiquette

The expectation is that you and your partner are working together on your partnered homework assignments. You should work together on planning, discussing, and writing up the problems. There may be short periods where you each go off and independently work on the problems, but you should frequently come together to talk about your progress as a team. The final submission has everyone's names on it and should represent work done as a team. You should not submit your name on work which is not your own.

Partnerships where partners work mostly independently tend to result in incomplete and buggy submissions, and do not help you learn the material thoroughly. Partnerships where partners work together for most of the time are much more productive and helpful in learning the material and successfully solving the problems.

If you have any issues with your partnership, please contact me as soon as issues arrive.

Academic Integrity

Academic honesty is required in all your work. Under no circumstances may you hand in work done with or by someone else under your own name. Discussing ideas and approaches to problems with others on a general level is encouraged, but you should never share your solutions with anyone else nor allow others to share solutions with you. You may not examine solutions belonging to someone else, nor may you let anyone else look at or make a copy of your solutions. This includes, but is not limited to, obtaining solutions from students who previously took the course or solutions that can be found online. The use of generative AI (e.g., chatGPT or GitHub CoPilot) without proper citation is also considered to be unauthorized collaboration with an outside source and is a violation of our academic integrity policy.

You may not share information about your solution in such a manner that a student could reconstruct your solution in a meaningful way (such as by dictation, providing a detailed outline, or discussing specific aspects of the solution). You may not share your solutions even after the due date of the assignment.

In your solutions, you are permitted to include material which was distributed in class, material which is found in the course textbook, and material developed by or with an assigned partner. In these cases, you should always include detailed comments indicating on which parts of the assignment you received help and what your sources were.

When working on tests, exams, or similar assessments, you are not permitted to communicate with anyone about the exam during the entire examination period (even if you have already submitted your work). You are not permitted to use any resources to complete the exam other than those explicitly permitted by course policy. (For instance, you may not look at the course website during the exam unless explicitly permitted by the instructor when the exam is distributed.)

Failure to abide by these rules constitutes academic dishonesty and will lead to a hearing of the College Judiciary Committee. According to the Faculty Handbook: "Because plagiarism is considered to be so serious a transgression, it is the opinion of the faculty that for the first offense, failure in the course and, as appropriate, suspension for a semester or deprivation of the degree in that year is suitable; for a second offense, the penalty should normally be expulsion."

This policy applies to all course work, including but not limited to code, written solutions (e.g. proofs, analyses, reports, etc.), exams, and so on. This is not meant to be an enumeration of all possible violations; students are responsible for seeking clarification if there is any doubt about the level of permissible communication.

The general ethos of this policy is that actions which shortcut the learning process are forbidden while actions which promote learning are encouraged. Studying lecture materials together, for example, provides an additional avenue for learning and is encouraged. Using a classmate’s solution, however, is prohibited because it avoids the learning process entirely. If you have any questions about what is or is not permissible, please contact your instructor.

Policy on use of Generative AI. In this course, students may use generative AI for homework assignments as long as it does not circumvent the learning process of the course. In any circumstance, if/when you use generative AI you must explicitly state that in your pollster poll (a) that you did so and (b) in what context you used generative AI, even if you used it only to generate ideas rather than usable text or illustrations.
You may be asked to come into my office to discuss your solutions. I reserve the right to not award you credit for problems that you cannot explain in these discussions.
Overall, AI tools should be used wisely and reflectively with an aim to deepen understanding of subject matter.

Please contact me if you have any questions about what is permissible in this course.