Assessment 2. Final Exam

Motivation

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

Logistics

  • The final exam will be on Monday, December 9th from 8:30-11:30AM.
  • Locations are assigned by first letter of your surname/family/last name.
    • A - Hof: Bishop Auditorium
    • How - Rej: Dinkelspiel Auditorium
    • Rev - Wu: CEMEX
    • Xi - Z: 260-113
  • Students with special circumstances (SCPD, OAE, athletic conflicts) will receive an email from Head TA Jonathan with your arrangements. If you do not receive an email by the end of Wednesday, Dec 4, reach out to Jonathan immediately because your situation is not in our records, and room reservation and staffing arrangements often do not allow us to accommodate late requests.
  • The exam will be taken on paper.
  • The exam is closed book. You can bring a one-page note sheet, which must be handwritten (no computerized printing allowed). Note that this is 1 individual piece of paper, 2 total sides of notes allowed. You are not allowed to bring in any magnifying devices.
  • There will also be this reference sheet, as well (note: you can ignore the Lexicon class, as we did not cover that this quarter.)

Coverage

  • 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
    • 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
    • hashing: simulate operations on a hash table that resolves collisions by chaining, show understanding of simple hash function
    • graphs: understanding of graphs data structure and implementation options (adjacency matrix vs adjacency list), trace simple graph algorithms (breadth-first, Dijkstra, A-star)
  • 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

Study Materials

  • Practice Exam 1. To give a representative sample, we have provided an actual CS106B final exam from recent quarter. You can find the sample here. Here are the solutions.
    • We strongly recommend that you practice on the sample as if it were the real thing.
  • Practice Exam 2. Here is a second past CS106B final exam. Here are the solutions.
  • Practice Exam 3. Here is a third past CS106B final exam. Here are the solutions.
  • Additional Practice Problems
    • Here is a set of more practice problems you can work through.
    • 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.

Final Thoughts

✨We want you to do well on this exam.✨

See this as an opportunity to show what you've learned and display your great efforts in the class. Always remember why you are here! Your efforts to build practice skills and real understanding will take you a lot further than a pristine transcript. If you work hard toward mastery and feel good about your understanding of computer science that is an achievement to be proud of—regardless of how many points you get relative to the other students in the course. You've put in tremendous effort this quarter – we look forward to seeing your knowledge and growth on full display!