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, we like to think of this as a course in both art appreciation and practice. We’ll bring you through a gallery and show you some of our 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
Our talented course staff is super excited to share our love for CS103 material with you. We encourage you to get in touch with us through the course EdStem forum. Ed is the best place to contact us with questions on any topic - course logistics, problem set questions, life advice, you name it! When appropriate to protect your privacy or avoid sharing assignment solutions with other students (an honor code violation!), you can mark your post as private and only staff will be able to view it. We ask you to email sensitive matters only and please use the private setting on Ed more often. Posting on Ed allows both of us to answer - and you get quicker response time!
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 Panopto to host lecture videos.
- You’ll submit work using Gradescope.
- We use EdStem 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 you'll need as a prerequisite is high-school algebra. We'll build up all the remaining mathematical machinery you 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 TTh 4 - 6:30 PM in CoDa B80. Lectures will be recorded and posted on the course Canvas page.
It's important to keep pace with the lectures. If you are not a CGOE student, the expectation is that you'll be in class. If there's some reason you cannot be, please email Robyn to discuss an alternate plan. With an abbreviated quarter, and the midterm often being one of the only ways students find out whether they're doing well or not, it's important that students attend class to deepen their learning and stay on top of the material.
Thus, please email Robyn if you're going to miss class for a valid reason. Additionally, we will track attendance via PollEV. We've reserved 5% of your grade for lecture participation, and starting Week 2, in lecture we'll ask a small number of practice questions through the PollEV polling system. You will earn participation credit if you answer those questions, regardless of whether your answers are right.
To allow for some flexibility, you're allowed to miss the credit opportunity (i.e. not completing PollEV) for three lectures over the course of the quarter and still earn the full 5%. If you are unable to attend class for a valid reason, you will also have the option to instead count your final exam score in place of your lecture participation grade.
If you are a CGOE student, then we will drop the participation portion of your grade when computing raw scores, renormalizing the remaining 95% of your grade back up to 100%. However, when calculating final letter grades, we will ensure this does not place you at a disadvantage compared to those who were able to earn participation credit through PollEV.
Lecture Recording Legal Notice
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.
Units
If you are an undergraduate or are taking this course through CGOE, 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.
Problem Sets
There will be eight total problem sets in CS103, given out once per week. With the exception of the first PSet 0 (due the first Friday at 1:00 PM), Problem Sets will be posted on Thursday afternoons and are due the following Thursday at 1:00 PM Pacific time. (Although there is therefore an assignment that overlaps with the weeks of our exams, rest assured they will be lighter than usual and have additional flexibility.)
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!)
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 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 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 (other than OAE) 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 the Head TA Joyce Lu. Extension requests must be received at least 24 hours before the assignment due date, or they will be automatically rejected. Please do not send extension requests through other channels, or they might be missed.
Honor Code Policy
Please see our Honor Code page for more information about the Honor Code as it applies in CS103.
Please see this additional information about the honor code.
Exams
There will be one midterm and one final exam. The exams will run on the following days:
- Midterm is Tuesday, July 21 from 3:00 - 6:00 PM. (End of Week 4)
Please make every effort to make the midterm, as we will not be giving an alternate midterm. Therefore, if you cannot make this particular day, you may want to take the class in the fall.
- Final Exam is Saturday, August 15 from 3:30 - 6:30 PM.
Please note that you are required to attend the exams as scheduled. The final exam date is set by the Registrar. Note that 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.
CGOE students will receive information over email about taking the exams remotely.
Proctoring Pilot
This course is participating in the proctoring pilot overseen by the Academic Integrity Working Group (AIWG). The purpose of this pilot is to determine the efficacy of proctoring and develop effective practices for proctoring in-person exams at Stanford. To find more details on the pilot or the working group, please visit the AIWG's webpage and read this document.
Exam-Related Accommodations
IMPORTANT OAE DEADLINES: If you plan to use your OAE approved exam accommodations for a specific assessment, students must provide their accommodation letter and inform the instructor by 10 calendar days prior to an exam. The deadline for requesting OAE accommodations for the final exam is July 31st, by 5pm.
You only need to submit your letter once per quarter. For urgent OAE-related accommodation needs that arise after the deadline, please consult your OAE adviser. If you are not yet registered with OAE, contact the office directly at oae-contactus@stanford.edu.
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{7}{15} \cdot \text{The Higher of Your Exam Percent Scores } +\\ & \frac{5}{15} \cdot \text{The Lower of Your Exam Percent Scores } +\\ & \frac{3}{15} \cdot \text{Your 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
\[\text{Participation Score} \quad = \quad \min \left\{1, \frac{\text{number of lectures where you answered PollEV}}{\text{number of lectures with PollEV questions} - 3}\right\}\]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 are two exceptions to this rule. First, A+ grades are given only sparingly and at the discretion of the instructor, not with regard to raw course grades. Second, to earn a passing grade in CS103, your PSet Score and your Exam Score, as computed above, must each be passing work. (The numbers used to denote “passing work” are set at the discretion of the instructor at the end of the quarter, after all assessments have been graded and we have a full view of everyone’s performance in the course available for review. As a rough estimate, we expect these cutoffs will be somewhere around 60% for passing work for problem sets and somewhere around 50% for passing work for exams. However, we retain final authority to set those cutoffs as we see fit when assigning letter grades at the end of the quarter. The final cutoffs might be higher or lower than the numbers listed here. The final cutoffs will be applied equitably to all students; i.e., we will not choose one cutoff for some students and a different cutoff for others.) If your score in at least one area is below that area’s 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.
Withdraw / Incomplete Policy
If a serious emergency arises and you cannot complete the work in this course, you may contact Robyn – not the TA – 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.
Time Is of the Essence
We require timely notification if any circumstances arise that impact your ability to meet the requirements, deadlines, and expectations of the course in a way that our late assignment submission policy does not already accommodate – generally in advance of any impacted deadlines (including exam dates).
Generally speaking, we ask that you treat this course as you would any professional obligation. Think of project deadlines and exam dates the same way you would think of big project deadlines at work: if it became clear you weren't going to be able to meet such a deadline, or if you weren't going to have a presentation ready in time for a big quarterly staff meeting, your manager would want to know about that well in advance.
Access and Academic Accommodations
Stanford is committed to providing equal educational opportunities for disabled students. Disabled students are a valued and essential part of the Stanford community. We welcome you to our class and look forward to supporting you!
If you experience disability, please register with the Office of Accessible Education (OAE). Professional staff will evaluate your needs, support appropriate and reasonable accommodations, and prepare an Academic Accommodation Letter for faculty. To get started, or to re-initiate services, please visit oae.stanford.edu.
If you already have an Academic Accommodation Letter, we invite you to share your letter with us. Academic Accommodation Letters should be shared at the earliest possible opportunity so we may partner with you and OAE to identify any barriers to access and inclusion that might be encountered in your experience of this course. Please email a copy of your letter to the Head TA Joyce Lu.
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.”
Force Majeure
A note from the Center for Teaching and Learning:
Stanford as an institution is committed to the highest quality education, and as your teaching team, our first priority is to uphold your educational experience. To that end we are committed to following the syllabus as written here, including through short or long-term disruptions, such as public health emergencies, natural disasters, or protests and demonstrations. However, there may be extenuating circumstances that necessitate some changes. Should adjustments be necessary we will communicate clearly and promptly to ensure you understand the expectations and are positioned for successful learning.