PDS · Reading course
Build programs.
Understand their structures.
Every section from your supplied notes: C programming, recursion, linear structures, trees, heaps, graphs, chapter lock-ins, and checkpoints.
103 reading items · 9 phases · Worked examples & practice
0%
0 of 103 reading items completed
Complete an item when you’re ready. Your place is saved in this browser.Your path through PDS
Lessons, chapter reviews, and checkpoints—in reading order.
Begin hereStart here0 / 2 complete
01Phase 0Foundations0 / 5 complete
0.1.1Programs and instructions; source code → compiler → executable; the shape of a first C program (main, printf, return)Lesson0.1.2Memory as numbered boxes: bits, bytes, addresses; a variable as a named boxLesson0.2.1Powers of 2 and logarithms; floor and ceilingLesson0.2.2Sums of series (1+2+…+n, 1+2+4+…+2ⁿ); basic countingLessonCP0FoundationsCheckpoint
02Phase 1Programming in C0 / 18 complete
1.1.1Data types and their sizes; signed vs unsigned; constants; variables; declaration vs definitionLesson1.1.2Operators: arithmetic, relational, logical with short-circuiting, bitwise, assignment, ++ and --; precedence and associativity; undefined behaviorLesson1.1.3Type conversion: implicit promotion, casting, overflow, char as a small integer; what printf returnsLesson1.2.1if / else if / else; nested conditions; switch and fall-throughLesson1.2.2for, while, do-while; break and continue; tracing loop output and counting iterationsLesson1.3.1Declaring, defining, calling; parameters; return values; call by valueLesson1.3.2Scope vs lifetime; local, global, static, extern, register; shadowing in blocks; static local variablesLesson1.3.3How calls work: the call stack and stack framesLesson1.4.1& and *; pointer declaration; NULL; pointer to pointerLesson1.4.2Simulating call by reference with pointers (swap)Lesson1.4.3Pointer arithmetic and why it scales by type sizeLesson1.5.11-D arrays; a[i] == *(a+i) == i[a]; arrays decaying to pointers; passing arrays to functions; the sizeof trapLesson1.5.22-D arrays; row-major layout; pointer to array vs array of pointers; reading complex declarationsLesson1.5.3Strings: char arrays, '\0', read-only string literals, strlen vs sizeof, string functions and tracing string codeLesson1.6Structures, unions, typedef; self-referential structures; structure size and paddingLesson1.7Dynamic memory: malloc, calloc, realloc, free; stack vs heap; dangling pointers, memory leaks, double freeLesson1.8Preprocessor macros and their expansion traps; function pointersLessonCP1Programming in CCheckpoint
03Phase 2Recursion0 / 6 complete
2.1.1Base case and recursive case; tracing calls on the stackLesson2.1.2Recursion trees; counting calls; work done before vs after the recursive callLesson2.1.3Classic patterns: factorial, Fibonacci, GCD, power, Tower of Hanoi (2ⁿ−1 moves), digit/array recursionLesson2.1.4Computing what a recursive function returns via its recurrence; static and global variables inside recursionLesson2.2Counting work: a Big-O primerLessonCP2RecursionCheckpoint
04Phase 3Linear Data Structures0 / 13 complete
3.1Arrays as a data structure: the ADT idea; address calculation (row-major, column-major, non-zero lower bounds); cost of insert, delete and searchLesson3.2.1Stack ADT; push/pop/peek; array implementation; overflow and underflowLesson3.2.2Stack applications: parenthesis matching; infix → postfix/prefix conversion; postfix evaluationLesson3.2.3Valid stack permutations; Catalan numbersLesson3.3.1Queue ADT; linear array queue and its wasted-space problemLesson3.3.2Circular queue: full/empty conditions and index arithmeticLesson3.3.3Deque; priority queue as a concept; queue from two stacks and stack from two queues (operation costs)Lesson3.4.1Singly linked list: node, head, traversal, search, insertion (head/tail/middle), deletionLesson3.4.2Reversing a list (iterative and recursive); finding the middle; detecting a cycle (fast/slow pointers)Lesson3.4.3Doubly and circular linked lists; operation costs compared with arraysLesson3.4.4Stack and queue built on linked listsLesson3.4.5GATE drill: tracing pointer-manipulation code on linked listsLessonCP3Linear data structuresCheckpoint
05Phase 4Trees & Binary Search Trees0 / 14 complete
4.1Tree vocabulary: root, parent, child, sibling, leaf, internal node, degree, level, depth, height; the edges-vs-nodes conventionLesson4.2.1Strict/full, complete and perfect binary treesLesson4.2.2Binary tree properties: nodes per level and height; n₀ = n₂ + 1; minimum and maximum heightLesson4.2.3Representations: linked nodes vs array indexing (both 0-based and 1-based formulas)Lesson4.3.1Preorder, inorder, postorder (recursive code and hand tracing)Lesson4.3.2Level-order traversal using a queueLesson4.3.3Rebuilding a tree from two traversals; counting distinct binary trees (Catalan)Lesson4.4Recursive code on trees: count nodes, leaves, height, mirror, sums; expression treesLesson4.5.1The BST property; search, minimum, maximum; inorder gives sorted orderLesson4.5.2BST insertion; building a BST from an insertion sequence; best- vs worst-case heightLesson4.5.3BST deletion: leaf, one child, two children (inorder successor or predecessor)Lesson4.5.4BST GATE drills: BST from a preorder/postorder sequence; number of BSTs; valid search paths; insertion orders giving the same BSTLesson4.6Balanced BSTs — AVL idea, balance factor, rotations, minimum nodes for a given heightLessonCP4Trees & binary search treesCheckpoint
06Phase 5Binary Heaps0 / 5 complete
5.1The heap idea: a complete binary tree in an array; max-heap and min-heapLesson5.2Heap insertion (sift-up) and deleting the root (sift-down)Lesson5.3Build-heap in O(n) vs n insertions; heap sortLesson5.4Heap GATE drills: k-th largest, number of heaps, comparisons, d-ary heapsLessonCP5HeapsCheckpoint
07Phase 6Graphs0 / 4 complete
08Phase 7Integration & Final Test0 / 36 complete
L0.1What a program isChapter reviewL0.2Math toolkitChapter reviewL1.1Data and expressionsChapter reviewL1.2Control flowChapter reviewL1.3FunctionsChapter reviewL1.4PointersChapter reviewL1.5Arrays and strings in CChapter reviewL1.6Structures, unions, typedefChapter reviewL1.7Dynamic memoryChapter reviewL1.8Preprocessor and function pointersChapter reviewL2.1RecursionChapter reviewL2.2Counting work: a Big-O primerChapter reviewL3.1Arrays as a data structureChapter reviewL3.2StacksChapter reviewL3.3QueuesChapter reviewL3.4Linked listsChapter reviewL4.1Tree vocabularyChapter reviewL4.2Binary treesChapter reviewL4.3TraversalsChapter reviewL4.4Recursive code on treesChapter reviewL4.5Binary search treesChapter reviewL4.6Balanced BSTs (AVL)Chapter reviewL5.1The heap ideaChapter reviewL5.2Heap insert and deleteChapter reviewL5.3Build-heap and heap sortChapter reviewL5.4Heap drillsChapter reviewL6.1Graph vocabularyChapter reviewL6.2Graph representationsChapter reviewL6.3Graph traversalsChapter review7.1Master Rule SheetRevision7.2.1Mixed practice set 1Revision7.2.2Mixed practice set 2Revision7.2.3Mixed practice set 3Revision7.3GATE pattern drillRevision7.4Final end-to-end testFinal test7.4-keyFinal Test — Answer Key🛑Stop here until you have finished the 90-minute final test.🔑 Open the full answer keyQ1 Answer: (C)1 mark6 & 3 = 2, 6 | 3 = 7, 6 ^ 3 = 5; + binds tighter than <<: 1 << 4.Output2 7 5 16(A) is wrong: 1 << 4 is 16.(B) is wrong: Precedence: 3 + 1 is computed first.(D) is wrong: 110 & 011 = 010.Re-read: Lesson 1.1.2 — Operators: arithmetic, relational, logical with short-circuiting, bitwise, assignment, ++ and --; precedence and associativity; undefined behaviorQ2 Answer: 151 markn = 3, 6, 9, 12, 15; 15 % 5 = 0 ends the loop.Output15Re-read: Lesson 1.2.2 — for, while, do-while; break and continue; tracing loop output and counting iterationsQ3 Answer: (D)1 markmul(add(2, 3), 4).Output20(A) is wrong: That is 2 + 3 + 4.(B) is wrong: That is 2 · 3 + 4.(C) is wrong: That is 2 + 3 · 4.Re-read: Lesson 1.8 — Preprocessor macros and their expansion traps; function pointersQ4 Answer: (D)1 markPrinting after the call reverses the string.Outputetag(A) is wrong: Print comes after recursion.(B) is wrong: Every character prints.(C) is wrong: Every character prints.Re-read: Lesson 2.1.3 — Classic patterns: factorial, Fibonacci, GCD, power, Tower of Hanoi (2ⁿ−1 moves), digit/array recursionQ5 Answer: 631 mark2⁶ − 1.Output63Re-read: Lesson 2.1.3 — Classic patterns: factorial, Fibonacci, GCD, power, Tower of Hanoi (2ⁿ−1 moves), digit/array recursionQ6 Answer: (B)1 markThe parameter is a pointer.(A) is wrong: sizeof counts bytes.(C) is wrong: No such size.(D) is wrong: That is sizeof the array in the caller.Re-read: Lesson 1.5.1 — 1-D arrays; a[i] == *(a+i) == i[a]; arrays decaying to pointers; passing arrays to functions; the sizeof trapQ7 Answer: 13001 mark1000 + (7·10 + 5)·4.Re-read: Lesson 3.1 — Arrays as a data structure: the ADT idea; address calculation (row-major, column-major, non-zero lower bounds); cost of insert, delete and searchQ8 Answer: 141 markC(4).Re-read: Lesson 3.2.3 — Valid stack permutations; Catalan numbersQ9 Answer: (C)1 markEach element moves between the stacks once.(A) is wrong: Only a single refill can cost O(n).(B) is wrong: Far too large.(D) is wrong: No tree involved.Re-read: Lesson 3.3.3 — Deque; priority queue as a concept; queue from two stacks and stack from two queues (operation costs)Q10 Answer: (C)1 markThe previous node of the last must be found.(A) is wrong: O(1).(B) is wrong: O(1).(D) is wrong: O(1).Re-read: Lesson 3.4.1 — Singly linked list: node, head, traversal, search, insertion (head/tail/middle), deletionQ11 Answer: 631 mark2⁶ − 1.Re-read: Lesson 4.2.2 — Binary tree properties: nodes per level and height; n₀ = n₂ + 1; minimum and maximum heightQ12 Answer: (B)1 markLeft, node, right.(A) is wrong: Root last.(C) is wrong: Root first.(D) is wrong: By depth.Re-read: Lesson 4.5.1 — The BST property; search, minimum, maximum; inorder gives sorted orderQ13 Answer: 201 markN(5) = 12 + 7 + 1.Re-read: Lesson 4.6 — Balanced BSTs — AVL idea, balance factor, rotations, minimum nodes for a given heightQ14 Answer: (A)1 markSum of node heights.(B) is wrong: Every key is read.(C) is wrong: Too large.(D) is wrong: That is n insertions.Re-read: Lesson 5.3 — Build-heap in O(n) vs n insertions; heap sortQ15 Answer: 191 mark(30 + 8)/2.Re-read: Lesson 6.1 — Graph vocabularyQ16 Answer: (D)2 marks(*(p + 1))[1] is a[1][1]; *(*p + 4) is the 5th int from a[0][0].Output5 5(A) is wrong: Index 1 in row 1 is 5.(B) is wrong: p + 1 is row 1.(C) is wrong: *p + 4 is &a[0][4] = &a[1][1].Re-read: Lesson 1.5.2 — 2-D arrays; row-major layout; pointer to array vs array of pointers; reading complex declarationsQ17 Answer: (C)2 marksq is a[2]; (q − 1) is a[1] with y = 1; P holds two ints.Output2 1 8(A) is wrong: sizeof(P) is 8.(B) is wrong: q->x is 2.(D) is wrong: a[1].y = 1·1.Re-read: Lesson 1.7 — Dynamic memory: malloc, calloc, realloc, free; stack vs heap; dangling pointers, memory leaks, double freeQ18 Answer: (D)2 marksOnly 10…40 fit; pop 40 and 30, push 70 at index 2.Outputfull 70 2(A) is wrong: The fifth push prints full.(B) is wrong: 50 was never pushed.(C) is wrong: Two pops then one push: top is 2.Re-read: Lesson 3.2.1 — Stack ADT; push/pop/peek; array implementation; overflow and underflowQ19 Answer: 132 marksBottom-up: f(0) = f(1) = f(2) = 1; f(3) = f(2) + f(0) = 2; f(4) = 2 + 1 = 3; f(5) = 3 + 1 = 4; f(6) = 4 + 2 = 6; f(7) = 6 + 3 = 9; f(8) = f(7) + f(5) = 9 + 4 = 13.Re-read: Lesson 2.1.4 — Computing what a recursive function returns via its recurrence; static and global variables inside recursionQ20 Answer: (C)2 marksBoth loops run about log₂ n times.(A) is wrong: Neither loop is linear.(B) is wrong: The inner loop is logarithmic.(D) is wrong: Two nested logarithmic loops.Re-read: Lesson 2.2 — Counting work: a Big-O primerQ21 Answer: (A) (B) (C) (D)2 marksAt the "−" the stack holds a b c d.Re-read: Lesson 3.2.2 — Stack applications: parenthesis matching; infix → postfix/prefix conversion; postfix evaluationQ22 Answer: 22 marksrear moves 12 times: 12 % 10 = 2 (the queue holds 8 ≤ 9).Re-read: Lesson 3.3.2 — Circular queue: full/empty conditions and index arithmeticQ23 Answer: (D)2 marksBypass p from both sides, then free it.(A) is wrong: Neighbours still point to p.(B) is wrong: Changes only p’s own links.(C) is wrong: Uses p after free.Re-read: Lesson 3.4.3 — Doubly and circular linked lists; operation costs compared with arraysQ24 Answer: 22 marksPostorder 4 5 2 6 7 3 1.Re-read: Lesson 4.3.3 — Rebuilding a tree from two traversals; counting distinct binary trees (Catalan)Q25 Answer: 32 marksLongest path 15 → 10 → 8 → 6 (also 15 → 20 → 25 → 27).Re-read: Lesson 4.5.2 — BST insertion; building a BST from an insertion sequence; best- vs worst-case heightQ26 Answer: (A)2 marksLeft {1, 2}: C(2) = 2; right {4, 5, 6}: C(3) = 5; 2 × 5.(B) is wrong: That is only the right side.(C) is wrong: Not doubled again.(D) is wrong: C(4) is unrelated.Re-read: Lesson 4.5.4 — BST GATE drills: BST from a preorder/postorder sequence; number of BSTs; valid search paths; insertion orders giving the same BSTQ27 Answer: (A)2 marks5 moves to the root and sinks below 2.(B) is wrong: 2 is the smaller child.(C) is wrong: The last key goes to the root first.(D) is wrong: 4 does not move.Re-read: Lesson 5.2 — Heap insertion (sift-up) and deleting the root (sift-down)Q28 Answer: 82 marksC(4, 3)·2·1.Re-read: Lesson 5.4 — Heap GATE drills: k-th largest, number of heaps, comparisons, d-ary heapsQ29 Answer: (A) (C)2 marksLevels {A}, {B, C}, {D}, {E}, {F}.(B) is wrong: E (distance 3) cannot precede D.(D) is wrong: C (distance 1) must come before D (distance 2).Re-read: Lesson 6.3 — Graph traversals: BFS, DFS, connected componentsQ30 Answer: 362 marksK₉ plus one isolated vertex: (10 − 2)(10 − 1)/2.Re-read: Lesson 6.1 — Graph vocabularyAnswer key
A good way to read
01 · Think before revealingTry the Predict First and self-test questions. Open the Answer Vault when you’re ready.
02 · Keep track of understandingMark each reading item complete yourself. The reading-position bar simply shows where you are on the page.
03 · Revisit what mattersUse chapter reviews, checkpoints, and revision pages to connect ideas. The imported practice is self-checked against the supplied answers.
Your progress, your copy.
Saved in this browser. Export a backup to move your PDS progress to another device.
Adapted from your supplied PDS notes. Source answers and claims in the notes have not been independently fact-checked. Reading progress is separate from the Atlas topic checklist.