CS 106B: Programming Abstractions (C++)
Spring 2015

Time/Place:

• Sat, Jun 6, 2015, 8:30am - 11:30am

Answer Key:

• final | answer key | code ZIP

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

Rules and Information:

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

Practice Exams and Review:

(Suggestion: Don't just look at the first 1-2 exams. Take a look at at least one of the later ones, like #5 or #6, to see some of the changes from quarter to quarter. Different practice exams contain slightly different kinds of problems, and you are responsible for any of these kinds of problems being on the real exam.)

• slides from exam review session, led by our TA Kevin Miller
• practice final #1 | key | code (based on Autumn 2013 practice final 1)
• practice final #2 | key | code (based on Autumn 2013 practice final 2)
• practice final #3 | key | code (based on Autumn 2013 final)
• practice final #4 | key | code (based on Winter 2014 final)
• practice final #5 | key | code (based on Summer 2014 final)
• practice final #6 | key | code (based on Autumn 2014 final)
• More practice problems can be found in the textbook and in your section handouts.
• Sample final exam(s) posted here are intended to be similar to the actual final. The number of problems and type of problems on the actual exam will be relatively similar to what is seen on these practice exams, though we do not promise that it will be exactly the same in length or in difficulty.

Additional Sample Problems:

If you want more practice problems, here are links to some past exams given in 106B by other instructors. They don't exactly match the current exam format, so they may be of limited use. Some of the problems on these tests don't match the topics, difficulty level, and/or type of questions we currently plan to ask. These links are provided merely as a convenience to help you study.

• Spring 2014 (Cynthia Lee): final exam
• Spring 2013 (Keith Schwarz): practice midterm 2 (final) | key | midterm 2 (final) | key
• Winter 2013 (Eric Roberts): practice midterm 2 | key | midterm key | practice final 1 | key | practice final 2 | key
• Autumn 2012 (Jerry Cain): practice final | key | final | key

Topics to Study:

The actual exam will have roughly 10 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).

• linked lists: add behavior to the LinkedList class from lecture or a similar linked list class
• recursion and/or recursive backtracking: write a function that uses recursion to solve a problem, possibly one involving backtracking
• binary trees: simulate operations on a binary search tree (BST) such as adding or removing elements; perform traversals on a binary tree; add behavior to the BinaryTree class from lecture or a similar binary tree class
• implementing data structures: simulate operations on a data structure we implemented or discussed the implementation of in lecture, such as a tree set/map, priority queue (heap), hash set/map; stack, queue, vector; and/or, add behavior to an existing implementation class such as HeapPriorityQueue or ArrayList
• searching and sorting: trace the behavior of binary search, selection sort, and/or merge sort
• graphs: look at a given graph and answer questions about it, such as connectedness, cyclicness, degrees; simulate the execution of path-searching algorithms such as DFS, BFS, Dijkstra's algorithm, A*; simulating execution of Kruskal's algorithm
• inheritance, polymorphism, object-oriented programming: look at a piece of code involving inheritance and interpret its output; and/or, write a class that uses inheritance to extend some existing base class

• The following topics are guaranteed NOT to be required to solve any problem on the final exam:
  • drawing fractals; graphics with the GWindow class
  • multiple inheritance; pure virtual functions; private inheritance
  • overloading the = operator, copy constructors, and deep copying
  • the Standard Template Library (STL)
  • writing C++ template classes
  • details of how to perform rotations on an AVL tree to restore its balance
  • other kinds of advanced trees such as AVL, Red/Black, Splay, or prefix trees (tries)
  • anything else not explicitly covered in lecture or homework

Time/Place:

• Thu, May 7, 2015, 7:00 - 9:00pm
• last name (family name) starts with A - M: go to Hewlett 200
• last name (family name) starts with N - Z: go to Annenberg Hall

Answer Key:

• midterm | answer key | code (Qt Creator project)

Score Stats, Curve, and Other Information:

* Stats below are raw scores and do not reflect any curve yet.

Picking up your exam: Starting Week7 Tue, you can pick up your exam from the filing cabinets on the first floor of the Gates building. Go to the filing cabinet labeled "CS 106B". If you have questions about exactly what points you missed and why, please pick up your exam and look it over, then contact the head TA and instructor if you still have any questions.

Curve?: To increase the averages up to our targets, +3 points will be added to everyone's score, up to a maximum of 45/45 (100%).

Low Grades: Another topic some students ask about is: If their score was lower than they hoped, how much effect will that have on their grade, or what are their options, etc.? Most of the information to answer this can be found on this web site. The course info sheet lists the relative grading weight of homework vs. midterm vs. final exam, so you can use that to compute the rough effect on your grade of a particular midterm score. Also look at our FAQ page for info about pass/fail grading options, drop dates, and other information.

Regrade Policy:

We work hard to grade consistently and correctly, but sometimes we make mistakes in grading. If you disagree with the grading of your exam, such as if you think your solution actually does work, or that your solution is more nearly correct than it was given credit for, the procedure for regrades is the following:

If your complaint is about the correctness of your solution to a programming question, you must download our Qt Creator code project, which will contain runnable testers for the midterm problems. Type your code into the project .cpp file, fixing any trivial syntax problems. Run it for yourself and see how nearly correct your solution is.

If after running the code files you still think your grade is incorrect, submit your exam to the instructor for a regrade. (Either give it to us in lecture, go to our office hours, or slide it under our office doors.) You must include a cover page with a brief written explanation of what specifically you think was misgraded and why. You must also email your midterm "main" .cpp file to the instructor so that we can compile and run your code to verify your claim. As part of your cover page, include copy/pasted output from the the test case results, so that we can to verify its correctness.

We will not accept any exam for a regrade unless it includes this cover page, and we will not re-evaluate grading of the correctess of any programming questions without a typed copy of your solution from the .ZIP / .cpp file being shown to us first.

Also note: When you submit an exam for a regrade, we will regrade your entire exam. If we notice anywhere that you were mistakenly given too many points, we will also correct this. So it is possible (though less likely) that a regrade request will result in you receiving a lower mark than what you started with.

All midterm regrade requests (other than simple score addition errors) must be submitted to the instructor no later than Week8 Mon, at 5:00pm.

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)

Practice Exams:

• practice midterm #1 | key | code (Qt Creator project for testing your answers)
• practice midterm #2 | key | code
• practice midterm #3 | key | code
• practice midterm #4 | key | code (based on Autumn 2013 midterm)
• practice midterm #5 | key | code (based on Winter 2014 midterm)
• practice midterm #6 | key | code (based on Summer 2014 midterm)
• practice midterm #7 | key | code (based on Autumn 2014 midterm)
• Week8 Mon 12:00pm practice midterm #7 | key | code (based on Spring 2015 midterm)
• More practice problems can be found in the textbook and in your section handouts.
• 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.

Additional Sample Problems:

If you want more practice problems, here are links to some past exams given in 106B by other instructors. They don't exactly match the current exam format, so they may be of limited use. Some of the problems on these tests don't match the topics, difficulty level, and/or type of questions we currently plan to ask. These links are provided merely as a convenience to help you study.

• Spring 2014 (Cynthia Lee): midterm | key
• Spring 2013 (Keith Schwarz): practice midterm 1 | key | midterm 1 | key | practice midterm 2 | key | midterm 2 | key
• Winter 2013 (Eric Roberts): practice midterm 1 | key | practice midterm 2 | key | midterm key
• Autumn 2012 (Jerry Cain): practice midterm | key | midterm | key

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 8-10 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: strings, streams (file I/O), functions; passing by value and by reference
• using ADTs: the collections from the Stanford C++ library, such as Vector, Grid, Stack, Queue, Set, Map, HashSet, HashMap, or Lexicon; understanding tradeoffs between various data structures
• implementing ADTs: write code to implement operation(s) inside a basic ADT such as a list, stack, queue, etc.
• pointers/arrays: write lines of code that use pointers and arrays, and/or look at a piece of pointer code and answer questions about it
• linked lists: write a few lines of code to change a "before" picture of some linked nodes into an "after" picture, and/or add behavior to the LinkedList class from lecture
• 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
• 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
• classes and objects: write a class and/or add behavior/data to an existing C++ class; understanding public vs. private, const, constructors, operator overloading

• 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)
  • string input/output streams (istringstream, ostringstream)
  • searching and sorting algorithms
  • drawing fractals; the GWindow class
  • priority queues and heaps
  • writing C++ template classes
  • overloading the = operator, copy constructors, and deep copying
  • anything else not explicitly covered in lecture or homework
  • any material covered past week 6 of the course (material from weeks 1-5 inclusive will be tested on the exam)

Here is a handout created by a past CS 106B instructor with her advice about how to study for, and take, a CS 106B exam. Note that not all of the information and policies in this handout are correct for the current quarter; for example, in Julie's quarter the exam was open-notes, but the exam this quarter is not.

• Exam Strategies (by Julie Zelenski)