CS200 Final Exam Prep Guide

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 that Kathi wrote for cs18 are in the Final Prep folder in Canvas, under the Files section. Finals prior to 2020 were given paper-and-pencil on campus (as your format will be). Finals from 2020 and 2021 were given online.

• The 2020 exam covered a different set of learning objectives: question 3 from the 2020 final will not be covered on your exam.
• Bear in mind that these exams were written for a slightly different course that used Scala instead of Python in the second half.

Office Hours: While the TAs will not hold hours after the Search deadline, Kathi and/or Milda will be available for questions.

Logistics

The exam will be given from 9am-noon EDT on Friday, May 20. You may take it either in person or remotely, but everyone must take the exam simultaneously.

If you are still in Providence, we expect you to take the exam in person barring a medical situation backed by a dean's/health services note (such as being in COVID isolation) or SAS accommodations for reduced-distraction space. The remote option is for students who will have left campus before the exam slot.

Let us know how you plan to take the exam (this is the same form link included in the classwide email about exam logistics). We only need to hear from you once. Please reply no later than May 13th (earlier is helpful).

You may NOT apply late days to the final. If you have extenuating circumstances, reach out to Kathi and Milda. In no case can you take the exam early.

In-person logistics: Once we know how many students will be taking the exam in person, we will announce which classrooms on campus you should report to for the exam. Bring your Brown ID, as we will check it as you turn in your exam.

Remote logistics: The exam will be released as a PDF to everyone (via email or Canvas – we will let you know) at 9am EDT on May 20. You will need to upload a filled-in PDF to Gradescope by 12:03pm EDT on May 20 (we're giving you three minutes to upload if needed). There are several ways you can prepare your PDF:

• print it out, take it on paper, then scan it in
• download the exam to a tablet and write on it
• use a PDF annotation tool to fill in your answers on your computer

Remote takers will also need to make a brief (60-90 second) video recording of yourself explaining one of your question answers (the exam will tell you which one). As part of your video, we will ask you to hold your Brown ID up to the camera by way of identity check. To be absolutely clear, we are NOT asking you to have video on for the entire exam – we are just asking you to briefly record an additional explanation to one of the problems.

It is critical that you put your answers on the exam paper/PDF in the same spaces that you'd have used were you taking it on a printout. We leverage Gradescope features to cluster exams based on similar answers, and Gradescope can only look in designated places on your PDF. Don't prepare and upload a separate file with your answers – that won't work with our grading workflow.

Make sure you have obtained and tested the tools you need to create, annotate, or scan your file to PDF and to record your video BEFORE the exam. "I hadn't figured out how to upload" will not be an acceptable excuse for turning in a late exam. There are free tools for scanning printouts to PDF using a mobile phone, should you need a scanning solution. If you anticipate a problem with any of these tasks, reach out to Milda and Kathi before the exam.

SAS Accommodations: We will arrange for the time and location accommodations named in everyone's letters. We will follow up with you personally by email.

Asking clarification questions during the exam: We will monitor an Ed thread during the exam for remote takers who have questions. We will also be going around the classroom answering live questions, so it may take a couple of minutes for someone to answer your question.

What if something goes wrong?: Stay calm and be responsible. Email us or contact us privately on Ed ASAP.

Notes and Collaboration Policy

You must do the exam entirely on your own. The exam will ask you to indicate whether you have done so.

Original policy (now changed, see below):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.

Revised Apr 30: You may prepare two pages (or one sheet both sides) of references notes. These can be handwritten or typed (your choice), in any font size you wish. You may work with other students while studying to prepare your sheet, but you may not share notes with other students during the exam. In particular, you should not be using any materials from another student that provides information about the actual exam content (say if a friend finished a question 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 (or leave comments in it) after the exam starts. At core, take the exam on your own without assistance from others – if you have to ask, chances are it isn't permitted.

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 do you need to know?

The exam will cover material up through the Friday, April 15th lecture on Balanced BSTs. (The lectures after that were designed to help you think about some of our data structures in different contexts, but those contexts will not be tested on the final.)

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 (Search) Trees, Hashmaps, Hashsets, Heaps/Priority Queues, and Graphs. (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). If you worked on these assignments as we expected (developing own solutions for homework, sharing work with your partner in projects), you should be fine.

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. You may be asked to draw a memory diagram.

Algorithms: You could be asked about the process of inserting/deleting elements from data structures, whether and how to use 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 what they do (e.g., what paths would each return, whether a given set of edges is a minimal spanning tree, etc) and what information is maintained during the algorithm (e.g., a visited list in DFS, BFS captures nodes that have already been explored).

Running Time: You could be given a snippet of code or algorithm and asked to determine its running time, at the level of detail (not more) than we have had you do on assignments and projects.

Ideas from Course Projects: We expect that you understand the main components of the projects. For example, what did the indexer and querier do in search? why were each of the algorithms in Travel Planner appropriate? why were function objects useful in Travel Planner? 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.

Testing: You could be asked to describe tests or provide a brief testing plan for a given question.

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/Python 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
• Regular expressions
• The algorithm to balance a binary search tree
• PageRank (how it works, what it produces, etc)
• Differences between Java and Python (You can use ideas from either language on any code-related question, including a mix of ideas across the languages)

How will this be graded?

There will be partial credit on all questions.

Design-facing questions may have multiple correct answers. If we ask you to argue for or against a data structure, we care most about what your answer reveals about your understanding of relevant aspects of the data structure. We don't need to see essays, but say enough to show us your understanding.

For example, saying "addLast on a list is linear time" conveys less than "addLast takes time linear in the size of the list because we might have to visit every node (assuming we don't have an end pointer)".

When you state runtimes, be sure to include what any variables stand for (e.g., "linear in the number of nodes").

When you select data structures, be sure to tell us how they are configured (e.g., "a linked list of tickets", "a hashmap from id numbers to a set of courses").

Last bits of advice

• The top-level questions will be independent of one another. Feel free to do them out of order.
• You are better off turning in solid work on most questions than shallow work on all of them (remember, we look at the breakdown of your grades, not just raw scores).