Overview
This lecture reviews key concepts in abstract data structures, focusing on static and dynamic structures, 2D arrays, basic pseudocode operations, recursion, and sample IB exam problems.
Static vs Dynamic Data Structures
- Static data structures (e.g., arrays) have a fixed size set at creation and cannot be resized.
- Static structures can be memory inefficient since all elements are pre-allocated, even unused ones.
- Advantages of static structures include direct access to any element and ability to traverse both forwards and backwards.
- Dynamic data structures (e.g., collections, linked lists) can grow or shrink in size and do not require contiguous memory.
- Dynamic structures use nodes and pointers to link elements, allowing for memory efficiency.
- Only forward traversal is possible in dynamic structures, and direct access to arbitrary elements is not supported.
2D Arrays
- 2D arrays are arrays of arrays, typically visualized as grids with rows and columns.
- Accessing an element requires specifying a row and column, e.g., nums[1][2] accesses row 1, column 2.
- 2D arrays are commonly used to represent data with two dimensions (e.g., student grades).
Operations with 2D Arrays
- To output an entire row: output grades[row]
- To access a specific element: output grades[row][col]
- To iterate through all elements: use nested loops—outer for rows, inner for columns.
- To output only a column: iterate through rows, output grades[row][column_index]
- To count or sum elements: use nested loops with a counter or sum variable.
- To find max/min value and its position: track max/min and their indices while iterating.
Sample IB Exam Problems
- Swap function: To swap two variables, use temp = a; a = b; b = temp.
- To swap two rows in a 2D array, iterate through each column and swap corresponding elements using a temporary variable.
Recursion Fundamentals
- Recursion is when a function calls itself to solve smaller instances of a problem.
- Every recursive function has a base case (when to stop) and a recursive step (calls itself).
- Example: Factorial function where n! = n × (n-1)! until n = 1.
- IB questions may require tracing recursive functions or determining output, not necessarily writing them.
Tracing a Recursive Algorithm Example
- For a function calculating fun(x, n): returns 1 if n ≤ 0, else x * fun(x, n-1).
- The number of multiplications performed equals n.
- The function computes xⁿ by recursion.*
Pros and Cons of Recursion
- Pros: Cleaner code, breaks complex tasks into subproblems, easier sequence generation.
- Cons: Harder to understand/debug, typically less memory efficient than iteration.
Key Terms & Definitions
- Static Data Structure — Fixed-size data structure; size set at creation, e.g., array.
- Dynamic Data Structure — Flexible-size structure that can grow/shrink, e.g., linked list.
- 2D Array — An array containing arrays, used for grid-like data.
- Node — A single element in a dynamic structure, with stored data and pointer(s).
- Recursion — Function technique where the function calls itself.
- Base Case — The condition under which recursion ends.
- Recursive Step — The part where the function calls itself.
Action Items / Next Steps
- Practice reading and solving IB-style abstract data structure problems.
- Complete basic coding tasks using 2D arrays (access, iterate, find max/min).
- Review recursion by tracing sample recursive functions.
- Prepare for the next lecture on stacks, queues, binary trees, and linked lists.