ZIMFundi
Sign inJoin free

Topic 5 of 6 · Form 5

Algorithm design and data structures

Abstraction, decomposition, pattern recognition; structured English, flowcharts, pseudocode; stepwise refinement.

Notes for this topic 1 file, in order

Create a free account to download PDFs.

  1. PDFAlgorithm design and data structures – Computer Science notes (Cambridge A Level)45.2 KB

Computational thinking

Abstraction, decomposition, pattern recognition; structured English, flowcharts, pseudocode; stepwise refinement.

Data types and structures

Records, 1D and 2D arrays, files; abstract data types: stacks (LIFO), queues (FIFO, circular), linked lists (nodes and pointers), binary trees, hash tables, dictionaries.

Algorithms

Linear and binary search; bubble and insertion sort; algorithms on ADTs (insert, delete, find, traverse); recursion (base case, general case, call stack); Big O notation for time and space complexity.

Worked example: Write a recursive function for the sum of 1 to n.

FUNCTION Sum(n : INTEGER) RETURNS INTEGER

   IF n = 1 THEN

      RETURN 1

   ELSE

      RETURN n + Sum(n − 1)

   ENDIF

ENDFUNCTION

Further algorithms

Graph representation; Dijkstra's shortest path and A* search (introduction); binary search tree traversal (pre-, in-, post-order).

Exam tip: Trace recursive algorithms with a table showing each call and return value.

Check yourself

  1. State the time complexity of binary search.
  2. Which tree traversal outputs a binary search tree in ascending order?
  3. What is a base case in recursion?
Show answers
  1. O(log n)
  2. In-order traversal.
  3. The condition that stops recursion and returns a value without further calls.
Next topicProgramming, software development and advanced theory

Questions about this topic (0)

No questions about this topic yet.