Assessment 2. End-quarter exam

Motivation

For the end-quarter final exam, we use a traditional format comprehensive exam to evaluate your achievement of the learning goals for the CS106B course.

Logistics

  • The exam is Monday December 12 8:30am-11:30am.
  • Locations are assigned by first letter of your surname/family/last name.
    • If your last name falls between Aalami-Hekmat, you'll be in Cemex Auditorium
    • If your last name falls between Heng-Zu, you'll be in in Dinkelspiel Auditorium
    • Students with special circumstances (SCPD, OAE) will receive an email from Head TA Neel with your arrangements.
  • You will write your answers directly on the paper exam.
  • The exam is closed-book and closed-device.
    • We will provide a reference sheet to jog your memory about the Stanford library functions.
    • You also may bring your own prepared notesheet.
      • The notesheet is one sheet of letter-size paper (8-1/2" x 11") where you have written/printed/drawn on both sides with whatever information you would like to have handy during the exam.

Coverage, sample/practice materials

  • 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 be assessed at greatest intensity/weight, and more minor excursions will 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 min-heap or max-heap, write code to implement binary heap operations
    • pointers: 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
    • 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
    • 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), trace simple graph algorithms (breadth-first and depth-first search)
    • hashing: simulate operations on a hash table that resolves collisions by chaining, show understanding of simple hash function
  • Format. Questions including on the final exam generally fall into one of the types below. The sample shows 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. Here is a practice final and solution. This was the actual exam given in a recent quarter and should be mostly representative in scope, content, difficulty, and format to what you can expect on our exam.
  • Further practice exercises
    • 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. 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.
    • We're hosting two review sessions next week (one solely focused on recursive backtracking and one general review session). See our pinned Ed post with final exam logistics for more info.

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!