DSM-103 Data Structures · full course recap · S01 → 21 Sep (Dey, Prakash)
S01 (18 Aug) · S02 (20 Aug) — Dey
The vocabulary, the address formula, and the first three array operations — all written with L and U, never a language's own indexing.
max().int float char double).101 with a sign bit; float 5.5 = 55×10⁻¹ → sign | exponent | mantissa; char → an unsigned code. So a slot built for one type can't hold another. (Python's mixed lists hide this in library code.)L…U, contiguous; free space elsewhere is useless to it | linked list: grabs scattered free blocks and links themI ← L; while I ≤ U: process A[I]; I ← I+1. O(n) time, O(1) space.I, then I ← I−1. Inner loop is J < I, not ≤, or A[J+1] doesn't exist. O(n²) time, O(1) space. Flip the test for descending.FOUND flag + LOCATION (start at 0, or a negative number if 0 is a valid index). Loop ends for two reasons, so test FOUND after it. Best O(1), worst O(n).while / for check the condition first; do-while runs the body once before checking. With I = 5 and condition 5 < 4: while → 0 runs, do-while → 1 run.SUBSTRING. So write algorithms with L/U and let the formula absorb the difference.Why a data scientist needs this (S01):
The amber frame is the pair being compared (J, J+1). The teal zone is the settled part to the right of I. Watch the largest value ride to the end of each pass.
← → step · space play/pause (click the panel first)
1003
1002
I ← U, decrement, and stop at the first match. That first match from the right is the last occurrence.FOUND = 0 from the loop test and overwrite LOCATION ← I on every match. You always scan all n elements.last: I ← U, decrement · all: flag array, O(n) space
J < I and not J ≤ I?S02 20 Augso that A[J+1] always exists
20 elements · 2028
4 3 2 1: how many comparisons and swaps? (Type it into the widget to watch.)practice6 comparisons, 6 swaps
I = 5; do { print I; I = I + 1 } while (I < 4) — what prints?practicewhile loop would have printed nothing.5 (once)
S03 (22 Aug) — Dey · S06 said exams ask indexing calculations
Memory is a single line, so a grid has to be flattened. Every formula here comes from one method: count what is stored before the element.
| matrix (n × n, 1-based) | stored per row | row-major index of $a_{ij}$ | column-major index of $a_{ij}$ |
|---|---|---|---|
| lower-left triangular ($j \le i$) | row $i$ has $i$ | $\frac{i(i-1)}{2} + j$ | $n(j-1) - \frac{(j-1)(j-2)}{2} + (i-j+1)$ |
| upper-right triangular ($j \ge i$) | row $i$ has $n-i+1$ | $n(i-1) - \frac{(i-1)(i-2)}{2} + (j-i+1)$ | $\frac{j(j-1)}{2} + i$ |
| diagonal ($i = j$) | 1 | $i$ (both orders agree) | |
| tridiagonal ($|i-j| \le 1$) | 2, 3, 3, …, 3, 2 | $2i + j - 2$ | $2j + i - 2$ |
| α–β band, case 1: $i \le \beta$ | $\alpha + i - 1$ (growing) | $(i-1)\alpha + \frac{(i-1)(i-2)}{2} + j$ | |
| α–β band, case 2: $\beta < i \le n-\alpha+1$ | $\alpha+\beta-1$ (full) | $\beta\alpha + \frac{\beta(\beta-1)}{2} + (i-\beta-1)(\alpha+\beta-1) + (j-i+\beta)$ | |
| α–β band, case 3: $i > n-\alpha+1$ | shrinking | case-2 prefix up to row $n-\alpha+1$ $+ \sum_{k=n-\alpha+2}^{i-1}(n-k+\beta) + (j-i+\beta)$ | |
Upper-right is lower-left with the roles of i and j swapped ("i will be j, j will be i"). Band: α = cells in row 1 (the diagonal plus everything to its right), β = cells in column 1 (the diagonal plus everything below). The case formulas need α + β ≤ n + 1. All formulas above were checked against a brute-force count for every n up to 9.
Why bother (S03):
Click any cell to make it the target, then press Count it. Cells light up in storage order while the 1-D strip below fills in. The breakdown shows the lecture formula term by term.
row-major 7 (address 106) · column-major 8
5 in both orders (the same number by coincidence)
18 + 30 + 5 = 53 → Address = B + 52·w
Index 8 · Address 528
33 · 36
same method: stored-before + offset from the row's first stored cell
S04 (29 Aug) · S05 (3 Sep) — Dey · S06 said exams ask you to fill in missing algorithm steps
Data goes wherever memory is free, and each node remembers where the next one is. Almost every bug comes from one of three things: where the pointer starts, which test ends the loop, or the order of two assignments.
[data | link], where link = the address of the next node. Every node has the same fields.DATA[k] holds the value, LINK[k] holds the index of the next one. Fixed size.getNode() returns a fresh node's address, or NULL when memory is full (overflow). With an 8 B int and an 8 B pointer, one node is 16 B.ptr = header + while ptr->link ≠ NULL stops on the last node and is safe on an empty list. Use it for insert at end, delete last, and concatenate.ptr = header->link + while ptr ≠ NULL visits every node. Use it for traverse, search and copy.ptr and ptr1.ptr->data = key.getNode() = NULL before inserting, and check for an empty list before deleting.NULL becomes header. So ptr ≠ header, ptr->link ≠ header, new->link ← header. Empty: header->link = header.new->link ← header plus the loop test.if ptr->link = header is wrong when the key is last. Test ptr->data ≠ key instead.ptr1->link ← header). Delete key: two lines.getNode a fresh node, copy the data and hang it on ptr1. Two independent lists, with no arrow between them. O(n) time and O(n) space.ptr = header1, walk to the last node, ptr->link = header2->link, then header2->link = NULL before RETURNNODE(header2).flag plus a location pointer. Loop while ptr ≠ NULL and flag = 0. The NULL test comes before any ptr->data, so empty lists and missing keys are safe.| singly linked list | time | why |
|---|---|---|
| insert at front · delete first | O(1) | a fixed handful of statements, no loop |
| insert at end · delete last | O(n) | walk to the last node (and its predecessor) |
| insert after key · delete key · search | O(n) | best O(1) when the key is first; quote the worst case |
| traverse · copy | O(n) | every node once. Copy also uses O(n) extra space. |
| concatenate (lists of m and k nodes) | O(m) | only list 1 is walked |
Why linked lists exist (S04, S05):
list is a resizable array of pointers, which is why indexing it is O(1). The professor's point is that Python manages the memory for you.)Nodes are [data | link]. An amber arrow is the link the current line just changed. Dashed nodes are unreachable. The labels above the nodes are the pointer variables.
← → step · space play/pause · the drawing scrolls sideways on a phone
index : 109 105 101 125 113 DATA : 20 30 25 35 … LINK : 105 101 125 113 NULL
20 → 30 → 25 → 35 → (113) → NULL
GETNODE for every element, never a copied pointer. ptr walks the original while ptr1 builds the copy in step; header1 itself never moves, because it is what gets returned.own header · fresh node per element · O(n) time and space
while (ptr ≠ NULL) AND (flag = 0) safe on an empty list and for a missing key?S05ptr = header->link = NULL, so the test fails immediately and ptr->data is never read.flag tells you which of the two exits happened, and location holds the node's address or NULL.the NULL check guards every dereference
while (ptr ≠ header) AND (ptr.data ≠ key). Does it work for the key first, in the middle, last, and absent?S05 homeworkworked out hereptr ← header.link and ptr1 ← header. The loop body is ptr1 ← ptr; ptr ← ptr.link.ptr1.link ← ptr.link unlinks it. ✓ptr1.link ← ptr.link copies header, so the circle stays closed. ✓ptr = header. Deleting now would unlink the header. ✗ Modification: add if ptr = header then "key not found" before deleting.works for first, middle and last · needs an "if ptr = header" check for a missing key
if (ptr.link ≠ key) for the insert-after-key fix. Why was it rejected?S05ptr.link is an address and key is a data value.ptr.data ≠ key.you can't compare an address with a value
S06 (5 Sep) — Dey
Adding a second link per node lets you walk backwards. Adding a header link to the last node turns "insert at end" from O(n) into O(1).
[LLINK | DATA | RLINK]: back to the previous node, forward to the next. The order you declare the fields in doesn't matter.PTR = PTR->RLINK forwards, PTR = PTR->LLINK backwards. O(n).PTR = HEADER->LLINK reaches the last node with no walk. O(n) becomes O(1).PTR ≠ HEADER instead of PTR ≠ NULLPTR = HEADER->RLINK = NULL, and PTR->LLINK = NEW then crashes. Give the empty case its own branch.DLL delete, search and insert at an arbitrary position were set as self-study. They use the SLL logic plus the left links.
[i | j | DATA | ROW LINK | COL LINK]: row link → next non-zero in the same row, col link → next non-zero in the same columni or j marks a header. A row header's DATA holds that row's count of non-zeros. Its ROW LINK → the row's first element, its COL LINK → the next row header.Where linked lists show up (S06):
[coefficient | exponent | link]. Adding or multiplying polynomials just inserts result terms as new nodes.Upper arrows are RLINK (forward) and lower arrows are LLINK (back). Compare the two "insert at end" presets: one walks every node, the other jumps straight to the end.
NEW->RLINK = 300 (forward to 20). NEW->LLINK = 100 (back to the header).PTR->LLINK (node 20's back link) = 200, the address of NEW itself, not "NEW->RLINK".HEADER->RLINK = 200.300 · 100 · 200 · 200
8×10⁸ B vs 2,400 B
[coef | exp | link], in decreasing exponent.[5|5] → [3|3] → [1|1] → [7|0] → NULL
4,000 B for the element nodes
S07 (14 Sep) · S08 (17 Sep) — Prakash
A stack is an array or a linked list with one rule added: insert and delete at one end only. That rule is enough to reverse strings and evaluate expressions.
top = −1)top ← top+1 then A[top] ← xx ← A[top] then top ← top−1top = −1 · top = SIZE−1. With general bounds L…U (S07): empty is top < L, full is top ≥ U.new←GETNODE(); new->data←item; new->link←top; top←new; stackhead->link←toptop = NULL? then empty · item←top->data; ptr←top->link; top←ptr; stackhead->link←ptrnewtop now holds that address.a + b · + a b · a b +. Same value; only the position of the operator changes. Unary operators (++a, a++) have no infix form.^ > * / > + −. Brackets first, innermost first.^ is right-to-left (a^b^c = a^(b^c)). * / + − are left-to-right.arg2 = pop(), arg1 = pop(), push(arg1 op arg2).Analogies (S07, S08):
1 2 23 could be misread. Leave space or bracket them, e.g. 1 2 (23). Inside the machine each number is a separate token, so there's no ambiguity.The indices 0…3 run up the side of the bucket. Watch top move before a push stores and after a pop reads. In postfix mode, the two popped values move out to arg1 op arg2, and the result drops back in.
Try a broken one, like 3 + (underflow) or 1 2 3 + (left-over operand). Tokens are separated by spaces.
(2*3)+4 and 2*(3+4) to postfix.S082*3 gives 2 3 *. Then (2 3 *) + 4 gives 2 3 * 4 +, which is 10.3+4 gives 3 4 +. Then 2 * (3 4 +) gives 2 3 4 + *, which is 14.2 3 * 4 + (=10) · 2 3 4 + * (=14)
A − (B − (C − D)) to postfix and prefix.S08C D −. Then B C D − −. Then A B C D − − −.− C D, then − B − C D, then − A − B − C D.postfix A B C D − − − · prefix − A − B − C D
a ^ b ^ c to prefix.S08 · associativity^ is right-to-left, so b ^ c comes first: ^ b c.a ^ (^ b c) gives ^ a ^ b c.^ a ^ b c
8 2 − 3 /. What goes wrong if you swap arg1 and arg2? (It's preloaded in the input box above.)practice−: arg2 = 2, arg1 = 8, giving 8 − 2 = 6./: arg2 = 3, arg1 = 6, giving 6 / 3 = 2.2 (swapped order gives −0.5)
(A + B) * C − D / E to postfix.practiceA B +.* and / before −: (A B +) C * and D E /.−.A B + C * D E / −
S09 (18 Sep) · S10 (19 Sep) — Prakash
A queue uses two ends, each with one job: insert at the rear, delete at the front. The naive array version wastes the cells it has already served. Treating the array as a ring fixes that with pointer arithmetic alone.
TOP · queue: FRONT and REAR, because the two jobs happen at different endsFRONT = REAR = 0. 0 is an impossible index, the same idea as the stack's −1.FRONT = REAR · REAR − FRONT + 1 (e.g. 5…10 holds 6). Linear only.REAR = N. True: FRONT = 1 AND REAR = N, which only makes sense with compaction.FRONT = 1. Dequeuing the last element (FRONT = REAR) resets both to 0.REAR = N but FRONT > 1, shift everything back to start at index 1, set REAR ← REAR − FRONT + 1 and FRONT ← 1, then insert. That costs O(N) whenever it happens.REAR = N becomes a true fullness test. Every dequeue costs O(N).new->link = NULL. If front = NULL, then front = rear = new and qhead->link = front. Otherwise rear->link = new; rear = new.item = front->data; ptr = front->link; qhead->link = ptr; front = ptr. If front = NULL, also set rear = NULL.| circular array queue | linked-list queue | |
|---|---|---|
| memory reserved | a fixed block of n slots up front | exactly one node per element |
| waste / capacity risk | may idle (100 slots, 10 used) or overflow (need 101) | neither |
| space per element | better: data only | worse: data + link |
| enqueue / dequeue | O(1) | O(1) |
| overflow · underflow | insert into a full queue · delete from an empty queue (same as a stack's push and pop) | |
Where queues appear (S09):
Both queues get identical operations. The data never moves: only F and R do. The ring is the circular queue's own cells 1…n bent into a circle, with the same indices. Step to the 6th operation in the first preset to see the difference.
+ enqueue / − dequeue add your own operation to the end of the sequence
the false "full" at step 3 is the drawback that motivates the circular queue
r = 1, f = 2
PALINDROME(S) create empty stack ST and empty queue Q for each ch in S: push(ST, ch); enqueue(Q, ch) while ST not empty: if pop(ST) ≠ dequeue(Q): return "not a palindrome" return "palindrome"
MOM: M = M, O = O, M = M, so it's a palindrome. MON: the first comparison is N vs M, which fails immediately, so there's no need to continue.MOM ✓ · MON ✗ at the first comparison
4 elements · the first enqueue fits at 3 · the second is refused (full)
FRONT 1, REAR 4
S11 (21 Sep) — Prakash · plus the S06 primer (Dey)
Count steps, not seconds. Then keep only how the count grows, because constants and small inputs don't matter.
| order | name | example from the course |
|---|---|---|
| O(1) | constant | min/max of a sorted array (a₁, aₙ) · insert at the front of a linked list · push/pop · circular enqueue |
| O(log n) | logarithmic | binary search |
| O(n) | linear | vector addition · max of an unsorted array · traversal · linear search |
| O(n log n) | "poly-logarithmic" in lecture; linearithmic in most textbooks | many sorting algorithms (after the midterm) |
| O(n²) | quadratic | bubble sort · scanning every cell of an n × n matrix |
The intuition (S06 primer, S11):
Slide c until the teal bound c·g(n) stays above the amber f(n) from some point on. That point is n₀. Dots are f at whole numbers of n: teal where the bound holds, red where it fails.
c = 5, n₀ = 1
sum = 0; i = 1; input n; while i ≤ n: sum = sum + i; i = i + 1.S11sum = 0, i = 1 and input, which is 4 steps.T(n) = 2n + 4 = O(n) · c = 10, n₀ = 1
(8, 1) · (7, 1)
No. (n = O(n²) is true, though.)
every operation in the course, worst case
| structure | operation | time | note |
|---|---|---|---|
| array | access A[I] · 2-D / triangular / band index | O(1) | one formula: a multiply plus additions |
| array | traverse · linear search | O(n) | search best case O(1) |
| array | bubble sort | O(n²) | n(n−1)/2 comparisons · O(1) extra space |
| array | insert into a sorted array | O(n) | shift everything after the slot |
| singly linked | insert at front · delete first | O(1) | |
| singly linked | insert at end · delete last · after/delete key · search · traverse | O(n) | walk from the header |
| singly linked | copy · concatenate | O(n) · O(m) | copy uses O(n) extra space; concatenate walks list 1 only |
| doubly linked | insert at front | O(1) | 4 link updates |
| doubly linked | insert at end: linear · circular | O(n) · O(1) | via HEADER->LLINK |
| sparse multi-linked | reach element (i, j) | O(n) | n + n steps, against O(1) for an array |
| stack (array or linked) | push · pop · isEmpty · isFull | O(1) | linked status = count nodes, O(n) |
| stack | evaluate postfix · reverse a string | O(n) | each token or character once |
| linear array queue | enqueue · dequeue | O(1) | but falsely "full" |
| linear array queue | with compaction · with shift-on-dequeue | O(N) | non-uniform: some operations are cheap, some expensive |
| circular / linked queue | enqueue · dequeue | O(1) | pointer arithmetic only, no shifting |