CSE 312: Foundations of Computing I, Spring 2023

General Information

Students are expected to be familiar with all of the information below. They should read it fully and carefully.

Instructors

Paul Beame [he/him]

MWF 10:30-11:20 (CSE2 G01)
beame(at)cs.washington.edu
Office: CSE 668

James Wilcox [he/him]

MWF 1:30-2:20 (CSE2 G01)
jrw12(at)cs.washington.edu
Office: CSE 440

Course Resources

  1. Course website: https://cs.washington.edu/311

  2. Gradescope, EdStem and other materials linked from the website above.

Announcements

You should regularly check the class web site and EdStem for announcements and other information, including the most up-to-date information on problem sets and errata. The class web page will also have the schedule of topics to be covered and links to other class materials, including slides (after lecture) etc. If you have any personal questions, please email the instructors directly. Any other non-sensitive questions about course content should be posted on our discussion forum. The discussion forum also allows posting privately that are visible only to the course staff.

Goals

The goals of this course are to:

  • Teach students the shared language of computer scientists.
  • Give students a toolkit for solving difficult computational problems.
  • Allow students to practice making and clearly communicating rigorous, formal arguments.
  • Introduce students to theoretical computer science.

Prerequisites

The formal prequisites of this course are MATH 126 and CSE 123/143. Informally, we will assume familiarity with basic mathematical objects like integers and functions and with the basics of how computers perform calculations. For example, we will assume students are familiar with how non-negative integers can be written in binary.

For students who are unsure of their preparation for the course in any way: You are strongly encouraged to take CSE 390z concurrently with CSE 311.

Course Structure

Topics

The course content can be grouped into three parts:

  1. Logic and Proofs: how to make and communicate rigorous, formal arguments (and how to specify logic circuits)
  2. Applications of Logic: understanding mathematical objects that are widely used in computer science such as numbers, sets, relations, and recursively-defined data and functions
  3. Theoretical Computer Science: different models of computation and what problems they can solve

Textbook

There is no required text for the course. For the first 6-7 weeks of the course, the following textbook can be useful: Rosen, Discrete Mathematics and Its Applications, McGraw-Hill. (Course materials will reference problem numbers from the 8th edition, but older versions largely include the same material.) It should be available through the bookstore and on short-term loan from the Engineering Library.

On occasion, there may be required readings during the course when there is insufficient time to fully cover the material during lecture. If this occurs, the readings will be posted on the web site and students will be notified of the reading via email or the message board.

Lectures

Lectures will be given in person, at the locations and times shown on the time schedule. They will be recorded for later review but this ability should not be used to substitute for in-class attendance. Experience with prior classes has shown that there is a strong correlation between attendance in class and overall course grades.

Sections

Each week includes a TA-led quiz section. These will not be recorded, but the printed material used will be posted on the section list and calendar.

Each quiz section will be focused on preparation for the next homework assignment. A substantial portion of the time will be spent on practice problems similar to those appearing in that homework. It is very important that students take the time to work through the practice problems before attempting the homework, not only to make sure they understand how to solve them but also to understand how to communicate their solution in writing in a way that will be clear enough to receive full credit.

Course Grades

Your final course grade will be computed according to the following rough breakdown:


Problem Sets (8)45-50 %
Midterm15-20 %
Final Exam30-35 %

Problem Sets

  • There will be 8 homework problem sets, to be solved individually.

  • Students will receive an email invitation, during the first week of the course, to a course web page in GradeScope, where they can submit their homework solutions. To do so, they will first need to scan their solutions into a PDF. Portions of the scans that are not readble by the TAs (either due to the quality of the scan or the legibility of the handwriting) cannot be graded or receive credit.

  • Many of the problem sets will also involve submission through tools via another website that will let you practice with the course concepts directly and will act both as an assistant and autograder.

  • Problem Sets will generally be due on Wednesdays.

  • You must show your work; at a minimum 1-2 sentences per question, but ideally as much as you would need to explain to a fellow classmate who had not solved the problem before. A correct answer with no work is worth nothing, less than a wrong answer with sufficient explanations explaining your reasoning.

  • You must tag the question parts of your homework correctly on Gradescope. Failure to do so will result in a 0 on every untagged question. Please check your submission by clicking each question, and making sure your solution appears there.

  • You do not need to solve all problem sets to secure the highest possible grade.

  • Students are encouraged to help each other learn the course material. However, we must disallow collaboration that aims to avoid learning (a.k.a. "cheating").

    It is okay, and indeed encouraged, to discuss homework problems with other students, but this is subject to strict constraints:
    • You must list, on their submission, the name of everyone you worked with.
    • You must write up all solutions on your own, unassisted.

    When working on solutions with others, we require that:

    • You do not leave with any part of the solution in writing or photographs (only in their head).
    • You wait at least 30 minutes before writing your own solution.

    Since you cannot list "The Internet" as one of their collaborators, students may not consult the Internet for problems or key-phrases. This includes Google, MathOverflow, reddit, and any other website. However, students may consult the internet for ideas, definitions, and understanding general concepts.

    Each student should keep their own solution (the one they plan to or have submitted) private until after the assignment due date. Under no circumstances should they give a copy of their solution to another student, as that would clearly violate the rules listed above.

    You must be able to explain your answer if asked to do so. We may do some spot checks in which we ask students to explain one of their solutions (or solve a slight variant of the problem they solved on the homework) in person.

    Extra Credit

    Homework assignments will often have extra credit problems. They will be scored separately from the regular problems, and they will have little to no impact on course grades. The main incentive for doing the extra credit problems is for the additional challenge.

    Typesetting

    Students are not required to type their homework solutions. However, solutions are required to be legible, and typesetting is one way to ensure that they are easy to read.

    Students who would like to try typing their solutions can see the typesetting page for advice on how to do so. Another useful resource for those who want to learn latex (especially useful if you take other classes that involve a fair amount of math or plan to write research papers) is here. However, students should be warned that the software is not always easy to use. In the past, some students have spent several hours trying to make their solution look the way they want, which is neither necessary nor advisable.

    Late Policy

    • Problem Sets: You have a total of four late days during the quarter, but can only use up to two late days on any one problem set. Please plan ahead, as we will not be willing to add any additional late days except in absolute, verifiable emergencies.

    • The final problem set will not be accepted late.

    Homework Regrades

    If grading mistakes occur, regrade requests are due on Gradescope within one week of grades being published (with no exceptions). While regrades can (and should) be used to fix mistakes where a correct solution is mistakenly marked incorrect, they cannot (and should not) be used to request changes to amounts of points deducted for errors. Deductions are applied consistently to all students. We will not give one student a smaller deduction than others who made the same (or very similar) mistakes, so do not ask us to do so.

    Getting Help

    Each member of the course staff will have at least one office hour every week, where students can get one-on-one help. See the staff page Course Staff Page for times and locations.

    Students can also ask questions at any time on the message board. During normal working hours, they should receive a response within a fairly short period of time (certainly under an hour).

    Exams

    • There will be a midterm and final in this course to act as culminating assessments of the course concepts.
    • The midterm will be in class during your regular lecture time on Wednesday, May 10.
    • The final exam will be Monday, June 5 in JHN 102 rather than our regular classroom. The exam times are also changed from the times and location listed in the exam schedule. There will be two times possible: either 2:30-4:20 or 4:30-6:20 to choose from.

    Policies

    Inclusiveness

    Students should expect and demand to be treated with respect by their classmates and the course staff. All students belong here, and the staff is here to help them learn and enjoy a challenging course. If any incident occurs that challenges this commitment to a supportive and inclusive environment, students should please let the staff know so the issue can be addressed.

    Academic Integrity

    As noted above, even when students work together to initially solve a problem, we expect each student to write their own solution, independently and unassisted. Attempting to misrepresent another student's solution as their own would be unfair to the other students in the course and constitute academic misconduct in violation of the Allen School policy. Any such violation will be reported to University, and the instructors will make every attempt to ensure the harshest allowable penalty.

    If a student is ever unclear about whether their collaboration went over the line, they should (a) ask and (b) describe their collaboration clearly on their assignment. If they do, the worst that will happen is losing some points. That is much better than the alternative.

    Accommodations

    • Disability Accommodation Policy: See here for the current policy.

    • Religious Accommodation Policy: See here for the current policy.

    Advice For Students

    • Start each homework assignment early. As noted above, it is hard to know how long any assignment will take you, so you need to leave time available in case the problems are more difficult than you expected. We strongly encourage you to consider a schedule of completing one problem a day, rather than all the problems in one or two days.

    • Prefer the message board to office hours. Office hours get very busy, especially in the last 48 hours before assignments are due. (Yet another reason to start early is that you can attend office hours that are less busy.) Even just before assignments are due, however, questions on the message board are usually answered within a short period of time.

    • Do not skip class to work on homework, not even late in the quarter when you are more tired and busy. Doing so often seems like it will save you time in the short run, but it will cost you time (and learning) in the long run.

    • Remember that your grade in this course matters much less than how much you learn. Your success in future classes (and job interviews) will depend on how well you learned the topics we cover, not what grade you received. (Employers, in particular, do not care that your instructors say, via your grade, that you learned the material. They want to see you demonstrate your knowledge directly in the interview.)

    • Remember that making mistakes is part of learning. The only people who do not make mistakes are those who don't try new things. People who push themselves to do new things make mistakes all the time, even if you don't notice them. As Kevin Kelly said, "professionals are just amateurs who recover gracefully from their mistakes."

    • Try to find the parts of computer science that excite you. To quote Kevin Kelly again, "being enthusiastic is worth 25 IQ points".