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

Teaching Team

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. You can also reach us by email at cs103-sum2324-staff@lists.stanford.edu. 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:

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.

OAE Accommodations

We are committed to meeting all OAE disability accommodations. At your earliest convenience, please send your letter to our staff email list cs103-sum2324-staff@lists.stanford.edu. More generally, feel free to contact us at any time with questions about your accommodations.

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 eight total problem sets in CS103, given out once per week. They will be posted on Friday afternoons and are due the following Friday at 6:00PM Pacific time. (Although we do therefore have an assignment that overlaps with the weeks of our exams, rest assured they will be lighter than usual and/or have easier 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. Thus we will only grant accommodations in the case of unforeseen special circumstances (illness, etc) - please contact the course staff via email if this applies to you.

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.

Gradescope will not accept late submissions (though it does allow you to add a forgotten partner’s name after the deadline, in case you ever find yourself in that situation). If your group needs an extension on a problem set due to extenuating circumstances, you will need to email your PDF and extension request to the course staff email cs103-sum2324-staff@lists.stanford.edu. (Please do not email individual instructors/TAs as we have a centralized system for processing.) Emergencies exempted, all requests for extensions must be received at least 24 hours in advance of the posted due date.

Honor Code Policy

Please see our Honor Code page for more information.

Exams

There will be one midterm and one final exam. 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 is Friday, July 26 from 5PM - 8PM. (End of Week 5)
  • Final Exam is Saturday, August 17 from 7PM - 10PM. (End of Week 8)

Please note that you are required to attend the exams as scheduled. For the midterm exam, if you have a conflicting exam in another Stanford class or other conflict such as personal travel, internships, interviews, etc, we may be able to accommodate you but only if you let us know before the end of Week 2. 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.

SCPD students will receive information over email about taking the exams remotely.

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:

\[\begin{aligned} \text{Raw Score } = & \quad 0.4 \cdot \text{PSet Score} \\ & + 0.2 \cdot \text{Midterm Score} \\ & + 0.35 \cdot \text{Final Exam Score} \\ & + 0.05 \cdot \text{Lecture Participation Score} \end{aligned}\]

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}}.\]

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.

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.

Lecture Participation

Because we have historically observed better learning outcomes in students who keep up with regular lecture attendance, a portion of your grade will come from lecture participation. Lectures are held in person on Mondays, Wednesdays, and Fridays. Lecture attendance/participation is recorded via Poll Everywhere. Students who submit answers to all questions during a lecture (regardless of response correctness) will receive credit for attending that lecture. For students taking the course remotely, each lecture will have participation questions on Gradescope that you can complete asynchronously as you watch the lecture recordings.

If you are ill, in COVID-19 isolation, or have other extenuating circumstances and cannot attend lecture on a given day, we will permit 4 excused absences across the quarter - you do not need approval from the course staff for these 4 absences. Beyond these 4 absences, we will grant additional excused absences only in cases where you have already used your 4 excused absences for extenuating circumstances and further extenuating circumstances necessitate additional accommodations. Please do not hesitate to reach out to the course staff or the instructor if any personal circumstances or issues arise!

You may also choose to opt-out of lecture participation entirely, in which case the 5% of your overall grade allocated to participation will go to your final exam, giving the following alternate grading breakdown:

\[\begin{aligned} \text{Raw Score } = & \quad 0.4 \cdot \text{PSet Score} \\ & + 0.2 \cdot \text{Midterm Score} \\ & + 0.4 \cdot \text{Final Exam Score} \end{aligned}\]

Grade Notes:

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 composite score on the problem sets and your composite score on the exams 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.