Written by Nick Troccoli, Jerry Cain and Lisa Yan, based on documents by Julie Zelenski and others

Date/Time:

Friday, December 16th, 8:30-11:30AM

Location: CEMEX Auditorium

Review Session: Wed. 12/14, 8-9PM (Zoom, link here). Video recording here, slides here.

Overview

The final exam will be held during our registrar-scheduled exam time: Friday, December 16, 8:30AM-11:30AM. For the final exam, there will be __no alternate time, except for those with relevant official university athletics or Office of Accessible Education accommodations, so please make sure that you can attend the final exam at the specified time before enrolling in the class.

The exams are designed to assess your mastery of the course learning objectives, with a particular emphasis on material that was prominent in the lectures, assignments and labs.

The exam is closed-book. You may bring a double-sided US-Letter-sized (8.5"x11") page of your own prepared notes. The exam will include a digital and physical reference sheet of essential details such as prototypes for system calls (e.g., waitpid, fork, execvp).

You will take your exam electronically, using our custom BlueBook exam software (same as the midterm), which you can run on your computer if you have one. BlueBook is a full-screen exam-administration application that provides syntax highlighting capabilities but does not provide the ability to run code. If you do not have access to a laptop for the exam that can run BlueBook, please contact the course staff. You cannot access digital notes, run other applications (such as Terminal or other myth SSH tools), use the Internet, nor use any other electronic devices during the exam.

Please make sure to thoroughly read all information contained on this page to ensure you understand the midterm logistics, requirements and restrictions.

Logistics

The exam is closed-book. You may bring a double-sided US-Letter-sized (8.5"x11") page of your own prepared notes. The exam will include a digital and physical reference sheet of essential details such as prototypes for system calls (e.g., waitpid, fork, execvp).

Course staff will be proctors at the exam to answer clarification questions.

You will take your exam electronically, using our custom BlueBook exam software, which you can run on your computer if you have one. BlueBook is a full-screen exam-administration application that provides syntax highlighting capabilities but does not provide the ability to run code. If you do not have access to a laptop for the exam that can run BlueBook, please contact the course staff. You cannot access digital notes, run other applications (such as Terminal or other myth SSH tools), use the Internet, nor use any other electronic devices during the exam.

We know that BlueBook is not the same as working with a compiler as you do on Myth, and we account for that in how we design and grade the exam. We are assessing your ability to think logically and use appropriate problem-solving techniques. We expect you to express yourself in reasonably correct C/C++, but we will be lenient with errors that are syntactic rather than conceptual.

If you already have BlueBook downloaded from the midterm, you're all set. Otherwise, see the downloads section below for how to download and use BlueBook.

Unlike the assignments, the exam is strictly individual work.

During the exam, you may use/reference:

• a double-sided US-Letter-sized (8.5"x11") page of your own prepared notes.
• a provided reference page of essential details such as prototypes for standard library functions (e.g., waitpid, fork, execvp). This is included digitally in the exam.
• provided blank scratch paper (we will provide this at the exam)

You are not permitted to use any other materials, such as printouts (notes, slides, code, practice exams, etc.), other textbooks, or electronic devices (iPads, Kindles, calculators, music players, etc.) other than using your computer, which must be used solely to run the BlueBook software.

The exam may be a mix of short answer, multiple choice, code reading, code writing, etc. questions.

If you want to try out a BlueBook exam, there is a Practice BlueBook exam listed in the practice materials below.

Material Covered

The final is intended to assess your understanding of the content covered throughout the course. The priority is on material that figured prominently in the assignments, sections, and lecture. The topic coverage for the final exam will be comprehensive and span the entire quarter, but expect more emphasis on material covered after the midterm (i.e. >= section4 and assign4, since assign4 was only lightly covered on the midterm). In particular, we highly recommend revisiting the sections and assignments!

We'd love to see the discussion forum come alive in helping everyone do their best on the exam – this is a great place to ask and answer unresolved questions, discuss conceptual issues, share techniques and materials you are finding useful as preparation, and support and encourage each other.

Topics Summary

Check your rear-view mirror for the very impressive list of things you've learned in 111! Here's a list of main topics (not fully exhaustive):

• Filesystems: filesystem design and tradeoffs, internal vs. external fragmentation, contiguous allocation, linked files, FAT, multi-level indexes, Unix V6 (inodes, direct, single-indirect and doubly-indirect addressing, directories, lookup), block cache and delayed vs. synchronous writes, locality, free list (linked list or bitmap)
• File I/O: file descriptors, file descriptor table, open file table, open/close/read/write, STDIN / STDOUT / STDERR
• Crash Recovery: tradeoffs, data loss and inconsistency, atomic operations, free list and block cache, fsck, ordered writes, write-ahead logging, transactions, checkpoints, idempotency, durability and consistency
• Multiprocessing: processes, PIDs, fork, execution order, copy on write, waitpid, zombie processes, execvp, pipes and pipe / pipe2, I/O redirection
• Multithreading: processes vs. threads, C++ threads and .join(), thread safety, race conditions, atomicity, critical sections, mutexes, deadlock, busy waiting, condition variables, notify_one and notify_all, unique_lock, monitor pattern
• Dispatching / Scheduling: Process control blocks, traps and interrupts, context switching, thread state (running / blocked / ready), scheduling algorithms, first-come-first-serve, round robin, shortest remaining processing time, priority-based scheduling, preemption, interrupts, implementing locks and condition variables
• Virtual memory: single-tasking, process memory, memory sharing goals, load-time relocation, dynamic address translation and MMU, virtual and physical addresses, base and bound, multiple segments, paging, demand paging, page maps, page faults, thrashing, fragmentation, disk swap, page replacement policies, random replacement, FIFO replacement, LRU replacement, clock algorithm, per process vs. global replacement, virtualization.

What To Bring

The exam is on your computer. You should bring:

• Your laptop and charger
• The device you use for two-step authentication
• your physical double-sided page of notes
• A power strip/extension cord (optional, but recommended if you have access to one)

Honor Code

The exam is to be completed individually and without any assistance from a partner or other students. Follow the Stanford Honor Code (see link on main course homepage) during the exam: submit only your own work, do not use unpermitted aids on the exam, and say something to the instructors or students in question to prevent any inappropriate activity conducted by others surrounding the exam.

Grading

(Same as midterm exam)

For coding questions, the majority of the points are typically focused on the correctness of the code. However, there may be deductions for code that is roundabout, awkward or inefficient when more appropriate alternatives exist. We will reward the simple, direct approach for its good design decisions and such code will likely have fewer correctness issues, so the choice of appropriate design can have a large impact. For example, we expect you to leverage appropriate features from the standard libraries; re-implementing that functionality wastes your valuable time and introduces opportunity for error.

Note that certain problems may have certain constraints (such as only using certain material, etc.) that you must follow to earn full credit. These constraints are not intended to make things difficult; typically, we are trying to guide you in the direction of a more straightforward solution. If you disregard these instructions, you are likely to lose points, either for not meeting the problem specification and/or for errors introduced when attempting a convoluted alternative. We reserve the right to deduct points for extremely inelegant or inefficient code that dodges the spirit of the problem.

• You are not required to write #include statements. Please do not abbreviate any code (such as writing "x2" next to code to copy it twice). Abbreviated code will not be graded.
• Pseudo-code (writing English sentences and phrases instead of code) will typically earn little to no points. For example, writing "In this part of the code, I want to open the file and read each line and print it" will not earn any points.
• You should include your answer, as well as any scratchwork, in the text area for each problem. An answer to a problem not in the designated answer pages for that problem will not receive any credit.
• Unless otherwise specified, it is fine to write helper functions to implement the required behavior.
• Style and decomposition are secondary to correctness. The correctness of the answers dominates the grading. Decomposition and style are thus somewhat de-emphasized. However, good design may make it easier for you to get the functionality correct and may require less code, which takes less time and provides fewer opportunities for error. Comments are never required unless specifically indicated by a problem. When a solution is incorrect, commenting may help us determine what you were trying to do when we attempt to give partial credit.
• We are lenient on syntax. We won’t trouble you about most small syntax errors (forgetting semicolons or spaces, for example) as long as your intentions are clear. Having said that, beware that if your syntax errors cause ambiguity (e.g. very unclear curly braces), we might not get the correct meaning.
• The majority of the points for a problem will be reserved for grading the critical core of the code. For example, if we ask you to write a function that iterates over an array and spawns child processes, only a tiny fraction of the points will be allocated to tasks such as iterating over the right bounds, while the bulk of the points will be gained or lost in the tricky details of whether you correctly handle the processes. Be sure to focus your attention accordingly!

Downloads

BlueBook Download / Usage Instructions

Exam Reference Sheet:

PDF
Note: the reference sheet is included as the last "problem" in the BlueBook exam. You will be provided with a hard copy as well during the exam.

Practice Materials:

Guide for how to approach and succeed on CS111 exams.

Practice 1: BlueBook | PDF | Solutions
Password: pagefault
This exam is the same length as the exam given this quarter (3 hours). Note: the practice BlueBook exam is configured with an infinite time limit. You cannot close BlueBook and come back to work on the exam later - you must complete it in one sitting. If you'd like to check your answers, leave BlueBook open while you do so. You may submit the practice exam when you're finished if you'd like to see the submit process, but it will not be accessible anywhere. Note that for security reasons, BlueBook disables copy/pasting into or out of BlueBook. You can copy/paste within BlueBook, however.

The practice exams below were taken from prior quarters of CS110 and CS111, and administered for varying lengths of time. Not all problems are relevant to the material covered this quarter - the notes below each exam indicate which problems cover CS111 material this quarter. Also note that some of these are the same as materials given on the midterm exam webpage, with new problems noted below each exam. The midterm page has further practice materials as well!

CS110 Practice Midterm 1: PDF | Solutions
This practice midterm was provided previously, but you can now solve problem 4b.

CS110 Practice Midterm 2: PDF | Solutions
This practice midterm was provided previously, but you can now solve problems 2c and 2d.

CS111 Spring 2021 First Midterm: PDF | Solutions
This practice midterm was provided previously, but you can now solve problems 1d, 1e, and 6. Problem 6 is used in the BlueBook practice exam.

CS111 Spring 2021 Second Midterm: PDF | Solutions
Relevant problems: 1 (1c provided previously), 3, 5. Problem 1b is used in the BlueBook practice exam.

CS140 Practice Final Exam: PDF | Solutions
Relevant problems: 1b, 1d, 1e, 5a, 5b, 6, 8b, 9. Problems 1b, 1d, 1e, 5a, 5b, and 6 are used in the BlueBook practice exam.

CS110 Practice Final 2: PDF | Solutions
Relevant problems: 4b, 4c

CS110 Practice Final 3: PDF | Solutions
This practice final was provided previously, but you can now solve problems 4a and 4e. Problems 4a and 4b are used in the BlueBook practice exam.