---
# System prepended metadata

title: CS18 Final Exam Prep Guide
tags: [Documents]

---

---
tags: Documents
---
# CS18 Final Exam Prep Guide

Here is some information on what to expect from the final. 

The final, just like the midterm, will be conceptual. While you may be asked to fill in a line of code or look at code, it is not a programming exam. The questions will  not be designed to trick you, nor will they introduce new content.

*Previous exams are in the Final Prep folder in Canvas, under the Files section*. Note that finals prior to 2020 were given paper-and-pencil on campus. Your format will resemble what you had on the midterm. Also note that last spring's exam covered a different set of learning objectives: questions 3 from the 2020 final will not be covered on your exam. (I will get to preparing solutions to the 2020 final after the next round of grading reports.)

## Logistics

**When and Where?:** The exam will be available on Gradescope from Monday Apr 19th 8am EST through Friday April 23 (Anywhere on Earth time, so 8am EST Apr 24). You will have 90 minutes to work on it from the time you start. You may take the exam in any 90 minute period during the time when it is out. Adjustments for those with accommodations will be applied automatically.

:::info
You may **NOT** apply late days to the final. If you have extenuating circumstances, reach out to Kathi (if you haven't already). 
:::

**Overview:** The exam will test four learning objectives, all of which fall in the "Data Structures and Algorithms" theme:

- *Traits of Data Structures*: the run time and space usage of key operations on the data structures we've studied)
- *Implementing Data Structures*: why role do certain fields or other details play in the data structure implementations we've studied (e.g., the role of an end-field in a `LinkedList`)
- *Working with Data Structures and Algorithms*: how would you use a specific data structure or algorithm to solve a given problem (or why would doing so be difficult)
- *Choosing Data Structures*: given a concrete scenario, which data structure would you choose to use for it and why?

See the sections further down on what you (do not) need to know for details of which data structures and algorithms will be covered.

The exam will not be language-specific between Java and Scala. The questions will be conceptual. If you do have to write a line of code, the syntax of either will be fine. Any code we provide will be in Scala, just because you have used it most recently.

**Notes and references:** You may reference class notes (whether ones we have posted or ones that you have taken yourself). You may not look up or search for information beyond the course website or notes that you had a part in taking or creating. In particular, you should not be using any materials from another student that provides information about the actual exam content (say if a friend took the exam before you did). Your exam answers have to reflect your own understanding of the material.

It's fine for a group to study together and write up a shared notes file (say in Google docs), but nobody should modify that document after starting the exam. At core, take the exam on your own without assistance from others.

The exam will be self-contained, in that you could come with no notes and still answer all the questions if you knew the properties of the various data structures we covered, as well as the general mechanisms for structuring programs (interfaces, classes, etc). The exam will not expect you to recall details of specific lab or homework questions.

**What if I need a clarification during the exam?** The exam will contain an area where you can describe any assumptions you made while answering the questions. 

**What if my computer dies or internet crashes during the exam?** If you are still able to see the questions (internet goes out), write your answers on paper and email them to the HTA list when your internet is back. If your computer restarts and Gradescope won't let you back in, email the HTA list (which Kathi also sees) and we'll reopen the exam for you. Basically, alert us to the problem as soon as you can and we'll deal with it.

## What do you need to know?

The exam will cover material up through the Monday, April 5th lecture on Minimum Spanning Trees and Disjoint Sets. 

**Data Structures:** All data structures we have covered this semester are in scope, but you can expect a bit more emphasis on ones we have covered since the midterm. Concretely, we have covered Lists, Doubly-Linked Lists, Arrays, Dynamic Arrays, Binary Trees, Hashmaps, Heaps/Priority Queues, Graphs and (to a lesser extent) Disjoint Sets (the component labels from the Spanning Tree algorithms). (From hashmaps onward have been covered since the midterm.) 

You should be able to choose from or argue for or against these data structures for a given problem. You should be able to talk about the running times for operations that we have discussed on these data structures. 

For those data structures that you implemented on homework or projects, we expect you to be able to discuss roughly how those implementations work and what the various parts of the implementation do (you won't be asked to reproduce or remember the corresponding code in detail).

**Data Structures in Memory:** You might be asked to think about how data structures appear in memory, before and after running short programs with them (similar to what you saw on the midterm). You may be asked to upload a picture or PDF file of a memory diagram.

**Algorithms:** You could be asked about inserting/deleting elements from heaps, using dynamic programming to optimize algorithms, and our algorithms on graphs (depth-first search, breadth-first search, finding shortest paths, finding cheapest paths, and minimal spanning trees). 

You do not need to remember/reproduce the code for any of these, but you should know roughly what they do (e.g., what paths would each return, whether a given set of edges is a minimal spanning tree, etc).

**Ideas from Course Projects:** We expect that you understand the main components of the projects: what did the indexer and querier do in search? How did the model checker work? You won't be expected to reproduce code, but we could show you part of a homework/project solution and ask what that part does or why it was important to solving the problem.

## What do you NOT need to know?

- Syntax details -- you won't be asked to write more than a line or two of code, and even then, missing bits of syntax won't matter
- Specific examples or code from class, homeworks, or lab -- the exam will be self-contained, rather than say things like ``remember the Dillos? ...''
- The exact names of built-in methods on Java/Scala data structures -- as long as we understand what operation you are trying to do, you'd get credit for your answer
- How to build an iterator
- PageRank (how it works, what it produces, etc)

## What About the Optional Makeups?    

As previously announced on Piazza, there will be optional makeups on immutable data structures and time/space analysis, towards points lost on the midterm. These will also be out during the entire week. However, these will be **separate assessments** with their own time limits. They will **NOT** count against your time on the final. 