HL extension (45 hours)

Topic 5— Abstract data structures (23 hours)

5.1 Abstract data structures (23 hours)

This will be examined at the level of diagrams and pseudocode.

Students should be able to describe the most common data structures (arrays, stacks, queues, linked lists, binary trees) and the most common data processing operations on each of the basic data structures (addition, deletion and retrieval of data, traversal, searching for a given data, sorting of data into some order).

This should be taught and connected to flow charts, pseudocode and programming in the SL/HL core.

The basic ideas and their application should be illustrated with non-computer examples. Each basic idea should then be practiced in specific algorithmic contexts using concepts drawn from flow charts, pseudocode and programming.

--- Thinking recursively ---


Identify a situation that requires the use of recursive thinking.


Teaching Note:

Suggested practical activity: snowflakes and fractals, towers of Hanoi.


Sample Question:


JSR Notes:

For this assessment statement, you are not to think at all about how recursion works, rather what types of situations ***require*** recursion, and, this, in general is:

- any situation where you can only see how to solve the problem by solving a problem similar to it, but with a slightly different set of values, and iterative solutions will not work.

So, the Little Old Lady problem is solved by asking "why she swallowed" something else etc. - but each of these "why she swallowed" instances depends on the previous one to make sense.
And the best recursive situation we have for programming is the traversal of binary trees (post, pre, or in-order). Think about it: how can you use a for loop to loop through, or a while loop? It's a branching structure, so you can't simply go straight through, but what you can do is check left and right, and then check left and right from each of those and so on.

It would be a good idea to look at the teaching note examples of snowflakes and fractals, towers of Hanoi.

(Do note how a binary search does not require recursive thinking, since it can be addressed in an iterative way.

Examples of (looping) situations which do not ***require*** recursive thinking:

- The recursive binary search is solved by calling other binary search method instances (of smaller and smaller sub-sets of the full array).
- The simplest recursive loop method calls other instance of itself, which bring the loop control variable closer to the limit.
and so on.
- BUT NEITHER REQUIRE recursive solutions.)

Of the following notes, the ones which is best for this are "recursion analogies", and "recursive problem-solving little-old-lady style"

  640          Recursion                      a very Brief Introduction
  642                                         a Flash game example of recursion
  645                                         recursion analogies
recursive stacking in memory (jpg1) (jpg2) 647 recursive problem-solving little-old-lady style 648 recursion example diagrams from the Morelli textbook