unit 1 - fundamentals of algorithms

Question 1

what is an algorithm?

Answer 1

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

Question 2

what is abstraction?

Answer 2

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

Question 3

what is decomposition

Answer 3

breaking down a large problem into smaller sub-tasks, which can then be further broken down until each small task is manage

Question 4

arithmetic operators

Answer 4

+ add
- subtract
/ divide
* multiply
^ exponent
MOD division with a remainder
DIV integer division

Question 5

what is a variable?

Answer 5

is a location in memory where you can temporarily store text or numbers

Question 6

what are two tools to plan and write algorithms?

Answer 6

• pseudocode
• flowcharts

Question 7

what are the three programming constructs?

Answer 7

• sequence
• selection
• iteration

Question 8

data types

Answer 8

integer - a whole number
real - a number with a decimal point
boolean - can only be TRUE or FALSE
character - a single alphabetic or numeric character
- string - one or more characters enclosed in quote marks

Question 9

boolean operators

Answer 9

> greater than
< less than
= greater than or equal to
<= less than or equal to
= equal (== in python)
/= not equal (!= in python)

Question 10

what is sequence?

Answer 10

the statements are executed in the order that they are written

Question 11

what is selection?

Answer 11

• an IF statement in a selection statement
• the next statement to be executed depends on whether the condition tested is TRUE or FALSE

Question 12

what is pseudocode?

Answer 12

• a structured english for describing algorithms
• allows the designer to focus on the logic on the algorithm without being distracted by the syntax

Question 13

how to assign a value to a variable in pseudocode?

Answer 13

total <- 0
cost <- adult * child
counter <- counter + 1

Question 14

how to write an input/output in pseudocode?

Answer 14

firstname <- USERINPUT
OUTPUT (“enter a value”)

Question 15

what does iteration mean?

Answer 15

• repetition of a certain block of code

Question 16

what are the three different types of iteration statements?

Answer 16

• FOR…ENDFOR
• WHILE…ENDWHILE
• REPEAT…UNTIL

Question 17

what is the FOR…ENDFOR loop used for?

Answer 17

when you want to execute the loop a specific number of times

Question 18

what is the WHILE…ENDWHILE loop used for?

Answer 18

when you want to execute the loop while a certain condition is true
the condition is checked at the start of the loop

Question 19

what is the REPEAT…UNTIL loop used for?

Answer 19

• when you want to execute the loop until a certain condition is true
• the condition is tested at the end of the loop
• usually has an IF statement to test the condition at the end

Question 20

what is a flowchart?

Answer 20

means of defining an algorithm using shapes and arrows. each shape has a specific meaning that corresponds to an action/decision

Question 21

flowchart shapes and what they signify

Answer 21

tablet > marks the start and end of the code
diamond > a decision (asks if a condition is true or not)
parallelogram > input/outputs
rectangle/box > process (each contains a single instruction)

Question 22

what is a trace table?

Answer 22

a table used to keep track of variables that change throughout the algorithm

Question 23

what is searching?

Answer 23

determining whether a specific item of data exists within a data structure

Question 24

what is a linear search?

Answer 24

a search algorithm that begins at one end of the data and checks each item methodically if and until the required item is found or the end of the structure is reached

Question 25

what are the two types of search algorithms?

Answer 25

• linear search
• binary search

Question 26

what is binary search?

Answer 26

a search algorithm that begins in the middle of the data structure and eliminates half the structure with each pass
- the data must be sorted in ascending order before the search can take place

Question 27

linear search vs binary search

Answer 27

linear search:
+ functions on unsorted data
- is more time consuming than a binary search
- only really works on smaller data structures

binary:
+ far more time efficient
- data has to be sorted first

Question 28

what is sorting?

Answer 28

putting the data into order (ascending or descending)

Question 29

what is bubble sort?

Answer 29

• each item in a list is compared to the one next to it, and if it is greater then they swap places
• the initial pass doesn’t do anything
• at the end of the first pass through the list, the largest item is at the end of the list
• this is repeated until the items have been sorted

Question 30

what is merge sort?

Answer 30

• 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 - the sorted list

Question 31

bubble sort vs merge sort

Answer 31

bubble sort:
+ straightforward to program
+ doesn’t use much extra memory space whilst the sort is in progress
- often slow and inefficient compared to merge sort
- cannot sort long data structures

merge sort:
+ much more efficient in terms of time
- more complex to program
- requires a lot of memory space whilst it runs (quite bad with large data structures)