Data Structures & Algorithms

What this covers

• Tracing array, linked list, stack and queue operations step by step, including pointer reassignment when inserting or deleting a node
• Implementing and comparing linear search, binary search, bubble/insertion/selection sort, merge sort and quicksort
• Expressing best, average and worst case cost in Big-O notation and justifying why an algorithm is O(n log n) rather than O(n^2)
• Hash tables: hash functions, collisions, chaining versus open addressing, and why average lookup is treated as O(1)
• Binary search trees and binary heaps: insertion, deletion, in-order/pre-order/post-order traversal, and how tree height affects performance
• Choosing a structure for a scenario question (undo history, print queue, dictionary lookup, sorted leaderboard) and defending the choice in exam prose
• Recursion on structures: recursive traversal, base cases, and converting between recursive and iterative versions

Where learners get stuck

Treating Big-O as a measure of runtime in seconds rather than growth rate

Students first meet efficiency through timing their own code, so they conclude a 'fast' algorithm has small Big-O. They then can't explain why an O(n^2) sort can beat O(n log n) on ten items, or why constants and lower-order terms are dropped.

Losing the list when deleting or inserting in a linked list because pointers are reassigned in the wrong order

Diagrams on the board show the finished state, not the sequence. Students overwrite the pointer to the rest of the list before saving it, and because the code still compiles and runs, the bug looks like something else.

Believing binary search works on any list, or that a binary search tree stays balanced automatically

Both are usually taught with tidy, sorted, evenly spread example data. The precondition (sorted input) and the degenerate case (inserting already-sorted values, producing a linked list of height n) are rarely seen, so worst-case reasoning is missing.

Confusing a stack's LIFO behaviour with a queue's FIFO once both are implemented over an array

When both use an underlying array with index pointers, the implementation details look similar and students track indices instead of the abstract behaviour the structure is meant to guarantee.

What a session looks like

A session usually starts with you talking through a structure or algorithm you have already met, so gaps show up early. Evelyn then works a problem with you out loud — tracing a merge sort on eight values, walking a deletion through a BST, or counting operations to derive a complexity class — pausing for you to predict the next step rather than confirming afterwards. Longer sessions move to a scenario question ('which structure for a hospital triage system, and why') and then to writing or debugging the implementation. You can read code aloud or describe it; Evelyn will restate it back so you both know what is on the screen.

Helpful to know first

• Comfortable writing loops, conditionals, and functions in at least one language (Python, Java, C++ or similar)
• Familiarity with arrays or lists, including indexing and iteration
• Basic understanding of parameters, return values, and how a function call works
• Exponents and logarithms at the level of knowing that log2(1024) = 10; helpful but can be reviewed in session

Questions

Do I need to already know recursion before starting data structures?

No. Recursion is usually taught alongside tree traversal and merge sort in this topic. If you have never written a recursive function, say so at the start and the first session or two will build base cases and call stacks before moving to trees.

Which programming language does the tutoring use?

Whichever your course uses. Sessions can work in Python, Java, C++, or exam-board pseudocode. Say which one in your first session and examples will be given in that syntax.

My child can code but keeps losing marks on the theory questions about efficiency. Can this help?

Yes — that is a common split. Writing working code and justifying complexity in written prose are different skills. Sessions can focus specifically on counting operations, deriving Big-O, and structuring the written comparison answers that these questions ask for.

Is this the same as the programming taught in an Object-Oriented Programming course?

No. OOP focuses on classes, inheritance and encapsulation as ways of organising code. This topic is about how data is stored and accessed, and how the cost of operations changes with input size. They overlap when you implement a structure as a class, but the reasoning being assessed is different.