Link
CSE 332
Search

Midterm Exam

Table of contents

  1. Policies
  2. Charrette
  3. Coverage
  4. Practice Problems

Policies

The exam will be held 4:30–5:20 PM Friday, Feb 14 in ARC 147. The exam is 50 minutes long. We will start promptly, so be seated and ready to begin by 4: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” note sheets that you create for yourself.

Aside from the double-sided note sheets, this exam is closed book and closed notes. Electronic devices are prohibited. Scratch paper will not be provided. Use the white space on the exam or your note sheets for scratch work.

Each question has a 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. Scratch work will not be graded. Do not turn in your note sheets.

If you have a clarification question during the exam, 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.

To minimize disruption to other students, you may not leave your seat, ask clarification questions, or turn in the exam during the first 10 minutes and 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.

Alternate exams are offered only if the exam time overlaps with the regularly-scheduled exam time. If you miss the exam, your score will be reweighted according to the Midterm Clobber policy.

Charrette

The peer charrette for week 7 will be a group midterm exam activity. After the conclusion of the exam at 5:20 PM, the blank exam will be posted online and extra copies will be distributed to groups of students. Submit the completed group exam to Gradescope by the end of the following week in groups of up to 3 students for completion credit in the Activities category.

Coverage

The exam will cover all course topics and assignments released by Thursday, Feb 6. Emphasis will be given to concepts discussed in lecture and quiz section, though we will also expect familiarity with the programming homework and written exercises.

The exam is designed to stress 6 levels of concept mastery split into two categories: applying ideas and creating new ideas.1 In general, each level of mastery gets progressively more challenging because later levels rely on a strong understanding of earlier levels.

Apply

Use 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
Consider balancing a K-d tree using left-leaning red-black tree invariants. If this is possible, explain add and nearest. If this is impossible, explain why.

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.

Practice Problems

The questions we’ve solved in lecture and quiz sections are representative of most questions on the exam. For additional review and practice, see the lecture readings, handouts, and study guides posted on the course calendar.

Tip
Use the search bar at the top of the course website to search through all content except for quiz section handouts.

Data Structure Design

  1. Q5 from CSE 373 19au Final (Solution)
  2. Q10 from CS 61B 15sp MT2 (Solution)
  3. Q5 from CS 61B 16sp MT2 (Solution)
  4. Q7 from CS 61B 17sp MT2 (Solution)

Past Exams

  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?) ↩