\documentclass[11pt]{article}
\usepackage{mathnotes}
\discipline{UCLA COMPUTER SCIENCE FIELD NOTES}
\course{CS 32}{Data Structures and Object-Oriented Design}{Complexity, containers, trees, graphs, searching, sorting, and resource-safe C++}

\begin{document}
\makemathcover
\coursefrontmatter{
\begin{curriculumtable}
\unitline{1}{Object-oriented design and RAII}{Explain the model, apply it to a concrete case, and defend the relevant correctness or design decision.}
\unitline{2}{Asymptotic and amortized analysis}{Explain the model, apply it to a concrete case, and defend the relevant correctness or design decision.}
\unitline{3}{Linked lists and iterator invariants}{Explain the model, apply it to a concrete case, and defend the relevant correctness or design decision.}
\unitline{4}{Stacks, queues, and frontiers}{Explain the model, apply it to a concrete case, and defend the relevant correctness or design decision.}
\unitline{5}{Trees and binary search trees}{Explain the model, apply it to a concrete case, and defend the relevant correctness or design decision.}
\unitline{6}{Heaps, priority queues, and hashing}{Explain the model, apply it to a concrete case, and defend the relevant correctness or design decision.}
\unitline{7}{Graphs and representations}{Explain the model, apply it to a concrete case, and defend the relevant correctness or design decision.}
\unitline{8}{Sorting and binary search}{Explain the model, apply it to a concrete case, and defend the relevant correctness or design decision.}
\unitline{9}{Integration workshop}{Connect at least three chapters in one end-to-end problem and explain where their contracts meet.}
\unitline{10}{Synthesis and project review}{Audit assumptions and explain a complete solution from interface to failure handling.}
\end{curriculumtable}
}{\curriculumsource{https://catalog.registrar.ucla.edu/course/2025/COMSCI32}}

\section{Object-oriented design and RAII}

\begin{idea}
Inheritance models is-a, composition has-a, and polymorphism dispatches one interface to several implementations. RAII ties resource cleanup to object lifetime; virtual destructors protect polymorphic deletion.
\end{idea}
% MASTERCLASS EXPANSION
\subsection{Rebuild the chapter from first principles}
The claim I need to own is this: Inheritance models is-a, composition has-a, and polymorphism dispatches one interface to several implementations. RAII ties resource cleanup to object lifetime; virtual destructors protect polymorphic deletion. I do not count that as learned just because the sentence looks familiar. I should be able to name the objects, state what changes and what stays fixed, recover the rule from the definitions, and explain why the result is allowed.

\begin{move}
\textbf{My working sequence}
\begin{enumerate}
  \item \textbf{Translate.} Rewrite the prompt in the language of object-oriented design and raii. List the known quantities, the unknown, the units or types, and any hidden constraint.
  \item \textbf{Choose.} State the theorem, model, algorithm, accounting rule, or physical law before substituting values. This is where I make the assumption visible.
  \item \textbf{Execute.} Work one justified step at a time and keep intermediate state readable enough that I can audit it later.
  \item \textbf{Verify.} Check a boundary case, sign, unit, invariant, order of magnitude, or alternative derivation. Then translate the result back into an ordinary sentence.
\end{enumerate}
\end{move}

\subsection{Details I would refuse to skip}
\begin{itemize}
  \item \textbf{Definitions:} I should be able to define every technical noun in the chapter without using that same noun in the definition.
  \item \textbf{Assumptions:} I write the condition that makes the method legal beside the method itself. A correct procedure under the wrong assumptions is still a wrong answer.
  \item \textbf{Representation:} I move freely among words, equations or code, a diagram, and a small numerical example. If one representation disagrees with another, that disagreement is useful evidence.
  \item \textbf{Failure modes:} I keep the nearest counterexample in mind: the boundary where the rule changes, the invariant breaks, or the model stops matching reality.
  \item \textbf{Communication:} My final answer names what the result means and what it does not establish. I do not let notation do the explanatory work for me.
\end{itemize}

\begin{sanitybox}
\textbf{Closed-note check.} Can I teach object-oriented design and raii on a blank page, derive or reconstruct its main rule, work a fresh example, and diagnose a deliberately broken solution? If I can only recognize the finished work, I am not done.
\end{sanitybox}

\subsection{How this chapter connects}
I read this chapter as the bridge from the course foundations to asymptotic and amortized analysis. The earlier material supplies the language and constraints; this chapter adds a new reasoning move; the later material asks me to use that move without being told its name. That connection matters because exams and real projects mix chapters on purpose.


\subsection{What I need to be able to do}
For this chapter, I should be able to define the objects and state involved, state the governing invariant or contract, trace a small example without hand-waving, and explain which assumption makes the method valid. I should also be able to compare this model with the nearest alternative and say what failure would make me switch approaches.

\subsection{Deep notes}
\begin{itemize}
\item \textbf{Model.} Inheritance models is-a, composition has-a, and polymorphism dispatches one interface to several implementations.
\item \textbf{Mechanism.} RAII ties resource cleanup to object lifetime; virtual destructors protect polymorphic deletion.
\item \textbf{Boundary.} The useful test is whether I can apply object-oriented design and raii to a new case and explain the assumption that makes the answer valid.
\item \textbf{Decision test.} I should be able to say when object-oriented design and raii is the right model, when its assumptions fail, and what evidence would change my choice.
\end{itemize}

\begin{studenttake}
I use composition first and inherit only when substitution is genuinely true.
\end{studenttake}

\begin{plainbox}
Objects own responsibilities; RAII makes cleanup happen automatically when the owner leaves scope.
\end{plainbox}

\begin{examplebox}
Compose a game Actor with inventory and behavior objects instead of building a hierarchy for every ability combination. The worked question below makes that reasoning concrete: Why should a polymorphic base have a virtual destructor? The conclusion is Deleting through a base pointer must invoke the complete derived destructor or derived resources may leak.
\end{examplebox}

\begin{warningbox}
The common mistake is to memorize the visible procedure while dropping its precondition. I write the assumption beside the method and test one boundary case before trusting the result.
\end{warningbox}

\begin{chapterpractice}
\textbf{Practice.} Why should a polymorphic base have a virtual destructor?

\textbf{Solution.} Deleting through a base pointer must invoke the complete derived destructor or derived resources may leak.

\medskip
\textbf{Practice 2.} Give a short oral explanation of object-oriented design and raii that includes its model, one assumption, one failure mode, and one comparison with a neighboring method.

\textbf{Solution.} A strong answer begins with the model in the blue box, names the assumption that licenses the method, uses the common miss above as the failure mode, and chooses the comparison according to the decision test in the deep notes. The goal is not one memorized sentence; it is a four-part explanation I can reproduce on a new example.

\medskip
\textbf{Mastery practice A.} Reconstruct object-oriented design and raii from a blank page. Include the central definition, the governing rule, one required assumption, and one boundary case.

\textbf{Solution.} Start from the blue idea box, but rewrite it in my own words. Identify the objects and state, name the rule before using it, copy the relevant assumption from the details audit, and choose a boundary where that assumption becomes equality or fails. A complete solution explains why each part belongs; a list of vocabulary is not enough.

\medskip
\textbf{Mastery practice B.} A classmate gets a polished-looking answer to a object-oriented design and raii problem but never states a model or checks the result. Write the shortest useful review of that solution.

\textbf{Solution.} I would ask four concrete questions: What exactly are the inputs and desired output? Which rule licenses the main step? Which assumption could invalidate it? Which independent check supports the conclusion? If the answer cannot survive those four questions, I treat the numerical or verbal result as unverified.

\end{chapterpractice}

\section{Asymptotic and amortized analysis}

\begin{idea}
Big-O bounds growth above, Omega below, and Theta matches both. Worst, average, and amortized costs answer different questions. Every claim must define input size and counted operation.
\end{idea}
% MASTERCLASS EXPANSION
\subsection{Rebuild the chapter from first principles}
The claim I need to own is this: Big-O bounds growth above, Omega below, and Theta matches both. Worst, average, and amortized costs answer different questions. Every claim must define input size and counted operation. I do not count that as learned just because the sentence looks familiar. I should be able to name the objects, state what changes and what stays fixed, recover the rule from the definitions, and explain why the result is allowed.

\begin{move}
\textbf{My working sequence}
\begin{enumerate}
  \item \textbf{Translate.} Rewrite the prompt in the language of asymptotic and amortized analysis. List the known quantities, the unknown, the units or types, and any hidden constraint.
  \item \textbf{Choose.} State the theorem, model, algorithm, accounting rule, or physical law before substituting values. This is where I make the assumption visible.
  \item \textbf{Execute.} Work one justified step at a time and keep intermediate state readable enough that I can audit it later.
  \item \textbf{Verify.} Check a boundary case, sign, unit, invariant, order of magnitude, or alternative derivation. Then translate the result back into an ordinary sentence.
\end{enumerate}
\end{move}

\subsection{Details I would refuse to skip}
\begin{itemize}
  \item \textbf{Definitions:} I should be able to define every technical noun in the chapter without using that same noun in the definition.
  \item \textbf{Assumptions:} I write the condition that makes the method legal beside the method itself. A correct procedure under the wrong assumptions is still a wrong answer.
  \item \textbf{Representation:} I move freely among words, equations or code, a diagram, and a small numerical example. If one representation disagrees with another, that disagreement is useful evidence.
  \item \textbf{Failure modes:} I keep the nearest counterexample in mind: the boundary where the rule changes, the invariant breaks, or the model stops matching reality.
  \item \textbf{Communication:} My final answer names what the result means and what it does not establish. I do not let notation do the explanatory work for me.
\end{itemize}

\begin{sanitybox}
\textbf{Closed-note check.} Can I teach asymptotic and amortized analysis on a blank page, derive or reconstruct its main rule, work a fresh example, and diagnose a deliberately broken solution? If I can only recognize the finished work, I am not done.
\end{sanitybox}

\subsection{How this chapter connects}
I read this chapter as the bridge from object-oriented design and raii to linked lists and iterator invariants. The earlier material supplies the language and constraints; this chapter adds a new reasoning move; the later material asks me to use that move without being told its name. That connection matters because exams and real projects mix chapters on purpose.


\subsection{What I need to be able to do}
For this chapter, I should be able to define the objects and state involved, state the governing invariant or contract, trace a small example without hand-waving, and explain which assumption makes the method valid. I should also be able to compare this model with the nearest alternative and say what failure would make me switch approaches.

\subsection{Deep notes}
\begin{itemize}
\item \textbf{Model.} Big-O bounds growth above, Omega below, and Theta matches both.
\item \textbf{Mechanism.} Worst, average, and amortized costs answer different questions.
\item \textbf{Boundary.} Every claim must define input size and counted operation.
\item \textbf{Decision test.} I should be able to say when asymptotic and amortized analysis is the right model, when its assumptions fail, and what evidence would change my choice.
\end{itemize}

\begin{studenttake}
I write what n means before I write O anything.
\end{studenttake}

\begin{plainbox}
Complexity predicts scaling, not which program wins one small stopwatch race.
\end{plainbox}

\begin{examplebox}
Dynamic-array append is occasionally O(n) during resize but O(1) amortized because copied capacities form a geometric series. The worked question below makes that reasoning concrete: Analyze loops with inner bound j\textless{}i. The conclusion is The body runs 0+1+...+(n-1)=n(n-1)/2 times, so the cost is Theta(n\textasciicircum{}2).
\end{examplebox}

\begin{warningbox}
The common mistake is to memorize the visible procedure while dropping its precondition. I write the assumption beside the method and test one boundary case before trusting the result.
\end{warningbox}

\begin{chapterpractice}
\textbf{Practice.} Analyze loops with inner bound j\textless{}i.

\textbf{Solution.} The body runs 0+1+...+(n-1)=n(n-1)/2 times, so the cost is Theta(n\textasciicircum{}2).

\medskip
\textbf{Practice 2.} Give a short oral explanation of asymptotic and amortized analysis that includes its model, one assumption, one failure mode, and one comparison with a neighboring method.

\textbf{Solution.} A strong answer begins with the model in the blue box, names the assumption that licenses the method, uses the common miss above as the failure mode, and chooses the comparison according to the decision test in the deep notes. The goal is not one memorized sentence; it is a four-part explanation I can reproduce on a new example.

\medskip
\textbf{Mastery practice A.} Reconstruct asymptotic and amortized analysis from a blank page. Include the central definition, the governing rule, one required assumption, and one boundary case.

\textbf{Solution.} Start from the blue idea box, but rewrite it in my own words. Identify the objects and state, name the rule before using it, copy the relevant assumption from the details audit, and choose a boundary where that assumption becomes equality or fails. A complete solution explains why each part belongs; a list of vocabulary is not enough.

\medskip
\textbf{Mastery practice B.} A classmate gets a polished-looking answer to a asymptotic and amortized analysis problem but never states a model or checks the result. Write the shortest useful review of that solution.

\textbf{Solution.} I would ask four concrete questions: What exactly are the inputs and desired output? Which rule licenses the main step? Which assumption could invalidate it? Which independent check supports the conclusion? If the answer cannot survive those four questions, I treat the numerical or verbal result as unverified.

\end{chapterpractice}

\section{Linked lists and iterator invariants}

\begin{idea}
Lists trade random access for cheap local insertion when a node position is known. Mutations must preserve neighbor links, sentinels, size, and iterator-validity rules.
\end{idea}
% MASTERCLASS EXPANSION
\subsection{Rebuild the chapter from first principles}
The claim I need to own is this: Lists trade random access for cheap local insertion when a node position is known. Mutations must preserve neighbor links, sentinels, size, and iterator-validity rules. I do not count that as learned just because the sentence looks familiar. I should be able to name the objects, state what changes and what stays fixed, recover the rule from the definitions, and explain why the result is allowed.

\begin{move}
\textbf{My working sequence}
\begin{enumerate}
  \item \textbf{Translate.} Rewrite the prompt in the language of linked lists and iterator invariants. List the known quantities, the unknown, the units or types, and any hidden constraint.
  \item \textbf{Choose.} State the theorem, model, algorithm, accounting rule, or physical law before substituting values. This is where I make the assumption visible.
  \item \textbf{Execute.} Work one justified step at a time and keep intermediate state readable enough that I can audit it later.
  \item \textbf{Verify.} Check a boundary case, sign, unit, invariant, order of magnitude, or alternative derivation. Then translate the result back into an ordinary sentence.
\end{enumerate}
\end{move}

\subsection{Details I would refuse to skip}
\begin{itemize}
  \item \textbf{Definitions:} I should be able to define every technical noun in the chapter without using that same noun in the definition.
  \item \textbf{Assumptions:} I write the condition that makes the method legal beside the method itself. A correct procedure under the wrong assumptions is still a wrong answer.
  \item \textbf{Representation:} I move freely among words, equations or code, a diagram, and a small numerical example. If one representation disagrees with another, that disagreement is useful evidence.
  \item \textbf{Failure modes:} I keep the nearest counterexample in mind: the boundary where the rule changes, the invariant breaks, or the model stops matching reality.
  \item \textbf{Communication:} My final answer names what the result means and what it does not establish. I do not let notation do the explanatory work for me.
\end{itemize}

\begin{sanitybox}
\textbf{Closed-note check.} Can I teach linked lists and iterator invariants on a blank page, derive or reconstruct its main rule, work a fresh example, and diagnose a deliberately broken solution? If I can only recognize the finished work, I am not done.
\end{sanitybox}

\subsection{How this chapter connects}
I read this chapter as the bridge from asymptotic and amortized analysis to stacks, queues, and frontiers. The earlier material supplies the language and constraints; this chapter adds a new reasoning move; the later material asks me to use that move without being told its name. That connection matters because exams and real projects mix chapters on purpose.


\subsection{What I need to be able to do}
For this chapter, I should be able to define the objects and state involved, state the governing invariant or contract, trace a small example without hand-waving, and explain which assumption makes the method valid. I should also be able to compare this model with the nearest alternative and say what failure would make me switch approaches.

\subsection{Deep notes}
\begin{itemize}
\item \textbf{Model.} Lists trade random access for cheap local insertion when a node position is known.
\item \textbf{Mechanism.} Mutations must preserve neighbor links, sentinels, size, and iterator-validity rules.
\item \textbf{Boundary.} The useful test is whether I can apply linked lists and iterator invariants to a new case and explain the assumption that makes the answer valid.
\item \textbf{Decision test.} I should be able to say when linked lists and iterator invariants is the right model, when its assumptions fail, and what evidence would change my choice.
\end{itemize}

\begin{studenttake}
I sketch links before assignments and save every pointer I am about to disconnect.
\end{studenttake}

\begin{plainbox}
Arrays find by arithmetic; lists find by following arrows but make local surgery cheap.
\end{plainbox}

\begin{examplebox}
Insert x between a and b by connecting x to both before repairing a.next and b.prev. The worked question below makes that reasoning concrete: State the invariant after doubly linked deletion. The conclusion is Every adjacent u,v satisfies u.next=v and v.prev=u; boundaries remain connected to sentinels and size decreases once.
\end{examplebox}

\begin{warningbox}
The common mistake is to memorize the visible procedure while dropping its precondition. I write the assumption beside the method and test one boundary case before trusting the result.
\end{warningbox}

\begin{chapterpractice}
\textbf{Practice.} State the invariant after doubly linked deletion.

\textbf{Solution.} Every adjacent u,v satisfies u.next=v and v.prev=u; boundaries remain connected to sentinels and size decreases once.

\medskip
\textbf{Practice 2.} Give a short oral explanation of linked lists and iterator invariants that includes its model, one assumption, one failure mode, and one comparison with a neighboring method.

\textbf{Solution.} A strong answer begins with the model in the blue box, names the assumption that licenses the method, uses the common miss above as the failure mode, and chooses the comparison according to the decision test in the deep notes. The goal is not one memorized sentence; it is a four-part explanation I can reproduce on a new example.

\medskip
\textbf{Mastery practice A.} Reconstruct linked lists and iterator invariants from a blank page. Include the central definition, the governing rule, one required assumption, and one boundary case.

\textbf{Solution.} Start from the blue idea box, but rewrite it in my own words. Identify the objects and state, name the rule before using it, copy the relevant assumption from the details audit, and choose a boundary where that assumption becomes equality or fails. A complete solution explains why each part belongs; a list of vocabulary is not enough.

\medskip
\textbf{Mastery practice B.} A classmate gets a polished-looking answer to a linked lists and iterator invariants problem but never states a model or checks the result. Write the shortest useful review of that solution.

\textbf{Solution.} I would ask four concrete questions: What exactly are the inputs and desired output? Which rule licenses the main step? Which assumption could invalidate it? Which independent check supports the conclusion? If the answer cannot survive those four questions, I treat the numerical or verbal result as unverified.

\end{chapterpractice}

\section{Stacks, queues, and frontiers}

\begin{idea}
Stacks resume newest unfinished work; queues resume oldest. The policy shapes algorithms: DFS uses a stack and BFS uses a queue.
\end{idea}
% MASTERCLASS EXPANSION
\subsection{Rebuild the chapter from first principles}
The claim I need to own is this: Stacks resume newest unfinished work; queues resume oldest. The policy shapes algorithms: DFS uses a stack and BFS uses a queue. I do not count that as learned just because the sentence looks familiar. I should be able to name the objects, state what changes and what stays fixed, recover the rule from the definitions, and explain why the result is allowed.

\begin{move}
\textbf{My working sequence}
\begin{enumerate}
  \item \textbf{Translate.} Rewrite the prompt in the language of stacks, queues, and frontiers. List the known quantities, the unknown, the units or types, and any hidden constraint.
  \item \textbf{Choose.} State the theorem, model, algorithm, accounting rule, or physical law before substituting values. This is where I make the assumption visible.
  \item \textbf{Execute.} Work one justified step at a time and keep intermediate state readable enough that I can audit it later.
  \item \textbf{Verify.} Check a boundary case, sign, unit, invariant, order of magnitude, or alternative derivation. Then translate the result back into an ordinary sentence.
\end{enumerate}
\end{move}

\subsection{Details I would refuse to skip}
\begin{itemize}
  \item \textbf{Definitions:} I should be able to define every technical noun in the chapter without using that same noun in the definition.
  \item \textbf{Assumptions:} I write the condition that makes the method legal beside the method itself. A correct procedure under the wrong assumptions is still a wrong answer.
  \item \textbf{Representation:} I move freely among words, equations or code, a diagram, and a small numerical example. If one representation disagrees with another, that disagreement is useful evidence.
  \item \textbf{Failure modes:} I keep the nearest counterexample in mind: the boundary where the rule changes, the invariant breaks, or the model stops matching reality.
  \item \textbf{Communication:} My final answer names what the result means and what it does not establish. I do not let notation do the explanatory work for me.
\end{itemize}

\begin{sanitybox}
\textbf{Closed-note check.} Can I teach stacks, queues, and frontiers on a blank page, derive or reconstruct its main rule, work a fresh example, and diagnose a deliberately broken solution? If I can only recognize the finished work, I am not done.
\end{sanitybox}

\subsection{How this chapter connects}
I read this chapter as the bridge from linked lists and iterator invariants to trees and binary search trees. The earlier material supplies the language and constraints; this chapter adds a new reasoning move; the later material asks me to use that move without being told its name. That connection matters because exams and real projects mix chapters on purpose.


\subsection{What I need to be able to do}
For this chapter, I should be able to define the objects and state involved, state the governing invariant or contract, trace a small example without hand-waving, and explain which assumption makes the method valid. I should also be able to compare this model with the nearest alternative and say what failure would make me switch approaches.

\subsection{Deep notes}
\begin{itemize}
\item \textbf{Model.} Stacks resume newest unfinished work; queues resume oldest.
\item \textbf{Mechanism.} The policy shapes algorithms: DFS uses a stack and BFS uses a queue.
\item \textbf{Boundary.} The useful test is whether I can apply stacks, queues, and frontiers to a new case and explain the assumption that makes the answer valid.
\item \textbf{Decision test.} I should be able to say when stacks, queues, and frontiers is the right model, when its assumptions fail, and what evidence would change my choice.
\end{itemize}

\begin{studenttake}
I ask what order pending work should resume instead of memorizing structure names.
\end{studenttake}

\begin{plainbox}
They are waiting-room policies: newest-first versus oldest-first.
\end{plainbox}

\begin{examplebox}
Balanced-parenthesis checking pushes opens and pops matching closes; BFS assigns unweighted distances layer by layer. The worked question below makes that reasoning concrete: Why is first BFS discovery a shortest path? The conclusion is The queue processes all distance d vertices before distance d+1, so a later route cannot use fewer edges.
\end{examplebox}

\begin{warningbox}
The common mistake is to memorize the visible procedure while dropping its precondition. I write the assumption beside the method and test one boundary case before trusting the result.
\end{warningbox}

\begin{chapterpractice}
\textbf{Practice.} Why is first BFS discovery a shortest path?

\textbf{Solution.} The queue processes all distance d vertices before distance d+1, so a later route cannot use fewer edges.

\medskip
\textbf{Practice 2.} Give a short oral explanation of stacks, queues, and frontiers that includes its model, one assumption, one failure mode, and one comparison with a neighboring method.

\textbf{Solution.} A strong answer begins with the model in the blue box, names the assumption that licenses the method, uses the common miss above as the failure mode, and chooses the comparison according to the decision test in the deep notes. The goal is not one memorized sentence; it is a four-part explanation I can reproduce on a new example.

\medskip
\textbf{Mastery practice A.} Reconstruct stacks, queues, and frontiers from a blank page. Include the central definition, the governing rule, one required assumption, and one boundary case.

\textbf{Solution.} Start from the blue idea box, but rewrite it in my own words. Identify the objects and state, name the rule before using it, copy the relevant assumption from the details audit, and choose a boundary where that assumption becomes equality or fails. A complete solution explains why each part belongs; a list of vocabulary is not enough.

\medskip
\textbf{Mastery practice B.} A classmate gets a polished-looking answer to a stacks, queues, and frontiers problem but never states a model or checks the result. Write the shortest useful review of that solution.

\textbf{Solution.} I would ask four concrete questions: What exactly are the inputs and desired output? Which rule licenses the main step? Which assumption could invalidate it? Which independent check supports the conclusion? If the answer cannot survive those four questions, I treat the numerical or verbal result as unverified.

\end{chapterpractice}

\section{Trees and binary search trees}

\begin{idea}
Trees encode hierarchy. Preorder visits parent first, postorder parent last, and inorder exposes BST sorted order. BST operations cost O(height), so unbalanced insertion can degrade to a list.
\end{idea}
% MASTERCLASS EXPANSION
\subsection{Rebuild the chapter from first principles}
The claim I need to own is this: Trees encode hierarchy. Preorder visits parent first, postorder parent last, and inorder exposes BST sorted order. BST operations cost O(height), so unbalanced insertion can degrade to a list. I do not count that as learned just because the sentence looks familiar. I should be able to name the objects, state what changes and what stays fixed, recover the rule from the definitions, and explain why the result is allowed.

\begin{move}
\textbf{My working sequence}
\begin{enumerate}
  \item \textbf{Translate.} Rewrite the prompt in the language of trees and binary search trees. List the known quantities, the unknown, the units or types, and any hidden constraint.
  \item \textbf{Choose.} State the theorem, model, algorithm, accounting rule, or physical law before substituting values. This is where I make the assumption visible.
  \item \textbf{Execute.} Work one justified step at a time and keep intermediate state readable enough that I can audit it later.
  \item \textbf{Verify.} Check a boundary case, sign, unit, invariant, order of magnitude, or alternative derivation. Then translate the result back into an ordinary sentence.
\end{enumerate}
\end{move}

\subsection{Details I would refuse to skip}
\begin{itemize}
  \item \textbf{Definitions:} I should be able to define every technical noun in the chapter without using that same noun in the definition.
  \item \textbf{Assumptions:} I write the condition that makes the method legal beside the method itself. A correct procedure under the wrong assumptions is still a wrong answer.
  \item \textbf{Representation:} I move freely among words, equations or code, a diagram, and a small numerical example. If one representation disagrees with another, that disagreement is useful evidence.
  \item \textbf{Failure modes:} I keep the nearest counterexample in mind: the boundary where the rule changes, the invariant breaks, or the model stops matching reality.
  \item \textbf{Communication:} My final answer names what the result means and what it does not establish. I do not let notation do the explanatory work for me.
\end{itemize}

\begin{sanitybox}
\textbf{Closed-note check.} Can I teach trees and binary search trees on a blank page, derive or reconstruct its main rule, work a fresh example, and diagnose a deliberately broken solution? If I can only recognize the finished work, I am not done.
\end{sanitybox}

\subsection{How this chapter connects}
I read this chapter as the bridge from stacks, queues, and frontiers to heaps, priority queues, and hashing. The earlier material supplies the language and constraints; this chapter adds a new reasoning move; the later material asks me to use that move without being told its name. That connection matters because exams and real projects mix chapters on purpose.


\subsection{What I need to be able to do}
For this chapter, I should be able to define the objects and state involved, state the governing invariant or contract, trace a small example without hand-waving, and explain which assumption makes the method valid. I should also be able to compare this model with the nearest alternative and say what failure would make me switch approaches.

\subsection{Deep notes}
\begin{itemize}
\item \textbf{Model.} Trees encode hierarchy.
\item \textbf{Mechanism.} Preorder visits parent first, postorder parent last, and inorder exposes BST sorted order.
\item \textbf{Boundary.} BST operations cost O(height), so unbalanced insertion can degrade to a list.
\item \textbf{Decision test.} I should be able to say when trees and binary search trees is the right model, when its assumptions fail, and what evidence would change my choice.
\end{itemize}

\begin{studenttake}
I choose traversal by asking when the parent has enough information.
\end{studenttake}

\begin{plainbox}
A tree is one node plus smaller trees; traversal decides when to open each nested box.
\end{plainbox}

\begin{examplebox}
Two-child BST deletion swaps with the inorder successor, reducing to a zero- or one-child case. The worked question below makes that reasoning concrete: What is the cost of visiting every node? The conclusion is Theta(n): each node contributes constant local work once. Balance affects root-to-leaf operations, not a full traversal.
\end{examplebox}

\begin{warningbox}
The common mistake is to memorize the visible procedure while dropping its precondition. I write the assumption beside the method and test one boundary case before trusting the result.
\end{warningbox}

\begin{chapterpractice}
\textbf{Practice.} What is the cost of visiting every node?

\textbf{Solution.} Theta(n): each node contributes constant local work once. Balance affects root-to-leaf operations, not a full traversal.

\medskip
\textbf{Practice 2.} Give a short oral explanation of trees and binary search trees that includes its model, one assumption, one failure mode, and one comparison with a neighboring method.

\textbf{Solution.} A strong answer begins with the model in the blue box, names the assumption that licenses the method, uses the common miss above as the failure mode, and chooses the comparison according to the decision test in the deep notes. The goal is not one memorized sentence; it is a four-part explanation I can reproduce on a new example.

\medskip
\textbf{Mastery practice A.} Reconstruct trees and binary search trees from a blank page. Include the central definition, the governing rule, one required assumption, and one boundary case.

\textbf{Solution.} Start from the blue idea box, but rewrite it in my own words. Identify the objects and state, name the rule before using it, copy the relevant assumption from the details audit, and choose a boundary where that assumption becomes equality or fails. A complete solution explains why each part belongs; a list of vocabulary is not enough.

\medskip
\textbf{Mastery practice B.} A classmate gets a polished-looking answer to a trees and binary search trees problem but never states a model or checks the result. Write the shortest useful review of that solution.

\textbf{Solution.} I would ask four concrete questions: What exactly are the inputs and desired output? Which rule licenses the main step? Which assumption could invalidate it? Which independent check supports the conclusion? If the answer cannot survive those four questions, I treat the numerical or verbal result as unverified.

\end{chapterpractice}

\section{Heaps, priority queues, and hashing}

\begin{idea}
A heap maintains parent-child order in a complete array-backed tree; only the root is globally guaranteed. Hash tables map keys to buckets and manage inevitable collisions through chaining or probing.
\end{idea}
% MASTERCLASS EXPANSION
\subsection{Rebuild the chapter from first principles}
The claim I need to own is this: A heap maintains parent-child order in a complete array-backed tree; only the root is globally guaranteed. Hash tables map keys to buckets and manage inevitable collisions through chaining or probing. I do not count that as learned just because the sentence looks familiar. I should be able to name the objects, state what changes and what stays fixed, recover the rule from the definitions, and explain why the result is allowed.

\begin{move}
\textbf{My working sequence}
\begin{enumerate}
  \item \textbf{Translate.} Rewrite the prompt in the language of heaps, priority queues, and hashing. List the known quantities, the unknown, the units or types, and any hidden constraint.
  \item \textbf{Choose.} State the theorem, model, algorithm, accounting rule, or physical law before substituting values. This is where I make the assumption visible.
  \item \textbf{Execute.} Work one justified step at a time and keep intermediate state readable enough that I can audit it later.
  \item \textbf{Verify.} Check a boundary case, sign, unit, invariant, order of magnitude, or alternative derivation. Then translate the result back into an ordinary sentence.
\end{enumerate}
\end{move}

\subsection{Details I would refuse to skip}
\begin{itemize}
  \item \textbf{Definitions:} I should be able to define every technical noun in the chapter without using that same noun in the definition.
  \item \textbf{Assumptions:} I write the condition that makes the method legal beside the method itself. A correct procedure under the wrong assumptions is still a wrong answer.
  \item \textbf{Representation:} I move freely among words, equations or code, a diagram, and a small numerical example. If one representation disagrees with another, that disagreement is useful evidence.
  \item \textbf{Failure modes:} I keep the nearest counterexample in mind: the boundary where the rule changes, the invariant breaks, or the model stops matching reality.
  \item \textbf{Communication:} My final answer names what the result means and what it does not establish. I do not let notation do the explanatory work for me.
\end{itemize}

\begin{sanitybox}
\textbf{Closed-note check.} Can I teach heaps, priority queues, and hashing on a blank page, derive or reconstruct its main rule, work a fresh example, and diagnose a deliberately broken solution? If I can only recognize the finished work, I am not done.
\end{sanitybox}

\subsection{How this chapter connects}
I read this chapter as the bridge from trees and binary search trees to graphs and representations. The earlier material supplies the language and constraints; this chapter adds a new reasoning move; the later material asks me to use that move without being told its name. That connection matters because exams and real projects mix chapters on purpose.


\subsection{What I need to be able to do}
For this chapter, I should be able to define the objects and state involved, state the governing invariant or contract, trace a small example without hand-waving, and explain which assumption makes the method valid. I should also be able to compare this model with the nearest alternative and say what failure would make me switch approaches.

\subsection{Deep notes}
\begin{itemize}
\item \textbf{Model.} A heap maintains parent-child order in a complete array-backed tree; only the root is globally guaranteed.
\item \textbf{Mechanism.} Hash tables map keys to buckets and manage inevitable collisions through chaining or probing.
\item \textbf{Boundary.} The useful test is whether I can apply heaps, priority queues, and hashing to a new case and explain the assumption that makes the answer valid.
\item \textbf{Decision test.} I should be able to say when heaps, priority queues, and hashing is the right model, when its assumptions fail, and what evidence would change my choice.
\end{itemize}

\begin{studenttake}
I never call a heap sorted, and I expect hash collisions instead of treating them as bugs.
\end{studenttake}

\begin{plainbox}
A heap keeps the next priority accessible; a hash table jumps near where a key should live.
\end{plainbox}

\begin{examplebox}
Removing a heap root moves the last value to index zero and sifts toward the better child. The worked question below makes that reasoning concrete: Why can hashing degrade to O(n)? The conclusion is A poor distribution can place many keys in one bucket or cluster. A sound hash and controlled load factor preserve expected constant time.
\end{examplebox}

\begin{warningbox}
The common mistake is to memorize the visible procedure while dropping its precondition. I write the assumption beside the method and test one boundary case before trusting the result.
\end{warningbox}

\begin{chapterpractice}
\textbf{Practice.} Why can hashing degrade to O(n)?

\textbf{Solution.} A poor distribution can place many keys in one bucket or cluster. A sound hash and controlled load factor preserve expected constant time.

\medskip
\textbf{Practice 2.} Give a short oral explanation of heaps, priority queues, and hashing that includes its model, one assumption, one failure mode, and one comparison with a neighboring method.

\textbf{Solution.} A strong answer begins with the model in the blue box, names the assumption that licenses the method, uses the common miss above as the failure mode, and chooses the comparison according to the decision test in the deep notes. The goal is not one memorized sentence; it is a four-part explanation I can reproduce on a new example.

\medskip
\textbf{Mastery practice A.} Reconstruct heaps, priority queues, and hashing from a blank page. Include the central definition, the governing rule, one required assumption, and one boundary case.

\textbf{Solution.} Start from the blue idea box, but rewrite it in my own words. Identify the objects and state, name the rule before using it, copy the relevant assumption from the details audit, and choose a boundary where that assumption becomes equality or fails. A complete solution explains why each part belongs; a list of vocabulary is not enough.

\medskip
\textbf{Mastery practice B.} A classmate gets a polished-looking answer to a heaps, priority queues, and hashing problem but never states a model or checks the result. Write the shortest useful review of that solution.

\textbf{Solution.} I would ask four concrete questions: What exactly are the inputs and desired output? Which rule licenses the main step? Which assumption could invalidate it? Which independent check supports the conclusion? If the answer cannot survive those four questions, I treat the numerical or verbal result as unverified.

\end{chapterpractice}

\section{Graphs and representations}

\begin{idea}
Graphs preserve vertices and relationships; direction and weight are modeling choices. Lists use O(V+E) space and suit sparse neighbor scans; matrices use O(V\textasciicircum{}2) but test one edge in O(1).
\end{idea}
% MASTERCLASS EXPANSION
\subsection{Rebuild the chapter from first principles}
The claim I need to own is this: Graphs preserve vertices and relationships; direction and weight are modeling choices. Lists use O(V+E) space and suit sparse neighbor scans; matrices use O(V\textasciicircum{}2) but test one edge in O(1). I do not count that as learned just because the sentence looks familiar. I should be able to name the objects, state what changes and what stays fixed, recover the rule from the definitions, and explain why the result is allowed.

\begin{move}
\textbf{My working sequence}
\begin{enumerate}
  \item \textbf{Translate.} Rewrite the prompt in the language of graphs and representations. List the known quantities, the unknown, the units or types, and any hidden constraint.
  \item \textbf{Choose.} State the theorem, model, algorithm, accounting rule, or physical law before substituting values. This is where I make the assumption visible.
  \item \textbf{Execute.} Work one justified step at a time and keep intermediate state readable enough that I can audit it later.
  \item \textbf{Verify.} Check a boundary case, sign, unit, invariant, order of magnitude, or alternative derivation. Then translate the result back into an ordinary sentence.
\end{enumerate}
\end{move}

\subsection{Details I would refuse to skip}
\begin{itemize}
  \item \textbf{Definitions:} I should be able to define every technical noun in the chapter without using that same noun in the definition.
  \item \textbf{Assumptions:} I write the condition that makes the method legal beside the method itself. A correct procedure under the wrong assumptions is still a wrong answer.
  \item \textbf{Representation:} I move freely among words, equations or code, a diagram, and a small numerical example. If one representation disagrees with another, that disagreement is useful evidence.
  \item \textbf{Failure modes:} I keep the nearest counterexample in mind: the boundary where the rule changes, the invariant breaks, or the model stops matching reality.
  \item \textbf{Communication:} My final answer names what the result means and what it does not establish. I do not let notation do the explanatory work for me.
\end{itemize}

\begin{sanitybox}
\textbf{Closed-note check.} Can I teach graphs and representations on a blank page, derive or reconstruct its main rule, work a fresh example, and diagnose a deliberately broken solution? If I can only recognize the finished work, I am not done.
\end{sanitybox}

\subsection{How this chapter connects}
I read this chapter as the bridge from heaps, priority queues, and hashing to sorting and binary search. The earlier material supplies the language and constraints; this chapter adds a new reasoning move; the later material asks me to use that move without being told its name. That connection matters because exams and real projects mix chapters on purpose.


\subsection{What I need to be able to do}
For this chapter, I should be able to define the objects and state involved, state the governing invariant or contract, trace a small example without hand-waving, and explain which assumption makes the method valid. I should also be able to compare this model with the nearest alternative and say what failure would make me switch approaches.

\subsection{Deep notes}
\begin{itemize}
\item \textbf{Model.} Graphs preserve vertices and relationships; direction and weight are modeling choices.
\item \textbf{Mechanism.} Lists use O(V+E) space and suit sparse neighbor scans; matrices use O(V\textasciicircum{}2) but test one edge in O(1).
\item \textbf{Boundary.} The useful test is whether I can apply graphs and representations to a new case and explain the assumption that makes the answer valid.
\item \textbf{Decision test.} I should be able to say when graphs and representations is the right model, when its assumptions fail, and what evidence would change my choice.
\end{itemize}

\begin{studenttake}
The drawing is not the graph. I name what vertices and edges mean before choosing storage.
\end{studenttake}

\begin{plainbox}
Graphs keep relationships and discard coordinates.
\end{plainbox}

\begin{examplebox}
A prerequisite DAG can be topologically sorted; a detected cycle means the requirements are inconsistent. The worked question below makes that reasoning concrete: Compare neighbor iteration in lists and matrices. The conclusion is A list costs Theta(degree(u)); a matrix scans Theta(V). The matrix trades space for constant-time edge lookup.
\end{examplebox}

\begin{warningbox}
The common mistake is to memorize the visible procedure while dropping its precondition. I write the assumption beside the method and test one boundary case before trusting the result.
\end{warningbox}

\begin{chapterpractice}
\textbf{Practice.} Compare neighbor iteration in lists and matrices.

\textbf{Solution.} A list costs Theta(degree(u)); a matrix scans Theta(V). The matrix trades space for constant-time edge lookup.

\medskip
\textbf{Practice 2.} Give a short oral explanation of graphs and representations that includes its model, one assumption, one failure mode, and one comparison with a neighboring method.

\textbf{Solution.} A strong answer begins with the model in the blue box, names the assumption that licenses the method, uses the common miss above as the failure mode, and chooses the comparison according to the decision test in the deep notes. The goal is not one memorized sentence; it is a four-part explanation I can reproduce on a new example.

\medskip
\textbf{Mastery practice A.} Reconstruct graphs and representations from a blank page. Include the central definition, the governing rule, one required assumption, and one boundary case.

\textbf{Solution.} Start from the blue idea box, but rewrite it in my own words. Identify the objects and state, name the rule before using it, copy the relevant assumption from the details audit, and choose a boundary where that assumption becomes equality or fails. A complete solution explains why each part belongs; a list of vocabulary is not enough.

\medskip
\textbf{Mastery practice B.} A classmate gets a polished-looking answer to a graphs and representations problem but never states a model or checks the result. Write the shortest useful review of that solution.

\textbf{Solution.} I would ask four concrete questions: What exactly are the inputs and desired output? Which rule licenses the main step? Which assumption could invalidate it? Which independent check supports the conclusion? If the answer cannot survive those four questions, I treat the numerical or verbal result as unverified.

\end{chapterpractice}

\section{Sorting and binary search}

\begin{idea}
Binary search maintains a candidate-interval invariant over a monotone predicate. Stable sorting preserves equal-key order. Comparison sorting has an Omega(n log n) worst-case lower bound, while key-structured methods use extra assumptions.
\end{idea}
% MASTERCLASS EXPANSION
\subsection{Rebuild the chapter from first principles}
The claim I need to own is this: Binary search maintains a candidate-interval invariant over a monotone predicate. Stable sorting preserves equal-key order. Comparison sorting has an Omega(n log n) worst-case lower bound, while key-structured methods use extra assumptions. I do not count that as learned just because the sentence looks familiar. I should be able to name the objects, state what changes and what stays fixed, recover the rule from the definitions, and explain why the result is allowed.

\begin{move}
\textbf{My working sequence}
\begin{enumerate}
  \item \textbf{Translate.} Rewrite the prompt in the language of sorting and binary search. List the known quantities, the unknown, the units or types, and any hidden constraint.
  \item \textbf{Choose.} State the theorem, model, algorithm, accounting rule, or physical law before substituting values. This is where I make the assumption visible.
  \item \textbf{Execute.} Work one justified step at a time and keep intermediate state readable enough that I can audit it later.
  \item \textbf{Verify.} Check a boundary case, sign, unit, invariant, order of magnitude, or alternative derivation. Then translate the result back into an ordinary sentence.
\end{enumerate}
\end{move}

\subsection{Details I would refuse to skip}
\begin{itemize}
  \item \textbf{Definitions:} I should be able to define every technical noun in the chapter without using that same noun in the definition.
  \item \textbf{Assumptions:} I write the condition that makes the method legal beside the method itself. A correct procedure under the wrong assumptions is still a wrong answer.
  \item \textbf{Representation:} I move freely among words, equations or code, a diagram, and a small numerical example. If one representation disagrees with another, that disagreement is useful evidence.
  \item \textbf{Failure modes:} I keep the nearest counterexample in mind: the boundary where the rule changes, the invariant breaks, or the model stops matching reality.
  \item \textbf{Communication:} My final answer names what the result means and what it does not establish. I do not let notation do the explanatory work for me.
\end{itemize}

\begin{sanitybox}
\textbf{Closed-note check.} Can I teach sorting and binary search on a blank page, derive or reconstruct its main rule, work a fresh example, and diagnose a deliberately broken solution? If I can only recognize the finished work, I am not done.
\end{sanitybox}

\subsection{How this chapter connects}
I read this chapter as the bridge from graphs and representations to the cumulative course model. The earlier material supplies the language and constraints; this chapter adds a new reasoning move; the later material asks me to use that move without being told its name. That connection matters because exams and real projects mix chapters on purpose.


\subsection{What I need to be able to do}
For this chapter, I should be able to define the objects and state involved, state the governing invariant or contract, trace a small example without hand-waving, and explain which assumption makes the method valid. I should also be able to compare this model with the nearest alternative and say what failure would make me switch approaches.

\subsection{Deep notes}
\begin{itemize}
\item \textbf{Model.} Binary search maintains a candidate-interval invariant over a monotone predicate.
\item \textbf{Mechanism.} Stable sorting preserves equal-key order.
\item \textbf{Boundary.} Comparison sorting has an Omega(n log n) worst-case lower bound, while key-structured methods use extra assumptions.
\item \textbf{Decision test.} I should be able to say when sorting and binary search is the right model, when its assumptions fail, and what evidence would change my choice.
\end{itemize}

\begin{studenttake}
I write binary search as an interval proof, not a memorized midpoint loop.
\end{studenttake}

\begin{plainbox}
Search repeatedly discards impossible regions; sorting invests work now to make later questions cheaper.
\end{plainbox}

\begin{examplebox}
Merge sort guarantees Theta(n log n) with extra storage; quicksort is in-place and usually fast but pivot-sensitive. The worked question below makes that reasoning concrete: State the lower\_bound invariant. The conclusion is Below lo values are less than target; at or above hi values are at least target. Shrinking [lo,hi) until empty leaves the first legal index.
\end{examplebox}

\begin{warningbox}
The common mistake is to memorize the visible procedure while dropping its precondition. I write the assumption beside the method and test one boundary case before trusting the result.
\end{warningbox}

\begin{chapterpractice}
\textbf{Practice.} State the lower\_bound invariant.

\textbf{Solution.} Below lo values are less than target; at or above hi values are at least target. Shrinking [lo,hi) until empty leaves the first legal index.

\medskip
\textbf{Practice 2.} Give a short oral explanation of sorting and binary search that includes its model, one assumption, one failure mode, and one comparison with a neighboring method.

\textbf{Solution.} A strong answer begins with the model in the blue box, names the assumption that licenses the method, uses the common miss above as the failure mode, and chooses the comparison according to the decision test in the deep notes. The goal is not one memorized sentence; it is a four-part explanation I can reproduce on a new example.

\medskip
\textbf{Mastery practice A.} Reconstruct sorting and binary search from a blank page. Include the central definition, the governing rule, one required assumption, and one boundary case.

\textbf{Solution.} Start from the blue idea box, but rewrite it in my own words. Identify the objects and state, name the rule before using it, copy the relevant assumption from the details audit, and choose a boundary where that assumption becomes equality or fails. A complete solution explains why each part belongs; a list of vocabulary is not enough.

\medskip
\textbf{Mastery practice B.} A classmate gets a polished-looking answer to a sorting and binary search problem but never states a model or checks the result. Write the shortest useful review of that solution.

\textbf{Solution.} I would ask four concrete questions: What exactly are the inputs and desired output? Which rule licenses the main step? Which assumption could invalidate it? Which independent check supports the conclusion? If the answer cannot survive those four questions, I treat the numerical or verbal result as unverified.

\end{chapterpractice}

\section*{Final study check}
I should be able to close this packet and reconstruct the core models, not merely recognize their names. My final check is to explain one complete problem aloud: what the inputs mean, which invariant or contract controls the work, why the method is legal, what it costs, how it can fail, and what evidence would convince another engineer.

\end{document}
