Notes
Algorithms
- An algorithm is a finite, ordered set of clear steps that solves a problem. The building blocks are sequence, selection (decisions) and iteration (loops).
- Order of steps matters.
Breaking problems down
- Decomposition splits a problem into smaller parts. Abstraction hides unneeded detail. Pattern recognition finds repeated steps that can be reused.
Describing algorithms
- Pseudocode uses plain-language words like INPUT, IF, ELSE, REPEAT and PRINT, without exact syntax.
- Flowcharts use ovals (start/end), rectangles (process), diamonds (decision) and parallelograms (input/output), connected by arrows.
Efficiency
- Linear search checks items one at a time. Binary search needs a sorted list and halves the search area each step, so it is far faster on large lists.
- Efficiency compares how time or memory grows as input grows.
Topics in this unit
Each topic has its own short notes and practice.
Practice
Algorithms are precise, finite and language independent.
Breaking a large problem into smaller tasks is decomposition.
Rectangles are for process steps; diamonds are for decisions.
5 + 2 + 2 + 2 = 11.
64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1 is 6 halvings, so at most 7 checks (one more for the final item).
Without sorting, binary search will not work, so each item must be checked.
Free response
Write your answer first, then open the scoring guide.
Free-response question
A cafeteria wants a program that reads a student's lunch balance and the price of a meal and tells whether the student can buy it.
(a) Use decomposition to list at least three smaller tasks for this program.
Show the answer and scoring guide
Get the balance, get the meal price, compare them, and display a message.
Check off the points you earned:
(b) Write pseudocode that prints "OK" if the balance is at least the price, otherwise prints "Not enough".
Show the answer and scoring guide
INPUT balance
INPUT price
IF balance >= price THEN
PRINT "OK"
ELSE
PRINT "Not enough"
Check off the points you earned:
(c) A list of 1,000 student ID numbers is sorted. Which search would be faster, linear or binary, and about how many checks would the faster one need at most?
Show the answer and scoring guide
Binary search is faster. It needs at most about 10 checks, because 2 to the 10th power is 1,024.
Check off the points you earned: