Assessment 2. Final Exam

Exam Download files

Please click here to access the exam file download page

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 Friday, June 3rd from 8:30-11:30AM.

    • If your last name falls between Adeyinka-Her, you'll take the exam in Hewlett 200

    • If your last name falls between Hernandez-Ochalek, you'll take the exam in Hewlett 201

    • If your last name falls between Onadeko-Zou, you'll take the exam in STLC 111

  • The diagnostic will be taken using Bluebook.
    • On Bluebook, you can write code but you won't be able to compile your programs. It's like a hand-written exam, but for coding questions.
  • The exam is closed internet, closed note. You can bring a two-page cheat sheet with notes. Note that this is 2 individual pieces of paper, 4 total sides of notes allowed.
  • There will also be this reference sheet provided in BlueBook itself

Coverage

  • Coverage. The coverage is comprehensive over the entire quarter (up to and including lecture 27 on graph shortest path algorithms), 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, Dijkstra, A-star)
    • 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 Materials

  • Bluebook Practice Exam. To give a representative sample, we have taken an actual CS106B final exam from recent quarter and reworked into a Bluebook format. This will allow you to practice using the same environment. You can find the sample here, password practice. Here are the solutions.
    • We strongly recommend that you practice on the sample as if it were the real thing (set aside a block of time, gather the resources you plan to have on hand, and do a trial run using Bluebook).
  • 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!