Assessment 2. Final Exam

Summer 2023 Final Solutions

Logistics

  • The exam is on Friday, August 18th from 3:30-6:30pm in Hewlett Teaching Center, Room 200.
    • Students with exam accommodations will receive an email with their arrangements.
  • This exam is on paper, using pen/pencil. You will write your answers directly on the paper exam.
  • The exam is closed-book and closed-device.
    • We will provide you with a reference sheet during the exam to jog your memory about the Stanford library functions.
    • We will also allow you to bring your own prepared notesheet. The notesheet is one page 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

The coverage is comprehensive over the entire quarter (up to and including lecture 26 on graphs), but expect heavier concentration on content from latter half of course. Topics that figured most prominently in lecture/section/assignments 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
  • Algorithmic 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

Format

Questions included on the final exam generally fall into one of the types below. The practice exams show 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 Resources

We will be publishing multiple practice exams and their solutions. We strongly recommend that you print these out, and take the exam in a realistic setting (i.e. timed, with only a reference sheet and your notesheet available). Then, go back and check your answers with the solutions and make notes of where to target your study!

  • Practice Exam 1 / Solutions
  • Practice Exam 2 / Solutions
  • 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 than 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.
  • We will be having a review session during lecture on Tuesday of Week 8.

What to Expect

Our exams are designed to evaluate your mastery of the course learning goals. We will focus on material from the assignments, section, and lecture. Having spent two solid weeks on recursion and recursive backtracking, you can count on the exam asking you to demonstrate a mastery of recursive problem solving. On the other hand, we would never test you on an obscure fact that only had the briefest of mentions buried in the textbook.

Answering the exam questions is typically going to require good comprehension of the foundational concepts and the ability to analyze and apply them in a given situation. We are evaluating that not only did you successfully complete the assignments and sections, but that you came away with a comprehension you can demonstrate. We will not ask superficial questions about terminology (e.g. "Define abstractions") or details that can/should be looked up on demand ("Which header file has this prototype?").

Many questions will ask you to write C++ code. Other questions may ask you to analyze C++ code: to trace its behavior, to analyze its Big-O runtime, or to identify and fix flaws. There may also be short-answer thought questions about topics such as ADTs and their uses, recrusive techniques, etc.

When scoring answers, we will not be picky about minor syntax and oversights (missing braces around a block of clearly indented code, we don't ask for #include's etc.). The lion's share of the points are reserved for demonstrating a correct conceptual understanding and a valid approach to solving the problem, with somewhat fewer points for the minute details of executing on your plan. In our view, a solid first-pass approximation that shows the correct conceptual understanding of the key issues deserves to be strongly distinguished from code that exhibits significant conceptual issues and would require much trial-and-error with compiler/debugger to turn into working code.

You can read more here about our rationale against IDE exams and our grading criteria.

Advice

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. But assessments in a programming course can feel intimidating. How can you be sure the skills you are building on assignments will translate well to this new setting? Here is a bit of advice based on our past experience.

Before the exam

  • The long view. The mastery for the exams isn't created by a night of cramming, it is built up throughout the quarter. Make it a priority to monitor your own progress and identify holes or confusion to be shored up before moving on.
  • Recreate the environment. It is not a given that your real-world skills will translate to the exam setting without first becoming familiar with how the experience is different. The best practice is to solve problems without aid of compiler/debugger, in longhand using pencil and paper under a time limit, just as you will have to during the exam.
  • Practice makes perfect. Take problems (lecture or section example, textbook exercise, sample exam problem) and write out a solution under exam-like conditions. Review it to see how you did. This is much more valuable than a passive review of the problem and its solution where it is too easy to conclude "ah yes, I would have done that" only to find yourself adrift during the real exam when there is no provided solution to guide you!
  • Make reference/summary page as part of exam prep. Whether you're allowed infinite resources or just one page, building your page of key facts is a good investment. We are not expecting you to memorize minutiae and the exam will not focus on those details. Reviewing the topics and determining what information is worth including on your reference page will remind you of where we've been and help you take stock of your comfort level with the course topics. Use this opportunity to identify any areas on which you feel weak and resolve dangling issues before heading into the exam.
  • Get your questions answered. If there is a concept you're a bit fuzzy on, or you'd like to check your answer to an exercise, or you wonder why a solution is written a particular way, get those questions answered before the exam. Swing by LaIR, come to office hours, or post on Ed and we're happy to help.

During the exam

  • Scan the entire exam first. Quickly peruse all questions before starting on any one. This allows you to "multi-task"— as you are writing the more mundane parts of one answer, your mind can be brainstorming strategies or ideas for another problem in the background. You can also sketch out how to allocate your time between questions in the first pass.
  • Spend your time wisely. There are only a handful of questions, and each is worth a significant amount. Don't get stuck on any particular problem. There are many opportunities for partial credit, so it's better to make good efforts on all problems than to perfect an answer to one leaving others untouched.
  • Pay attention to specific instructions. A problem statement may include detailed constraints and hints such as "you must solve this recursively" or "you should not destructively modify the input list" or "you do not have to handle the case when the string is empty" or "this operation must run in constant time". You may want to underline or highlight these instructions to be sure you don't overlook them. These constraints are not intended to make things difficult, typically we are trying to guide you in the direction of a straightforward and simple solution. If you disregard these instructions, you are likely to lose points, either for not meeting the problem specification and/or for errors introduced when attempting a convoluted alternative.
  • Ask a question rather than answer the wrong one. If you are uncertain about what a question is asking or find some part of the question ambiguous, it's worth your time to ask the course staff for a clarification so you can be sure you are solving the right problem before you start working on it.
  • Style and decomposition are secondary to correctness. Unlike the assignments where we hold you to high standards in all areas, for an exam, the correctness of the answers dominates the grading. Decomposition and style are thus somewhat de-emphasized. However, good design may make it easier for you to get the functionality correct and require less code, which takes less time and has fewer opportunities for error. Comments are never required unless specifically indicated by a problem. When a solution is incorrect, commenting may help us determine what you were trying to do and award partial credit.
  • Syntax is not that important if it is clear what you mean. We won't trouble you about most syntax as long as your intentions are clear. But if there is ambiguity in your attempt, correct syntax can help us get the correct meaning. For example, if we see a for statement followed by two lines, where both lines are vaguely indented or a third line has been added in after the fact, we may be confused. If there are braces around all the lines, it will be clear you intended both to be a part of the loop body, but without the braces, we can't be sure and it may make your answer incorrect.
  • Answer in pseudocode only if you must. If the syntax of C++ is blocking you from writing a solution, you can answer in pseudocode for possible partial credit. We discourage this approach as pseudocode is often lacking in detail or just restates the problem description ("I would recursively try all the subsequences to find the longest"). Such answers will earn little, if any, credit. Sufficiently detailed pseudocode (e.g. "scan the next token from input, if it the first char is a digit, then convert to an integer") would have been easier and more concise to write in C++ and will earn more points that way.

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!