Speaker note: Welcome to week one — today builds the two foundations every later week stands on: how to measure cost, and how memory actually works.
Speaker note: Fourteen short animations carry most of today's lecture; each appears once, with a second look at its trickiest case.
Speaker note: Every term gets a full definition the first time it appears; this table just says where to find it again.
Speaker note: Open a terminal now if you want to run these live; every snippet on today's slides compiles and runs exactly as shown.
Speaker note: In class we only touch the highlights — read the syllabus, project guide and prerequisites page before next week.
Speaker note: Pick a team early — the rule exists so a team's work has time to build momentum before it locks in.
Speaker note: Data structures is a course about exactly two things: how to arrange data in memory, and how much that arrangement costs.
Speaker note: Section 1 asks the most basic question of the whole course, before we touch any code at all.
Speaker note: The arrangement of the names IS the difference — that arrangement is what we call a data structure.
Speaker note: The ADT distinction — what versus how — is one this course leans on constantly, starting informally today.
Speaker note: A stack of trays is fast to add/take from the top, terrible for finding something in the middle — that is the whole idea.
Speaker note: "Known, analyzable cost" is the part that turns a vague idea of "organizing data" into something this course can measure.
Speaker note: You cannot usually have all four operations be fast at once in the same structure — that trade-off is today's real subject.
Speaker note: Let the class answer before advancing.
Speaker note: This one sentence is the reason the rest of the semester introduces one new structure per week.
Speaker note: Every structure this semester falls into exactly one of these two families — this map is worth remembering.
Speaker note: It changes what operations are cheap or expensive — that is the whole point of today's second section.
Speaker note: A tree node can have several children; a graph node can connect to several others — no single "next" any more.
Speaker note: All four are linear — every element still has exactly one next.
Speaker note: Hash tables and files are still linear in how their slots sit — only the access pattern, by key, is new; Week 7 makes this explicit.
Speaker note: A tree and a graph are extremely structured — they simply allow more than one "next".
Speaker note: Let the class answer, then advance.
Speaker note: A single, unambiguous next in both directions is exactly the linear definition.
Speaker note: Let the class answer, then advance.
Speaker note: This is the same branching idea as the org chart from two slides ago.
Speaker note: This is the biggest section today — the tool, Big-O, that every later week uses to judge a structure.
Speaker note: What we want is a property of the algorithm itself: how its work grows as the input grows.
Speaker note: The notation predates computers by decades — it originally described how closely one function approximates another.
Speaker note: That count depends only on the algorithm and n — never on the machine, the language, or today's CPU load.
Speaker note: We will watch it count comparisons on an 11-element array, hunting for a value in the middle.
Speaker note: Normal example: 11 values, target in the middle. Watch the comparison counter climb one box at a time.
Speaker note: When the target is missing, linear search still checks every single box before it can say so — the true worst case.
Speaker note: One comparison per iteration, counted explicitly — this is exactly what the animation just counted on screen.
Speaker note: A million-element array would need up to a million comparisons in the worst case — that direct growth is O(n).
Speaker note: We will search for the same target, 42, that just took linear search 9 comparisons.
Speaker note: Normal example: 16 sorted values, target found. Watch lo, hi and mid close in on the answer.
Speaker note: 31 values this time; the range keeps halving until lo is greater than hi — nothing left to check.
Speaker note: One comparison eliminates half of whatever is left — that halving is the entire trick.
Speaker note: The trade-off: binary search needs the array sorted first, and sorting itself costs more than one search.
Speaker note: Two points on a much larger scale — this animation shows the whole scale at once.
Speaker note: Normal example: n doubling from 1 to 512. Watch n-squared and 2^n pull away from the rest.
Speaker note: Starting at n = 400, 2^n is already far too large to draw on the same chart as the others.
Speaker note: At n = 100,000, n-squared is over 6,000 times larger than n log n — instant on a toy input, very different at scale.
Speaker note: This is exactly the loop that produced the table you just saw, for five realistic sizes.
Speaker note: You rarely compute the constants formally — you count the steps and read off the fastest-growing term.
Speaker note: The pattern: keep the fastest-growing term, throw away everything smaller and every constant.
Speaker note: O(1) is constant-time array access from pointer arithmetic; O(log n) is binary search; O(n) is linear search.
Speaker note: Instead of trusting the table, let's count a real, counted program and see n-squared appear for ourselves.
Speaker note: Normal example: a square loop (j < n), n = 3 shown in full detail, then nine more n values.
Speaker note: A triangle loop (j < i) still runs the inner body n(n-1)/2 times — still O(n squared), a different constant.
Speaker note: The measured count matched n*n exactly for every n tried — T(n) = n squared, plus smaller dropped terms.
Speaker note: The worst case is the guarantee that matters most when you cannot control the input.
Speaker note: A recursive function pushes one stack frame per call; that is extra memory a loop never needs.
Speaker note: Normal example: 10 values. Watch the call stack grow one frame per call, then unwind.
Speaker note: 22 elements means 23 frames at the peak — the stack really can run out for large enough n.
Speaker note: Both return the same sum. sum_recursive uses O(n) stack space; sum_iterative always uses exactly O(1).
Speaker note: A hidden loop inside a line (like arr.contains(x)) can quietly turn an O(n) loop into O(n squared).
Speaker note: Let the class answer, then advance.
Speaker note: This is the "read off the dominant term" table applied directly.
Speaker note: Let the class answer, then advance.
Speaker note: Week 2 builds exactly this structure, so this question previews next week directly.
Speaker note: Let the class answer, then advance.
Speaker note: Best cases tend to look similar across algorithms, which is exactly why the worst case is more useful to compare.
Speaker note: A pointer is the location of a variable, not just its value — today we make that idea completely concrete.
Speaker note: To reach back into the caller's variables, a function needs the LOCATION of each one, not just its value — that location is a pointer.
Speaker note: You can still have two Java variables name the same object — you just cannot compute an arbitrary address.
Speaker note: int x = 3 puts 3 in some mailbox, say number 1000 — &x gets you that 1000.
Speaker note: Every one of these is O(1) — following a pointer is always a single jump, never a search.
Speaker note: Normal example: five operations — address-of, write through, copy (alias), move, add through the alias.
Speaker note: A write through a NULL pointer is never executed here — it is flagged as undefined behavior instead.
Speaker note: q = p copies the ADDRESS, not the value — q and p now alias the same variable.
Speaker note: alias is a second name for the SAME array as box; y is an independent COPY of x — same syntax shape, opposite behavior.
Speaker note: This is the O(1) arithmetic that array indexing, arr[i], compiles down to.
Speaker note: Normal example: an int array, five valid offsets. Watch each computed address and its dereferenced value.
Speaker note: A negative offset and one past the end are both flagged as undefined behavior, never dereferenced.
Speaker note: Java has no pointer arithmetic at all — only a[k], and an out-of-range k throws a clear exception.
Speaker note: A pointer to a struct lets you reach — and modify — the ORIGINAL struct, not a copy of it.
Speaker note: Normal example: 10 students, 2 grade updates. Watch (*p).id, p->grade, and p++ advance by sizeof(Student).
Speaker note: p reaches "one past the end" immediately — legal to HOLD, but never to dereference.
Speaker note: (*p).id and p->id are the same value — the arrow is purely a shorthand, nothing more.
Speaker note: Java checks every dereference and fails loudly; C simply does whatever the hardware does with a bad address.
Speaker note: Let the class answer, then advance.
Speaker note: Same variable, two completely different questions depending on whether you dereference it.
Speaker note: Let the class answer, then advance.
Speaker note: C needs both . (for values) and -> (for pointers); Java only ever needs one.
Speaker note: This is the single most important fact about memory you will use all semester.
Speaker note: The two questions have completely different answers — that difference is today's whole subject.
Speaker note: GC is much older than most people assume — it predates Java by 36 years.
Speaker note: Pushing or popping a stack frame is just moving one pointer — that is why it is so fast.
Speaker note: A stack overflow is deep recursion outrunning a small, fixed region; the heap is much larger but slower.
Speaker note: Normal example: 10 blocks, properly owned, some freed. Watch main's blocks[] column point at each heap row.
Speaker note: A second alias still holds a freed block's old address; using it is flagged as UB, never executed.
Speaker note: p is local to alloc_block's own frame — only the RETURNED address survives once that frame pops.
Speaker note: An object lives on the heap until the garbage collector proves nothing can reach it any more.
Speaker note: Normal example: a reference chain, ordinary collection. Watch objects become unreachable and get swept.
Speaker note: Two objects point at each other, but once NO root reaches either, both are collected — reachability, not reference counting.
Speaker note: In C, this exact pattern would leak forever — C has no garbage collector to notice the cycle is unreachable.
Speaker note: An object you keep an unneeded reference to cannot be collected, and still "leaks" in effect.
Speaker note: Next week you build exactly this linked structure — today is only the preview.
Speaker note: Normal example: 10 values, k = 4. Compare one computed address versus four hops through next.
Speaker note: The array still reaches the last element in one step; the linked list needs every single hop from the head.
Speaker note: Same n values, opposite access cost: array O(1), linked list O(n) — same data, completely different shape.
Speaker note: Let the class answer, then advance.
Speaker note: The fix: allocate with malloc instead, so the memory survives the function returning.
Speaker note: Let the class answer, then advance.
Speaker note: The order is not a style choice — reversing it silently creates a memory leak.
Speaker note: Let the class answer, then advance.
Speaker note: There is never a moment where a reachable reference points at memory already taken back.
Speaker note: How do two completely different programs agree, byte for byte, on a structured record?
Speaker note: The compiler, platform and padding rules all affect a struct's exact byte layout — we need something both sides agree on.
Speaker note: ASN.1 with BER still underlies X.509 certificates — the basis of HTTPS — LDAP, and SNMP, invisibly.
Speaker note: A decoder that has never seen your record before can still walk it correctly: read tag, read length, skip that many bytes, repeat.
Speaker note: INTEGER is tag 0x02, UTF8String is tag 0x0C, SEQUENCE is tag 0x30 — real ASN.1 universal-class numbers.
Speaker note: Normal example: 10 fields — integers, short strings, booleans — each becomes Tag, Length, Value.
Speaker note: A 300-character string's length no longer fits in one byte — the long form spends extra bytes just to say "how many".
Speaker note: The short form is one byte; the long form's top bit set means "the next n bytes ARE the length".
Speaker note: Both encode the same abstract information — BER trades size for self-description, PER trades the reverse.
Speaker note: The same kind of record as BER, this time packed bit by bit instead of byte by byte.
Speaker note: Normal example: 10 fields — name characters, an age, a few constrained numbers — packed into a handful of bytes.
Speaker note: When min equals max, there is only one possible value — the receiver already knows it, so NOTHING is sent.
Speaker note: PER output is only byte-aligned at the very end, not field by field — bits pack right up against each other.
Speaker note: A PER decoder cannot parse BER bytes, or vice versa — two different byte formats for the same schema.
Speaker note: Let the class answer, then advance.
Speaker note: A decoder never has to guess a size — the length prefix always tells it exactly.
Speaker note: Let the class answer, then advance.
Speaker note: 00 1 10000 in binary is exactly 0x30 — the constructed bit is what changes 0x10 into 0x30.
Speaker note: Every idea today is worthless until it compiles and runs — this section sets up the workflow for the whole semester.
Speaker note: This lab sets up, once, the exact workflow you repeat all semester: compile, run, debug.
Speaker note: A compiler translates source to machine code; a linker stitches it together with the C standard library.
Speaker note: gcc compiles hello_workshop.c into x; && only runs it if the compile succeeded.
Speaker note: A warning is the compiler telling you something is probably a bug, before you find out the hard way at runtime.
Speaker note: The average it prints is wrong — sum and n look right, but something in the last line is not.
Speaker note: This scales to bugs far subtler than the one we are about to find.
Speaker note: Normal example: 10 elements. Watch i, sum and n in the watch panel as we step, then print sum / n.
Speaker note: n == 0 stops the program right at the guard line — dividing by zero would be undefined behavior.
Speaker note: sum/n gives 7 (integer division); (double) sum/n gives the real answer, 7.666... — the bug was only in the final division.
Speaker note: The first command CONFIGURES: reads CMakeLists.txt, checks the compiler. The second BUILDS: compiles and links.
Speaker note: Visual Studio can open a CMakeLists.txt directly — the same file from the last slide works unchanged.
Speaker note: Always chain the run with && so a failed compile never lets you run yesterday's binary by accident.
Speaker note: Let the class answer, then advance.
Speaker note: Not discovered later, at runtime, the hard way.
Speaker note: Let the class answer, then advance.
Speaker note: Configure once (usually), build every time you change the source.
Speaker note: Every later week adds one more structure, judged with exactly these same tools.
Speaker note: Pointers, the stack and the heap are the picture of memory every later week assumes you already have.
Speaker note: If a student remembers only one sentence from today, this is the one worth remembering.
Speaker note: These mirror the self-check quiz at the end of the written notes, one question per slide, a shorter set here.
Speaker note: Ask, wait, then advance.
Speaker note: Correctness and cost are two completely separate questions.
Speaker note: Ask, wait, then advance.
Speaker note: This exact order comes back every single week for the rest of the semester.
Speaker note: Ask, wait, then advance.
Speaker note: Without sorted order, discarding a whole half would be a guess, not a guarantee.
Speaker note: Ask, wait, then advance.
Speaker note: Length never counts the Tag byte or its own Length byte(s).
Speaker note: Ask, wait, then advance.
Speaker note: Dereference-then-access is such a frequent pattern that C gave it its own operator.
Speaker note: The O(1)-insert-anywhere, O(n)-access trade-off from today's preview, now in full: insertion, deletion, traversal, measured.
Speaker note: These are the same references listed at the end of the week's written notes.
Speaker note: The historical references — Bachmann, Landau, Knuth, Liskov, Cayley's spirit of counting structures — are what today's "short history" slides drew on.