Course Promises / Learning Objectives

By the end of the course, you will have developed the following knowledge and skills:

• You will know how to analyze the powers and limits of various models of computation.
• You will learn and understand several standard proof techniques, including induction, contradiction, and diagonalization.
• You will be able to identify problems that are computationally intractable and argue why these problems might be hard to solve efficiently.

Above all, the goal of this course is to instill a deep understanding of the limits of computation, and how to think about these in a thorough and systemic way.

Student Responsibilities

CS46 is different from most other computer science courses, in that the course focuses on abstract thinking about problems, and does not ask you to implement many solutions in code. To succeed in this course, you should consistently do the following:

• Read the textbook prior to class.
  It will be assumed that you have read the posted readings on the syllabus prior to attending class. You may not follow everything you read in the book the first time, but we will supplement the text through class instruction. However, class instruction may not cover basic definitiona or detailed examples explained thoroughly in the text.
• 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 get hands on practice with the course material. Lab attendance is mandatory.
• Participate actively in the learning process.
  The best way to learn this material is through constant effort. This means trying to work out proofs yourself rather than simply reading through solutions. During class we will often derive solutions collaboratively. Labs provide additional time to experiment with solutions. There is a very strong correlation between students who ask questions (in class/lab/office hours/Piazza) and students who do well in this class.
• Start the lab assignments early.
  CS46 is not a coding course; it is a course with an emphasis on rigorous thought and explanation. It is extremely difficult to bang out proofs and 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 to help you start thinking about how to solve them early.
• Seek help early and often.
  Because course material builds on previous material, it is essential to your success in this class that you keep up with the course material. If you feel you are falling behind or having trouble grasping a concept, please come to office hours. Ask questions, and review other questions on Piazza. You should also feel free to email me to set up an appointment if you cannot attend normal office hours.

Academic Integrity

In this course, limited collaboration in planning and thinking through solutions to problems is allowed and encouraged, but no collaboration is allowed in writing up solutions. Your submitted write-up is your own. Please list your discussion partners and the extent of your discussions at the beginning of your write-up.

Note: in the following paragraphs, "code" refers to all homework solutions, including written programs but also proofs, analysis, written reports, etc.

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. Your code should never be shared with anyone; you may not examine or use code belonging to someone else, nor may you let anyone else look at or make a copy of your code. This includes, but is not limited to, obtaining solutions from students who previously took the course or code that can be found online. You may not share solutions after the due date of the assignment.

Discussing ideas and approaches to problems with others on a general level is fine (in fact, we encourage you to discuss general strategies with each other), but you should never read anyone else's code or let anyone else read your code. All code you submit must be your own with the following permissible exceptions: code distributed in class, code found in the course text book, and code worked on with an assigned partner. In these cases, you should always include detailed comments that indicates on which parts of the assignment you received help, and what your sources were.

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."

We will routinely run plagiarism detection software on your lab assignment submissions.

The spirit of this policy applies to all course work, including code, homework solutions (e.g., proofs, analysis, written reports), and exams. Please contact me if you have any questions about what is permissible in this course.