Computer science: End of half term 1 test - Comp 2

2.1.1 Computational thinking, 2.1.2 Designing, creating and refining algorithms, 2.1.3 Searching and sorting algorithms

Algorithm

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

Examples of an algorithm

making a cake, building a lego model, getting ready for school

Computer program

a detailed plan/procedure for a computer to carry out

not the same thing as an algorithm - computer programs are written specifically for computers to carry out, while algorithms can be for anything

Abstraction

removing unnecessary detail from a problem so that you can focus on the essentials

Decomposition

breaking down a problem into sections that are easier to manage

allows you to look at a problem in ways that are easier to deal with

How to decompose a problem (4)

• you have to look for key tasks & functions

• for each task/function ask ‘can you solve it in one go’

• if not, break it down into sub-tasks

• keep doing this until every task is broken down as much as possible

How to make a hierarchy/structure diagram

• at the top write the main task to be completed

• branch it off into as many subtasks as you can think of

• keep branching those tasks into more layers of smaller sub-tasks until the task is fully broken down

Computational thinking

the use of computers to solve problems

Algorithmic thinking

identifying the steps involved in solving a problem

Variable

a space in memory, given a name and assigned a value that can be changed while a program is running

Initialisation

when a variable is declared and assigned a value

Input

data that is entered by the user

Output

the outcome that is displayed to the user

Selection

changing the flow of the program based on a condition that is met- used to make decisions in a program. made using a if statement

Relational operators

used for comparison of data: > < ≥ ≤ ≠ =

Flowcharts

a graphical way of showing the sequence of instructions to be carried out by a computer program

a form of decomposition because you’re breaking the problem into smaller parts

Curved rectangle meaning in a flowchart

• start/end of action

• always have to use at start/end of program - all branches have to go to/from the start/end rectangles

Rectangle meaning in a flowchart

process

Diamond meaning in a flowchart (4)

• decision

• aka an if statement

• pose it as a question e.g. is age > 18

• two lines coming out of it must be yes/no

Parallelogram meaning in a flowchart

input/output

Double rectangle meaning in flowchart

• sub routine

• another flowchart inside flowchart

Arrow meaning in flowchart

dataflow - always put between boxes to symbolise flow of data

Pseudocode

a kind of structured english that uses short statements for describing algorithms

2 benefits of pseudocode

• allows designer to focus on the logic of an algorithm, not the syntax/language

• allows programmers who use different languages to communicate

‘MOD’ (modulo) in pseudocode

gives the remainder of the division of the two numbers (% in python)

‘DIV’ (quotient) in pseudocode

division but just the whole number result without the remainder (// in python)

Variable assignment in pseudocode

variable name ← data to go into the variable

e.g. age ← 16

Asking user to input data for a variable in pseudocode

variable name ← input(text to display to user)

e.g. age ← input(how old are you?)

Constant variable assignment in pseudocode (variable you can’t change)

CONSTANT variable name ← data to go into variable

e.g. CONSTANT pi ← 3.14

If statement in pseudocode

IF conditions of statement THEN
what you want to be done
ELSE
what you want to be done
ENDIF

Print in pseudocode

OUTPUT(what you want to print)

Variable assignment in reference language

name = ‘sophia’

Constant variable in reference language

const pi = 3.14

Input into variable in reference language

name = input(‘enter name’)

output/print in reference language

print (‘hello world’)

comment in reference language

// this program will calculate age

while loop in reference language

while age < 18
print(‘you can’t drive’)
endwhile

If statement in reference language

if answer ‘yes’ then
print(‘correct’)
elseif answer == ‘no’ then
print(‘wrong’)
else
print(‘error’)
endif

logical and/or/not in reference language

AND
OR
NOT

Syntax error

when the language isn’t right so the program can’t run
e.g. not using capital letter, space, colon

Logic error

incorrect code that lets the program run but gives an incorrect output/result that isn’t expected

Dry run

walking through an algorithm with sample data running through each step manually in your head

Dry run steps (4)

1. read what the algorithm needs to do

2. draft the steps that should be taking place in note form

3. trace (read through) each step of computer program

4. compare what notes show it is meant to do to what program does (compare step 2 & 3)

Trace tables

tables used to test algorithms and programs for logic errors that appear when it executes & accuracy

Trace table example

num = 3
n = 0
while n < 4:
	num = num + n
	n = n + 1
print(num)

num	n	n < 4?	output
3	0	true
3	1	true
4	2	true
6	3	true
9	4	false	9

Nesting

when a statement/routine is inside another one

Search algorithm

a precise step-by-step instruction that a computer can follow to efficiently locate specific data in big datasets

Binary search (3)

• search involving where you keep halving a dataset using the middle value until you find the required value / realise it’s not there

• data must be in order

• can be done with numbers or words (words in alphabetical order)

Binary search steps (6)

1. find the middle value of set

2. compare middle value to the one you’re looking for

3. if it’s the one you’re looking for, stop

4. if it’s bigger than the one you’re looking for, get rid of every value bigger than the mid value, creating a new list with only the smaller values

5. if it’s smaller than the one you’re looking for, get rid of every value smaller than the mid value, creating a new list with only bigger values

6. repeat with new list until you’ve found the value or you realise it’s not there

Linear search

starts with the first value and checks every value one at a time to see whether it’s the one you’re looking for, can be performed on unordered data

Linear search steps (4)

1. check the first value

2. if it’s the one you’re looking for, stop

3. if it’s not the one you’re looking for, go to the next value

4. repeat until you have checked all values & not found the value you’re looking for

Sorting algorithms

• help organise data in a way that makes it easier & faster to work with

• makes data easier to search, read, understand

• allows large datasets to be handled efficiently

Sorting

arranging data in a specific order, usually ascending or descending

Emamples of sorting

• playlists can be sorted alphabetically, by artist, by genre

• online libraries sort books by title, author, publication

• online shopping sites sort products by price, rating, popularity

Bubble sort

looks at 2 items in a pair at a time & swaps pairs until the list is sorted
the largest item will always be sorted by pass 1

• simple to understand

• inefficient for large datasets

Insertion sort

sorts by inserting each element into its correct position in a growing sorted list
compares a element with elements in the sorted list and places it in the right place

• efficient for small datasets

• can be slow for large lists

Merge sort

divide-and-conquer algorithm that splits the list up, sorts it, and merges it back together

• efficient for large datasets

• but requires additional memory.