Course: COS 340

Instructor: Bernard Chazelle

F 2018

### Description of Course Goals and Curriculum

This course covers mathematical topics and proofs relating to theoretical computer science. Emphasis will be placed on the mathematical reasoning behind proofs. The course is taught via lectures and precepts, with weekly problem sets, a midterm, and a final exam. This class is different from most COS courses in that there is no explicit programming involved, so it feels more like a math or ORF class.### Learning From Classroom Instruction

Lectures Lectures primarily serve to motivate many of the topics covered, so they are sometimes abstract. They also overlap with the assigned textbook readings, so it is helpful to read the assigned chapters before lecture so that students can reinforce their understanding of the readings. To get the most out of lecture, it is helpful to relate the content to the readings and focus on the motivating questions behind some of the concepts presented. To take organized notes in lecture, it helps to structure your notes by topic and avoid only writing what the lecturer writes on the board, because this might not make sense later on without writing down the context of why the lecturer wrote it. Precepts Precepts serve to apply the concepts from lecture and readings to problems that are similar to those on the assignments. Handouts with the problems and solutions are provided, so it is not necessary to write down everything the preceptor does. However, it is important to write down details behind some of the steps in proving something or solving a problem, because the solution handouts may not explicitly state every assumption or step that goes into a proof and it is helpful to fill in the details so you gain a better understanding of why the solution works. Furthermore, this will help you understand how to use similar problem-solving strategies for assignments and exams. Be sure to ask questions if you are unsure of the logic behind the problem-solving or proof processes because this is critical to your understanding of the topics presented. Readings The assigned readings primarily come from two online textbooks, which are designed for a similar course taught at another university. The readings are designed to be instructive, so they are usually not too dense or abstruse. Since the readings heavily overlap with lecture, it is helpful to do them before lecture and revisit them afterwards. Furthermore, it is not necessary to memorize the readings, but it is important to understand what motivates certain problems and the logic behind how they are solved.### Learning For and From Assignments

Problem Sets This course has weekly problem sets, usually about 5 problems per week. In past semesters, students were allowed to discuss problems in groups of three, but write up the solutions on their own. Problem sets are an opportunity for students to see if they understand not only why a the material in lecture, readings, and precepts makes sense, but also to see if they can apply it to other types of problems. The key here is that the problems in problem sets may look very different from those presented in precepts, but the students are expected to find ways to apply the concepts to these new problems. To increase learning from problem sets, it is best to attempt all the problems independently at first, and later on, check with collaborators or ask conceptual questions broadly related to the approach of questions you were not able to do. Furthermore, office hours and lab TA’s are helpful with explaining approaches to these problems, but it is best to try to tackle even the most difficult problems for a while before you ask someone else for help, since this will prepare you for exams. In terms of time management, students are expected to use LaTex for the problem sets, so it is best to start the problem sets early. For students who are not used to using LaTex, it might take a few hours to do this step, so students should account for this when scheduling time to work on the assignments. Exams The exams contain problems that are comparable in difficulty to the problem sets and precept problems. However, the exams can feel more difficult because there is a time constraint. In past semesters, students are allowed to bring any course materials, in printed or electronic form (but no communication during the exam), so it is important to study approaches to problems rather than memorizing. Furthermore, some exam questions might look unusually difficult or unrelated to the course material, but this might mean that a problem can be converted to look more like a concept taught in class, so it is important to keep this mind so you can find unexpected ways to approach difficult questions.### External Resources

Lab TA’s and Office Hours The course has Lab TA’s to help out with problem sets and explain concepts. It is helpful to go to their office hours after identifying difficulties in the material or problem sets. The instructors also have office hours in which students can clarify material or assignment questions. Piazza There is a Piazza page for this course, in which important announcements, readings, and assignments are all posted. It is important to follow this page, as there could be important clarifications for assignments posted on it. Furthermore, it is another resource to ask questions to other students or instructors (and even answer other students’ questions) regarding the course materials if you have a quick question and cannot make it to office hours. Keep in mind that questions here are supposed to be general, so if your question involves discussing a homework solution itself, then it is better to ask about it at office hours. Other Online Resources There are similar courses taught at other universities (such as MIT), so you can use their lecture notes or videos as well for concepts that are difficult to grasp with the provided materials. Keep in mind that other resources might not perfectly overlap with the material in this course, so you should keep in mind what the instructors specifically want you to learn as you go through other resources. Outside resources are especially useful when studying for exams because practice exams have not been provided in the past, so this is an opportunity to practice new problems as you would on a final.### What Students Should Know About This Course For Purposes Of Course Selection

This course is intended for COS majors and fulfills the theory requirement. It is also popular among similar majors like ORF and Math. The skills learned in this course could be important for students interested in further study or research in computer science or discrete math. The problem sets can be very time consuming, depending on your level of prior experience with proofs, so make sure you allocate enough hours for it in your schedule. For students with experience in similar classes (ex: ORF 309), some of the content will be a review, but there is more of an emphasis on thinking about these problems from a computer science lens.Reasoning about Computation