Computer Science - 1 Fundamentals of Algorithms

Algorithm

a set of instructions for solving a problem or completing a task

Decomposition

breaking a problem down into smaller, more manageable pieces

Abstraction

removes unnecessary details from a problem so that you can focus on the essentials

Python exponent

**

Python modulo

%

Python integer division

//

modulo

returns the remainder from a division

integer division

returns the result of a division truncated to the nearest integer

Variable

a location in memory in which you can temporarily store text or numbers

The name of a variable is called:

'identifier' or 'variable identifier'

Assigning a value in Python:

=

Pseudocode

a detailed yet readable description of what a computer program or algorithm should do

Flowchart: round-edged rectangle

start and end

Flowchart: rectangle

calculation or assignment

Flowchart: parallelogram

input or output

Flowchart: rhombus

decision

Three basic programming structures:

- sequence
- selection
- iteration

INTEGER

whole number

REAL or FLOAT

numbers that have a decimal part

BOOLEAN

a single value of either TRUE or FALSE

CHARACTER

a single alphabetic or numeric character

STRING

a sequence of characters

sequence

statements are executed in the order they are written in

selection

the next statement to be executed depends on whether the condition being tested is true or false (e.g. IF)

iteration

repetition of code

iterative statements [3]:

- FOR...ENDFOR
- WHILE...ENDWHILE
- REPEAT...UNTIL

Pseudocode assignment

←

Pseudocode output

OUTPUT("[text]")

Pseudocode input

[var] ← USERINPUT

Pseudocode for loop

FOR [var] ← [no.] TO [no.]
...
ENDFOR

Pseudocode while loop

WHILE [condition]
...
ENDWHILE

Pseudocode if statement

IF [condition] THEN
...
ELSE IF [condition] THEN
...
ELSE
...
ENDIF

Boolean operator

comparative symbols like < and >

Boolean expression

a comparative statement such as '15 > [var]'

Pseudocode repeat until statement

REPEAT
...
UNTIL [condition]

What is 'searching' in computing?

using a program to look through a list to find a value

What search would you use for a sorted list?

binary search

What search would you use for an unsorted list?

linear search

Binary search [3]

- look at middle value (if even set, use before midpoint)
- discard half without item
- repeat with kept half until item found or not found (not in set)

Linear search

an algorithm that iterates through each item in a list until it finds the target value.

In a sorted list of 2ⁿ items the maximum number of items you need to search is equal to:

n + 1

If the length of the sequence does not fit exactly into 2ⁿ:

use the lower exponent (e.g. 15 is 2³ rather than 2⁴)