Final Exam

Exam Logistics

• The exam is Friday, August 15, 3:30 - 6:30 PM.
• We have assigned seating, and we are using multiple exam rooms!
  • Please check this seat assignment page (Stanford login required) for your seat location. We recommend stopping by your assigned classroom to locate your seat at least one day before the exam. You'll be required to take the exam in your assigned room and seat.
  • We recommend taking a screenshot 📷 of your seating assignment in case the seating page goes kaput on the day of the exam. (That happened in Spring '24!)
• The general exam room breakdown is as follows:
  • Most people will be in 420-040.
  • Those with special circumstances (CGOE, OAE, athletic conflicts) can view the arrangements for their exam (time and place) on the seating assignment webpage linked above.
• The exam is closed-book, closed-notes, and closed-device. We will provide a printed copy of this reference sheet to jog your memory about the Stanford library functions. No additional aides are permitted.
• The exam will be proctored, and to ensure the integrity of the testing environment, the following policies and procedures will be in place:
  • You will need to take the exam in your assigned seat. See link above for details.
  • You will need to turn in your exam and present a Stanford ID when leaving the room.
  • Backpacks are not allowed at your seats. You may have a small purse or fanny pack, as long as it is tucked out of sight during the exam. Any backpacks will have to be left at the front of the classroom. To avoid the possibility of lost or stolen property, please do not bring backpack to the exam room if possible.
  • Accessing a cell phone, calculator, or other electronic device during the exam is prohibited, even to check the time. We'll make sure there's a readable clock in the classroom.
  • If you need a restroom break during the exam, you must check in with a proctor before leaving the classroom.

Motivation

The final exam is a paper-format comprehensive exam to evaluate your achievement of the learning goals for the entire CS106B course.

Coverage

The coverage is comprehensive over the entire quarter, but expect heavier concentration on content from latter half of course. Topics that figured most prominently in lecture/section/homework will likely be assessed at greatest intensity/weight, and more minor excursions will likely have correspondingly lighter attention. Here is a list of topics of high importance:

• client use of ADTs: design a data structure, demonstrate appropriate choice of ADTs, use of ADT operations to solve a problem, operational behavior of Vector, Grid, Stack, Queue, Set, Map, PriorityQueue, HashSet, HashMap, Lexicon
• algorithm analysis / Big-O: analyze a piece of code and answer questions about its runtime complexity, write code that solves a problem within a given Big-O limit, demonstrate knowledge of the Big-O runtime for standard algorithms and ADT operations
• recursion, recursive backtracking: use recursion or backtracking to solve a problem
• searching and sorting: demonstrate knowledge of algorithms for linear search, binary search, selection sort, insertion sort, mergesort and quicksort
• implementing ADTs/classes: implementation choices for standard ADTS (e.g. set/map as BST or hash table; stack/queue as linked list or dynamic array, vector as dynamic array, priority queue as sorted array or min heap); write ADT using alternative implementation, extend ADT with additional operations, discuss implementation tradeoffs in terms of design, Big-O efficiency, code complexity
• heaps: trace operations to insert/remove elements into binary minheap or maxheap, write code to implement binary heap operations; be sure you're familiar with how the array representation of minheaps works
• pointers and dynamic memory management: read/write code that uses pointers, most likely in context of dynamic arrays, linked lists, or trees, show understanding of correct use of dynamic memory including allocation/deallocation, be familiar with references to pointers; you could be asked to detect and/or fix memory leaks (orphaned memory) or draw diagrams representing the state of memory at various stages of execution of some chunk of code
• linked lists: trace operations on a linked list, write code to create/traverse/modify linked lists, either singly or doubly-linked
• binary trees: trace operations on a binary search tree (BST), write code to traverse/manipulate trees, understand tree traversals conceptually
• encoding trees: trace operations on encoding tree, huffman algorithm, write code to operate on encoding tree
• graphs: understanding of graphs data structure and implementation options (adjacency matrix vs adjacency list – implementation details, pros and cons, when to use one over the other), trace simple graph algorithms (breadth-first and depth-first search) (could you implement these?), topological sort (identify whether an ordering of vertices is a valid topological sort or not) (what sort's of problems could we solve with topological sort?), translating real-world problems into graphs (what would a node represent? what would an edge represent? what problem would we solve in the graph in order to solve the real-world problem: find shortest paths? finding a topological sort? something else?)
• hashing: simulate operations on a hash table that resolves collisions by linear probing or separate chaining, show understanding of simple hash function, understand properties of good hash functions, know runtimes for insertion and search (best-, worst-, and average-case, as well as what leads to each of those cases)

Take care to be familiar with the syntax for the following, which will not be included on your reference sheet:

• Syntax for using new and delete for objects, structs, arrays, and primitive data types such as int and char. Recall that when deleting an array, we use delete [] array and not just delete array. Be familiar also with how to declare appropriate pointer variables to use in conjunction with new.
• Syntax for defining the member functions for some class. In particular, recall the need for ClassName:: when defining a member function in a .cpp file.
• Syntax for accessing members of a struct or class. Be familiar with the distinction between the dot (.) and arrow (->) operators.

Format

Questions included on the final exam will generally fall into one of the types below. The practice exams show examples of various problem formats.

• code writing: write code to implement a function, class, or program that solves a specified task
• code reading: review a given code passage and reason about its behavior, analyze big-O runtime, or show output
• trace/diagram: trace the operation of an algorithm or diagram a data structure
• short answer: short prose answers to conceptual questions

Practice Exams and Other Resources

We have curated a collection of additional section problems (with solutions) to give more practice with core course concepts:

• Extra Practice Problems (Post-Midterm)

We have also assembled the following collection of practice exams for you to refer to as you prepare for the final. These are actual exams given in recent quarters, and they should be fairly representative of what you can expect on your exam in terms of scope, content, difficulty, and format. We strongly recommend setting aside at least one of these exams to use as a practice exam where you sit down in a quiet, distraction-free environment and try to complete it in a three-hour block with no breaks and no reference materials (other than the official reference sheet that we will provide you with for this exam).

• Higher priority practice exams:
  • Practice 4 and solution
  • Practice 5 and solution
  • Practice 6 and solution
  • Practice 7 and solution
• Lower priority practice exams:
  • Practice 1 and solution
  • Practice 2 and solution
  • Practice 3 and solution

We have also prepared a review sesion (passcode: @U.33chG) for this exam. More information, including the review problems with their solutions, can be found on this page.

Additional practice resources include:

• Be sure to work through all lecture quizzes.
• Work the exam prep section at the bottom of each page of lecture notes.
• Revisit our section materials. We pack each weekly section handout with many more exercises that fit in the section meeting, so there are plenty of good options there. Many section exercises are similar size and scope to those we use for exams. (In fact, many section exercises originally appeared on exams in previous quarters).
• The exercises in the textbook are another great source for practice.
• The online coding practice site Code Step By Step has been recommended by past students as a useful tool. It offers many practice problems and autogrades your answers to give immediate feedback.

Advice

We absolutely want you to come out on top! The lectures, sections, and assignments work together to guide you toward mastery of the course learning goals and the exams serve as an assessment of your progress. The absolute best outcome everyone has a great grasp on the material to nail the exam.

Read on for our advice on how to make that happen for you!