Syllabus

CS103 Course Syllabus

Are there “laws of physics” in computing? Are there fundamental restrictions to what computers can and cannot do? If so, what do these restrictions look like? What would make one problem intrinsically harder to solve than another? And what would such restrictions mean for our ability to computationally solve meaningful problems?

In CS103, we'll explore the answers to these important questions. We'll begin with an introduction mathematical logic, proofs, and discrete structures (sets, relations, functions). These mathematical tools will enable the real heart of the course, which is to rigorously answer questions like “what does it mean for a computer to solve a problem?” and “what makes some problems (sorting) inherently harder than others (searching)?”

In the course of the quarter, you'll see some of the most impressive (and intellectually beautiful) mathematical results of the last 150 years. In some ways, I like to think of this course as a course in both art appreciation and practice. I’ll bring you through a gallery and show you some of my favorite achievements of mathematical artistic beauty, and like a good tour guide help you understand what is special about what you’re looking at. You’ll also need to pick up the paintbrush yourself and write some proofs of your own. You'll learn how to think about computation itself and how to show that certain problems are impossible to solve. Finally, you'll get a sense of what lies beyond the current frontier of computer science, especially with regards to biggest open problem in math and computer science, the P = NP problem.

Teaching Team

Please take a moment to get to know us by checking out the staff photos and bios on our Ed forum intros post!

The best way to reach us for any question on any topic, large or small, public or private, is by posting on the Q&A forum Ed Discussion. If you need to send email, it's best to send to both instructors and the head TA (see course home page), to ensure your message isn't missed.

Websites and Technology

The main CS103 website is where you are right now, cs103.stanford.edu. We have links to a bunch of other tools here. Here's the quick rundown:

Prerequisites

CS103 has CS106B as a prerequisite or corequisite. This means that if you want to take CS103, you must either have completed or be concurrently enrolled in one of CS106B or CS106X (or have equivalent background experience).

Over the course of the quarter, we will be giving out a number of programming assignments to help you better understand the concepts from the course. Those assignments will assume a familiarity with C++ and programming concepts (especially recursion) at a level that’s beyond what’s typically covered in CS106A. The timing on these assignments is designed so that they’ll sync up with what’s covered in CS106B.

Although CS103 is a course on the mathematical theory behind computer science, the only actual math we'll need as a prerequisite is high-school algebra. We'll build up all the remaining mathematical machinery we need as we go. We've released another handout detailing the mathematical prerequisites for this course, so if you have any questions, check it out and see what you find!

Units

If you are an undergraduate or are taking this course through SCPD, you need to enroll in CS103 for five units (these are department and university policies, respectively). If you are a matriculated graduate student, you may enroll for anywhere between three and five units, depending on what best fits into your schedule. Regardless of how many units you are enrolled for, the course content and requirements will be the same. The unit flexibility is simply to make enrollment bookkeeping easier for matriculated graduate students.

CS103A

CS103A is an optional, one-unit companion course that runs alongside CS103. It's a great way to get extra practice with the course material and generally sharpen your theory skills. If you're interested in CS103A, you can apply online here.

OAE Accommodations

We are of course committed to meeting all OAE disability accommodations. To ensure rapid response and complete service, we have our Head TA dedicated especially to this importart duty. At your earliest convenience, please send your letter to our Head TA Ophir. He will also be your primary point of contact for any needs you have relating to implementing your accommodations throughout the quarter, so look out for emails from him, and feel free to reach out to him with ongoing questions about your accommodations at any time.

Video cameras located in the back of the room will capture the instructor presentations in this course. For your convenience, you can access these recordings by logging into the course Canvas site. These recordings might be reused in other Stanford courses, viewed by other Stanford students, faculty, or staff, or used for other education and research purposes. Note that while the cameras are positioned with the intention of recording only the instructor, occasionally a part of your image or voice might be incidentally captured. If you have questions, please contact a member of the teaching team.

Problem Sets

There will be ten total problem sets in CS103, given out once per week. They will be posted on Friday afternoons and are due the following Friday at 2:30PM Pacific time. (Although we do therefore have two assignments that overlap with the weeks of our midterm exams, rest assured they will be much lighter than usual and have eaiser grading.)

Submitting Work

You will submit an assignment by uploading a PDF to GradeScope. Please practice being good engineers by leaving yourself a fault tolerance window of time before the due date/time, to allow for any hiccups in the uploading process, thank you! :-)

In the past we’ve had issues with clarity of handwritten work, so barring a very extenuating circumstance (contact course staff for approval), you are required to type your assignment solutions, not hand-write. $\LaTeX$ is a great way to type up solutions, and we'll help you get started with that tool if you like, but Microsoft Word or similar options are also acceptable.

Coding Problems

Some of the questions on the problem sets will ask you to write C++ code. You’ll code these in Qt Creator on your own computer and upload the code on Gradescope. Note that programming questions and written questions for a pset will end up as two separate uploads on Gradescope.

Partners

You are allowed to work on the problem sets individually or in pairs (no groups larger than two people). Regardless of how many people you work with, your problem set will be graded on the same scale. You are not required to work with the same people on each problem set – you're welcome to work in a pair on one problem set, individually on the next, in a pair with a different partner the next time.

For more details about collaborating with other students, please read over our Honor Code policy and our Guide to Partners.

For pairs, only one person should submit to Gradescope, and that person should then add their partner’s name. (Should you find yourself in the situation that you forget to add your partner's name, Gradescope does allow you to add it even if the due date is passed. Partners–please double-check this each week!)

Regrade Requests

We do our best in this course to grade as accurately and as thoroughly as possible. We understand how important it is for your grades to be fair and correct. If there is an error, you're encouraged to submit a regrade request on Gradescope. Regrade requests must be submitted no later than one week after that assignment/exam's grades are released. Regrade requests that are not polite or that take issue with the rubric design (as opposed to misapplication of the rubric as it is) may be closed without comment.

Late Policy

We urge you to focus on being ready for the exams by finishing the problem sets on time, even if not perfectly. In the software industry, they often say, "Shipped is better than perfect." Therefore, there are no automatic free late days or grace periods this quarter. Accomodations for unforeseen special circumstances (illness, etc) are of course available by contacting the course staff via a private/staff only post on the Ed forum.

Please note that we take the square root of your assignment scores when calculating your final grade, which has the effect of hugely raising low scores. This is our way of supporting you and meeting you halfway in this "shipped is better than perfect" philosophy, by minimizing the grade impact of imperfect or incomplete solutions.

If you need an extension, submit whatever you have before the due date/time and then contact us via a private/staff only post on the Ed forum. That way, if you hear back that your situation is not something for which we can grant a due date extension, you at least have the credit for what was done. It's always better to reach out to us about extensions and special circumstances as soon as at all possible, rather than letting us know after due dates have passed.

If you do miss a deadline and want to know if you may be excused to submit late, you must attach your submission to a post asking us. Again, do this via a private/staff only post on the Ed forum.

Honor Code Policy

Please see our Honor Code page for more information.

Exams

There will be two midterm exams. We are planning on holding exams in-person this quarter, though this is subject to change based on university guidance. The exams will run on the following days:

  • Midterm 1 is Tuesday, May 2 from 7:00PM - 10:00PM. (Week 5)
  • Midterm 2 is Tuesday, May 23 from 7:00PM - 10:00PM. (Week 8)
  • Final Exam is Saturday, June 10, 8:30AM - 11:30AM. (End of Week 10)

For exam locations and more information, see the Preparing for the Midterm page as the exam date approaches.

Please note that you are required to attend the exams as scheduled. For midterm exams, if you have a conflicting exam in another Stanford class, or a conflicting commitment such as Orchestra or Varsity athletic competition, we may be able to accommodate you, but only if you let us know before the end of Week 2. For the final exam, you must not enroll in classes with conflicting final exams. This is a University-level policy, and we do not make exceptions under any circumstances. Other conflicts, such as personal travel, internships, interviews, etc, are your responsiblity to clear so you will be available for the exams. As part of your pset0, you will be asked to fill out this form about checking for exam conflicts.

Readings

There are two recommended textbooks for this quarter. The first is How to Read and Do Proofs by Daniel Solow, which is a great resource for learning how to approach mathematical problem-solving. The second is Introduction to the Theory of Computation, Third Edition by Michael Sipser. You might find this book useful in the second half of the quarter. We will never directly test material available only in the textbooks; the course materials we provide will be all you need.

There are copies of each of these books in reserve in the Engineering Library.

A helpful note from the School of Engineering:

“All students should retain receipts for books and other course-related expenses, as these may be qualified educational expenses for tax purposes. If you are an undergraduate receiving financial aid, you may be eligible for additional financial aid for required books and course materials if these expenses exceed the aid amount in your award letter. For more information, review your award letter or visit the Student Budget website.”

Withdraw / Incomplete Policy

If a serious emergency arises and you cannot complete the work in this course, you may contact us by the staff mailing list to request an incomplete. By University policy, incompletes are reserved for unforeseeable emergencies that arise late in the quarter during which a student was otherwise performing well ("…restricted to cases in which you have satisfactorily completed a substantial part of the coursework…"), so we do not do incomplete grades for ongoing performance struggles or overloaded course schedules or busy jobs. Retaking is the appropriate option in those circumstances.

Grading

Your raw score in CS103 is determined as follows:

\[\text{Raw Score } = \quad 0.25 \cdot \text{PSet Score} + 0.70 \cdot \text{Exam Score}\text + 0.05 \cdot Max({Final Exam Score}, \text{Lecture Participation Score}).\]

Here, your problem set score is computed as

\[\text{PSet Score} \quad = \quad \frac{\text{sum of square roots of problem set scores}}{\text{sum of square roots of problem set point totals}}\text.\]

Taking the square root of each problem set score provides a boost to each problem set grade. For example, if you score an 81% raw score on one problem set, we’d count it as though you’d earned a $\sqrt{0.81} = 90$%. We do not drop your lowest problem set score, but the square root calculation does a great deal to smooth over mishaps.

Your exam score is computed as

\[\begin{aligned} \text{Exam Score} \quad = \quad &\frac{1}{6} \cdot \text{First Midterm Score (Pct)} +\\ & \frac{1}{3} \cdot \text{Second Midterm Score (Pct)} +\\ & \frac{1}{2} \cdot \text{Final Exam Score (Pct)}\text.\end{aligned}\]

Your midterm and final exam scores means percentage scores. Note that we do not curve midterm or exam scores (instead, if for some reason the exam scores are unusually low in a given quarter, we would curve the whole course upward if needed)..

Your lecture participation score is computed as

\[\text{Lecture Participation Score} \quad = \quad Min(1.0, \frac{\text{credited lectures}}{25}).\]

Credited lectures is the number of lectures that you attended in person (and did PollEv participation for) and/or completed the Gradescope video quiz for. You can choose to attend as many or as few in-person lectures as you like, but you do need to watch videos for those you miss. There are 27 lectures in the quarter, so 25 means you can entirely miss up to 2 without penalty. The 5% of course grade can also be added to your final exam if you'd rather opt-out of lecture participation entirely.

Grade Notes:

We never assign letter grades that are lower than the decile of your raw score; for example, a 90% will never map to anything lower than an A-. Historically, the median raw score has ended up somewhere near the B/B+ cutoff. If grades end up lower than that, we may "curve" upwards by letting the A- grade cutoff go down to 89% or 88%, etc. The A+ grade is a rare award to a handful of very top students, and does not kick in at any particular percentage score.

To earn a passing grade in CS103, your PSet Score and your Exam Score, as computed above, must each be passing work. (A 60% cutoff for problem sets, and 50% exams, though these may be lowered to allow more students to pass in some quarters.) If your score in at least one area is below this cutoff, you will receive a non-passing grade. This is to ensure that students take the assignments, and don't ride high assignment scores (potentially done with a partner) to pass without demonstrating independent mastery on the exams. Historically, very few students are impacted by this rule, since usually having a non-passing score in either area results in having a low overall composite score anyway.