CS 106B: Programming Abstractions, Spring 2019

Rules and Information:

Same as on the midterm exam (see rules below).

Syntax Reference Sheet:

• syntax reference sheet (will be given out attached to your exam as a reference; bring your textbook to reference any other C++ syntax/libraries)

Review opportunities:

• The section leaders will lead a final review session Monday, June 3, 7:00pm - 9:00pm in Hewlett 201. Here are the slides from the review session.
• Your conceptual/prep questions are welcome in office hours! The Lair will be open regular hours Sun, Mon, and Tue evening. Julie's hours in final week are Monday 3:30-4:30pm and Tues 1:30-3pm.
• You can also ask/answer/discuss questions about the final exam on the Piazza forum. The staff will answer questions up until Thursday noon. Students can continue to discuss issues on the forum up until the exam begins. We will disable the forum while the exam is being adminsistered and re-open after all students have completed the exam.

Practice problems:

• practice final #1 | key

  If you like to practice using CodeStepByStep, here are links to the coding/writing problems from this practice exam that are available on CSBS:

  1. largestSum (backtracking write)
  2. chopBothSides (linked lists write)
  3. swapChildrenAtLevel (binary trees write)
• practice final #2 | key

  If you like to practice using CodeStepByStep, here are links to the coding/writing problems from this practice exam that are available on CSBS:

  1. digitsSorted (recursion)
  2. isSortedBy (linked lists write)
  3. removeMatchingLeaves (binary trees write)
• practice final #3 | key

  If you like to practice using CodeStepByStep, here are links to the coding/writing problems from this practice exam that are available on CSBS:

  1. combineDuplicates (linked lists write)
  2. range (binary trees write)
• Additional practice problems can be found in the textbook, in your section handouts, and on CodeStepByStep.

Topics to Study:

The actual exam will have 9-10 total problems. Some problems will ask you to read code (review a piece of existing code to analyze its behavior or show its output); others will ask to you write code (implement a function, class, or entire program that solves a specified task). Here are the topics covered this quarter and how we might assess content from this area. Material from the entire quarter is "fair game" , but you can expect that those 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.

• recursion and/or recursive backtracking: write a function that uses recursion to solve a problem, possibly one involving backtracking
• algorithm analysis / Big-Oh: look at a given piece of code and answer questions about its runtime complexity, and/or write a piece of code that solves a problem within a given Big-Oh limit, demonstrate knowledge of the Big-Oh runtimes for standard algorithms and ADT operations
• searching and sorting: demonstrate knowledge of the behavior of selection, insertion, merge, or quick sort algorithms
• binary heaps: know how to organize data in a min-heap/max-heap, read/write code to manipulate elements stored in a binary heap
• pointers: write lines of code that use pointers, and/or look at a piece of pointer code and answer questions about it
• linked lists: read/write code to manipulate a list of ListNode objects, either singly or doubly-linked
• binary trees: simulate operations on a binary search tree (BST) such as adding or removing elements; perform traversals on a binary tree; read/write code to manipulate a tree of TreeNode objects, construct an encoding tree and use to encode/decode data
• implementing data structures: simulate operations on a data structure we implemented or discussed the implementation of in lecture, such as a tree set/map, hash set/map; stack, queue, vector; and/or, add behavior to an existing implementation class such as TreeSet or ArrayList, discuss implementation tradeoffs in terms of design, Big-Oh efficiency, code complexity
• graphs: look at a given graph and answer questions about it, such as directedness, weights; simulate the execution of DFS and BFS path-searching algorithms
• hashing: simulate operations on a hash set or hash map data structure, show understanding of simple hash function

• The following topics are guaranteed NOT to be required to solve any problem on the final exam:
  • drawing fractals; graphics with the GWindow class
  • overloading the = operator, copy constructors, and deep copying
  • the Standard Template Library (STL)
  • writing your own C++ template classes such as ArrayList<T>
  • details of how to perform rotations on an AVL tree to restore its balance
  • anything else not explicitly covered in lecture or homework
  • any material that is only covered in the "Overflow" slides at the end of various lecture slide decks

Reference and Review:

• syntax reference sheet (will be given out attached to your exam as a reference; bring your textbook to reference any other C++ syntax/libraries)
• midterm review slides (by SLs Anand Shankar, Gaby Candes, Baker Sharp)

Practice Exams:

Sample midterm exam(s) posted here are intended to be very similar to the actual midterm. The number of problems and type of problems on the actual exam will be much like what is seen on these practice exams. You can test your answer by typing it into Qt Creator or CodeStepByStep.

• practice midterm #1 | key

  If you want to work on this practice exam's problems in CodeStepByStep, here are direct links to each problem:

  1. wordStats
  2. collection mystery
  3. byAge
  4. recursion mystery
  5. moveToEnd
  6. crack
  7. RingBufferQueue reverse (not in CodeStepByStep)
• practice midterm #2 | key

  If you want to work on this practice exam's problems in CodeStepByStep, here are direct links to each problem:

  1. parameter mystery
  2. flipLines
  3. collection mystery
  4. isSorted
  5. recursion mystery
  6. largestDigit
  7. printSquares
• practice midterm #3 | key

  If you want to work on this practice exam's problems in CodeStepByStep, here are direct links to each problem:

  1. parameter mystery
  2. coinFlip
  3. collection mystery
  4. removeBadPairs
  5. recursion mystery
  6. matchCount
  7. isElementSpellable
  8. ArrayStack pushAndFlip (not in CodeStepByStep)
• More practice problems can be found in the textbook and in your section handouts.

Rules and Information:

• The exam is to be completed individually and without any assistance from a partner or other students.
• The exam is open-book for the Programming Abstractions in C++ textbook, or any other relevant textbooks you want to bring. You can bring the current edition of the book, or the previous ring-bound "course reader" edition, but not a digital copy and not a printout of the book on loose paper.
• The exam is closed-notes and closed for all other resources. You may not bring or use any other printed materials such as handouts, slides, or practice exams. (A "syntax reference sheet" of necessary syntax will be given to you at the exam.) You may not use any computing devices of any kind including calculators, cell phones, music players, iPad/Kindles, or other electronic devices. Please do not have any of these devices out nor use any of them during the exam.
• Unless a question specifically mentions otherwise, your code you write will be graded purely on external correctness (proper behavior and output) and not on internal correctness (style). So, for example, redundancy or lack of comments will not reduce your score.
• You don't need to write any #include statements in your exam code.
• Please do not abbreviate any code on the exam. Abbreviated code will be ignored during grading.
• Unless otherwise specified, it is fine to write helper functions to implement the required behavior.
• Please be quiet during the exam. If you have a question or need, please quietly exit the room and a nearby SL or TA will assist you.
• Any corrections or clarifications to the exam will be written at the front of the room.
• Please follow the Stanford Honor Code during the exam. Work on the exam alone and submit only your own work. Please also take action to prevent any inappropriate activity conducted by others, such as speaking to the person and asking them to stop, or reporting the activity to the instructor.
• When you have finished the exam, please leave the room quietly and bring your exam to the instructor and SLs.

Topics to Study:

The actual midterm exam will have roughly 7-8 total problems. Those problems will be selected from the following categories. For each category, you may be asked to read code (look at a piece of existing code and answer questions about it, such as writing its output), and/or write code (write a piece of code such as a function or short program that solves a problem about that topic).

• C++ basics: console input/output; strings, streams (file I/O), functions; passing parameters by value and by reference; return
• using ADTs: the collections from the Stanford C++ library, such as Vector, Grid, Stack, Queue, Set, Map, or Lexicon; understanding tradeoffs between various data structures
• recursion: look at a piece of recursive code and write its output, and/or write a function that uses recursion to solve a problem
• backtracking: write a function that uses recursive backtracking to solve a problem
• implementing ADTs: write code to implement operation(s) inside a basic ADT such as a list, stack, queue, etc.

The following topics are guaranteed NOT to be required to solve any problem on the midterm:

• complex output formatting with the iomanip library (e.g. setw, setprecision)
• HashSet, HashMap, and other ADTs we did not explicitly cover in lecture or use on homework
• searching and sorting algorithms
• drawing fractals
• the GWindow class or any other code related to graphical user interfaces (GUIs)
• priority queues and heaps
• writing C++ template classes such as Foo<T>
• operator overloading
• anything else not explicitly covered in lecture or homework
• any material that is only covered in the "Overflow" slides at the end of various lecture slide decks
• any material covered past the end of week 5 of the course (material from weeks 1-5 inclusive will be tested on the exam)