T1: Algorithms

What is an algorithm?

A set of instructions to complete a task

What is decomposition?

Breaking down a large problem into smaller sub-problems (sub-problems can be broken down further into manageable tasks)

What are subtasks?

They are modules that may be reused in other programs

What is abstraction?

The process of removing unnecessary detail and focusing only on the essential features of a problem.

What is a variable?

A location in memory where you can temporarily store texts or numbers.

Flowchart - elongated oval

start/end

Flowchart - rectangle

Calculation/assignment

Flowchart - parallelogram

Input/output

Flowchart - diamond

Decision (with arrows pointing to options - mostly yes/no)

What is sequence (program structure)?

The program follows the order it's been coded in/statements executed in the order they're written in

What is selection (program structure)?

If statements - making decisions, next statement to be executed depends on whether the condition being tested is true or false

What is iteration (program structure)?

Repetition (loops)

What is MOD + symbol

Modulo - the remainder of what you're dividing %

What is DIV + symbol

Integer division //

Describe a for loop in pseudocode

FOR counter <-- 1 TO 7 (newLine) maxT <-- USERINPUT (newLine) ENDFOR

Describe a while loop in pseudocode

WHILE emailA does not contain "@"

OUTPUT "Invalid address"

emailA

Describe a repeat until pseudocode

REPEAT

emailA

Describe an if statement pseudocode

IF emailA does not contain "@" THEN

OUTPUT "Invalid address"

ENDIF

How to calculate max number of items to be checked in binary search

In a list of 2^n items - max no. of items need to be checked = n + 1

Steps for binary search

Look at the middle value (if number of values even, then look at the left one - the lower one)

If value is lower than the one you want to find, discard the first half of the list

If value is higher than the one you want to find, discard the top half of the list

Continue until you find what you're looking for

Compare binary search and linear search

List has to be sorted for binary search, b search more efficient

how pick a random number python

import random

random.randint(1,100)

How does bubble sort work/steps

Compare the first two items.

If they are in the wrong order, swap them.

Move to the next pair and repeat (compare and swap if needed).

Keep going until you reach the end of the list - at this point, the largest value "bubbles up" to the end - this is called a pass

Go back to the start of the list and repeat the process

Continue until a full pass is made with no swaps needed → the list is sorted.

Describe merge sort (not the steps)

Happens with 2 or more different lists. Combines 2 lists and puts them in order.

Steps for merge sort

Divide the unsorted list into n sublists, each containing one element

Repeatedly merge two sublists at a time to produce new sorted sublists until there is only one sublist remaining. = sorted lists

How to merge lists

Compare 1st values

Put the lower value in the list

Compare lowest values of the lists needing to be sorted

Put lower value in the list

What is a module

a section (sub task)