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, functions, graphs). 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 the biggest open problem in math and computer science, the P = NP problem.

Teaching Team

You can reach us at cs103-spr2324-staff@lists.stanford.edu, or on the Q&A forum Ed Discussion (us.edstem.org. Feel free to reach out to us with questions on any topics - course logistics, problem set questions, life advice, you name it!

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:

• Our main course website cs103.stanford.edu is the main hub for course information. It contains links to everything you’ll need.
• We use Canvas to host lecture videos.
• You’ll submit work using GradeScope
• We use Ed as our Q&A forum.
• You will need to download and install Qt Creator to complete the coding assignments.
• You may find it helpful to use Overleaf to typeset your problem sets. (Your @stanford.edu email address gives access to “Pro” features.)

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!

Lectures

Our lectures are Mondays, Wednesdays, and Fridays from 3:00PM - 4:20PM in Bishop Auditorium. Lectures will be recorded and posted on the course Canvas page.

It's important to keep pace with the lectures rather than to batch them up and watch them all in one go. (That model works great for Netflix shows that really hook you in, but it's not great for learning.) To give you an incentive to stay on top of lectures, we've reserved 5% of your grade for lecture participation in a way that can only help and not hurt your grade. Here's the details:

• Starting on Wednesday, April 10th, we'll ask a small number of practice questions through the PollEV polling system. If you attend lecture in person and answer those questions, you'll earn participation credit for the day regardless of whether your answers are correct.

• If you aren't able to make it, simply watch the video on Canvas and answer a few questions on Gradescope so we know you're up to speed. Unlike practice questions we do in class, you do need to answer these correctly to earn that day's credit. But Gradescope will give you the chance to retry questions you miss. These make-up questions need to be completed before the start of the next lecture (i.e., Monday lecture questions submitted before the start of Wednesday's lecture) to earn credit.

To allow for some flexibility, you're allowed to miss the credit opportunity (i.e. not completing PollEV or Gradescope quiz) for three lectures over the course of the quarter and still earn the full 5%.

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.

CS103 ACE

CS103 ACE 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 CS 103 ACE, you can apply online here.

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 3:00PM Pacific time.

Submitting Work

This quarter, we will be using GradeScope to handle problem set submissions and grading. Your enrollment should automatically sync with Axess.

You can submit your assignments by uploading them to GradeScope. You are responsible for the correctness, completeness, and timeliness of your submission to Gradescope. That means you need to allow plenty of time before the deadline for tagging each problem, for any hiccups in the process, and for double-checking to catch errors such as uploading the wrong file, forgetting your partner’s name, not tagging each problem correctly, etc.

GradeScope only accepts electronic submissions. Because in the past we’ve had issues with low-resolution scans of handwritten work, you are required to type your assignment solutions and submit them as a PDF; scans of handwritten solutions will not be accepted. $\LaTeX$ is a great way to type up solutions.

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, etc. If you do work in a pair, please note that both members of the pair are responsible for ensuring that each assignment is completed and submitted on 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. We rely on GradeScope for our final grading spreadsheet, so we need your partner entry to be accurate. Partners—if you aren’t the one submitting, double-check the Gradescope submission yourself in case there was some mistake such as your partner uploaded the wrong file or forgot to add you.

How We Grade

When grading assignments, we will grade both for intuition and for execution. When looking for execution, we will check whether your reasoning is correct, whether you prove the desired result, whether all your intermediary steps are valid, etc. If your proofs contain logical errors or prove statements other than the ones you needed to prove, we may deduct points for correctness. We will also grade your proof based on how clearly it lays out its argument and whether it adheres to the standard mathematical conventions governing proofwriting. If your proof proceeds on unnecessary tangents, doesn't clearly articulate where it's going, uses unnecessarily cryptic notation or shorthand, etc., then we may deduct points. We'll release more information about our proofwriting standards over the quarter.

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 contact the course staff and ask for a regrade. However, please understand that regrades are only for errors in grading, not that you disagree with the grading standards or rubric. The same rubric is applied to all students, so all students lose the same number of points for the same errors. Regrade requests must be submitted no later than one week after grades are released.

Late Policy

We understand that you have a lot going on in your life outside of CS103. To provide you some additional flexibility with due dates, every student in CS103 begins with three free late days. Each late day can be used to automatically extend the deadline on one of the assignments by 24 hours. Only one late day can be used per assignment, so you can think of this as a way to pick three assignments and give yourself an extra 24 hours on the deadline without penalty.

You do not need to let us know in advance if you are using your late days. GradeScope will automagically record your submit times, and we'll count it as if you've used a late day if you submit past the deadline.

If you are out of late days and submit past the deadline, we will still accept your submission, but we will apply a small penalty. Specifically, we will multiply your score by 0.7. It is still better to submit something late than to not submit at all.

Late days are per-person rather than per-partnership. If you submit late with a partner, both you and your partner will be charged a late day. If you are out of late days and your partner is not, you should be sure to communicate this to them to avoid unpleasant surprises.

No submissions will be accepted more than 24 hours past the due date without prior approval by the course staff. If you need an extension beyond the standard 24 hours, please email cs103-spr2324-staff@lists.stanford.edu. Extension requests must be received at least 24 hours before the assignment due date. Please do not send extension requests through other channels (e.g. directly emailing the instructor, posting on EdStem, etc.); use the staff mailing list instead.

Honor Code Policy

Please see our Honor Code page for more information.

Exams

There will be two midterm exams. The exams will run on the following days:

• Midterm 1 is on Tuesday, April 30th from 7:00PM - 10:00PM.
• Midterm 2 is on Tuesday, May 21st from 7:00PM - 10:00PM.

The final exam will be on Saturday, June 8th from 8:30AM - 11:30AM. We can only offer alternate final exams for students with documented OAE accommodations. If you cannot make the final exam, you will need to take CS103 in a different quarter.

All exams are in-person, pencil-and-paper exams. All students, except for SCPD students, are expected to be on campus for the exams.

SCPD students will take the exams remotely with their exam administered by their exam monitors. SCPD students may start the exam any time in the 24-hour window before the regularly-scheduled exam time. For example, an SCPD student may start the first midterm exam any time between Monday, April 29th at 7:00PM Pacific and Tuesday, April 30th at 7:00PM Pacific.

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 Alex and Keith – not the TAs – to request an incomplete. We reserve incompletes for emergencies, so we do not grant incomplete grades for poor performance on the assignments or exams, nor do we offer incompletes for busy work schedules. Withdrawing is the appropriate option in those circumstances.

In order to be eligible for an Incomplete, University policy says you must have completed a “substantial” part of the course work in “satisfactory” fashion. This means that incompletes are appropriate for serious medical or family emergencies that occur late in the quarter, which prevent you from completing the course despite having done well up to that point.

Grading

Your raw score in CS103 is determined as follows:

\[\text{Raw Score } = \quad 0.20 \cdot \text{PSet Score} + 0.75 \cdot \text{Exam Score} + 0.05 \cdot \text{Participation Score}\text.\]

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 90%. We do not drop your lowest problem set score; it is better to submit something largely incomplete than to submit nothing at all.

Your exam score is computed as

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

Your midterm and final exam scores are computed using raw percentage scores. Note that, in particular, this means that we do not curve midterm or exam scores.

Your participation score is computed as follows. First, we compute the fraction of lectures for which you either attended in person and answered PollEV questions (regardless of correctness) or where you answered questions on GradeScope correctly. (You are allowed to miss three lectures without penalty._ Second, we compute your final exam score. We then take the maximum of these two as your participation score. For example, if you attend every lecture and participate on PollEV, then your participation score is 100%. If you never attend lecture but always answer the quiz questions on GradeScope correctly, your participation score is 100%. If you never respond to PollEV questions and don't do the GradeScope quizzes and score 70% on the final exam, your participation score is 70%.

We assign letter grades as follows. We first determine a grading curve over raw scores to assign initial letter grades. Historically, the median raw score has ended up somewhere near the B/B+ cutoff. 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-.

There is one exception to this rule. To earn a passing grade in CS103, your PSet Score and your Exam Score, as computed above, must each be passing work. (The actual numbers used to denote “passing work” are set at the discretion of the instructor. We will likely use 60% as a cutoff for passing work for problem sets and 50% as a cutoff for passing work for exams, though this is subject to change.) If your score in at least one area is below this cutoff, you will receive a non-passing grade. This rule is to ensure that you have demonstrated competency throughout the quarter. 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.

Your final grade will be determined solely as mentioned above. We do not offer any make-up work.