Link
CSE 373
Search

Final Exam

Table of contents

  1. Archive
  2. Policies
  3. Coverage
  4. Recommended Problems
    1. Past Exams

Archive

Policies

The exam will be held 2:30–4:20 PM Tuesday, December 10 in ARC 147. The exam is 110 minutes long. We will start promptly, so please be seated and ready to begin by 2:30 PM sharp. As you arrive, sit towards the middle of the aisle. If you arrive late, you will not be given additional time. When time is called at the end of the exam, stop writing and hold your exam up in the air.

Bring the following materials to the exam.

  • An erasable writing utensil, preferably a dark pencil or erasable pen.
  • Your Husky Card or other valid student identification.
  • Two double-sided, 8.5-by-11” sheets of notes that you create for yourself.

Aside from the double-sided sheets of notes, this exam is closed book and closed notes. Electronic devices are prohibited. Scratch paper will not be provided. If you’d like to take notes, use the white space on the exam or your sheet of notes.

Each question has a clearly marked final answer region. Only unambiguous marks in the final answer region will be graded. Partial credit may be awarded but only based on the final answer. Notes made in the white space, scratch work, or intermediate steps will not be considered for grading purposes. After the exam, keep your sheet of notes so that you may reuse it for the final exam.

To minimize disruption to other students, you may not leave your seat or turn in the exam during the first 10 minutes or the last 10 minutes of the exam. If you need to use the restroom, bring your phone, student ID, and exam to a staff member.

If you have a clarification question during the exam, please read the clarifications displayed at the front of the room first. If your question has not already been addressed, raise your hand and a staff member will forward your question to the instructor. If a clarification is necessary, it will be added to the display for everyone to see.

Alternate exams are not offered. DRS students with alternate exam timing accommodations will be honored so long as the alternate exam time overlaps with the regularly-scheduled exam time.

Coverage

The exam will cover all course topics up to and including lecture Friday, November 22. Emphasis will be given to topics discussed in quiz section, homework, and QuickChecks. The exam will be divided into two approximately-equal parts: the first half covers course topics through the Midterm Exam (content through Friday, October 18) while the second half covers course from the following lectures.

Fundamentally, the goal of this course is to help you learn (1) how to write code that runs efficiently and (2) how to write code efficiently. We’ve introduced several frameworks for achieving these goals.

The exam is designed to stress your mastery of these frameworks, but mastery can be evaluated at many different levels. There are 6 levels of mastery, split into two categories: applying ideas, and creating new ideas.1 We’ve provided a few example questions of each level of mastery below. In general, each level of mastery gets progressively more challenging because later levels rely on a strong understanding of earlier levels.

Apply

Using knowledge in new situations.

Understand
Given a 2-3 tree, find the corresponding left-leaning red-black tree.
Analyze
Give the order of growth for the height of left-leaning red-black trees.
Evaluate
Given a binary search tree with some red edges, determine if it is a valid left-leaning red-black tree.

Create

Synthesize a solution to a new problem.

Understand
Given a 2-3-4 tree, find a corresponding binary search tree representation.2
Analyze
Suppose we modify a separate-chaining hash table to use left-leaning red-black trees instead of linked lists. What is the resulting order of growth of the runtime for each hash table operation?
Evaluate
Assuming all priority values are integers and bounded by a constant, design a priority queue implementation such that the order of growth of the runtime for every operation is constant.

The exam will give slightly greater weight to the first 3 levels of mastery associated with Apply. As a consequence, the exam will be “hard” in that the mean and median scores will likely fall between 60–70% after taking into account partial credit.

Each lecture comes with its own study guide containing some of the highlights from lecture as well as recommended problems. See the Guide next to each lecture in the Calendar. Relevant past exam problems have been added to the following guides in particular.

For content from the first half of the course, see the Midterm Exam.

Tip
The website search bar at the top of the course website will search through all of the text in lecture, which is especially helpful for quickly finding a keyword in the readings, lectures, or study guides.

Algorithm Design

  1. Q4 from CS 61B 17sp Final
  2. Q13a, Q13b, Q13c from CS 61B 17sp Final
  3. Q7 from CS 61B 18sp Final
  4. Q7 from CS 61BL 18su Final
  5. Q14 from COS 226 14sp Final
  6. Q12 from COS 226 14au Final
  7. Q12 from COS 226 15sp Final
  8. Q15 from COS 226 18au Final

Past Exams

Past exams from this course (or Practice-It! problems) are not likely to be relevant as this offering of the course is completely redesigned. The closest analogues in terms of content coverage are CS 61B(L) offered at UC Berkeley and COS 226 offered at Princeton; however, the emphasis is quite different so focus on the recommended problems first.

  1. Ursula Fuller, Colin G. Johnson, Tuukka Ahoniemi, Diana Cukierman, Isidoro Hernán-Losada, Jana Jackova, Essi Lahtinen, Tracy L. Lewis, Donna McGee Thompson, Charles Riedesel, and Errol Thompson. 2007. Developing a computer science-specific learning taxonomy. SIGCSE Bull. 39, 4 (December 2007), 152-170. https://doi.org/10.1145/1345375.1345438 ↩

  2. This data structure is called a red-black tree, which we did not discuss in class. But since we discussed the correspondence between 2-3 trees and LLRB trees, we can develop a similar correspondence between 2-3-4 trees and red-black trees in general. (However, it isn’t a 1-1 correspondence. Why?) ↩