19 - computational thinking

Question 1

binary search

Answer 1

method of searching an ordered list by testing the middle value of the list and rejecting the half that doesn’t contain the value

Question 2

conditions for binary search

Answer 2

data has to be sorted

Question 3

how performance of binary search varies with no. data items

Answer 3

as you double your data size, you’ll have to do twice as many checks to find an item

Question 4

insertion sort

Answer 4

method of sorting data in an array into alphabetical or numerical order by
placing each item in turn in the correct position in the sorted list
+ good for incremental sorting - elements are added one at a time over a long period while keeping the list sorted

Question 5

binary tree

Answer 5

a hierarchical data structure in which each parent node can have a maximum of
two child nodes.

Question 6

graph

Answer 6

a non-linear data structure consisting of nodes and edges.
used to implement directed and undirected graphs
consists of a set of edges that join a pair of node - if the edges have a direction is a directed graph
edge can have a weight eg the distance between bus stops

Question 7

path and cycle in a graph

Answer 7

is the list of nodes connected by edges between two given nodes
a cycle is a list of nodes that return to the same node

Question 8

graph uses in real life networks

Answer 8

• bus routes, where the nodes are bus stops and the edges connect two stops next to each other
• websites, where each web page is a node and the edges show the links between each web page
• social media networks, where each node contains information about a person and the edges connect people who are friends

Question 9

dictionary

Answer 9

an abstract data type that consists of pairs, a key and a value, in which the key is used to find the value
- each key appears once - values can appear more than once
- keys are unordered
- a value is retrieved by specifying its key
-

Question 10

big O notation

Answer 10

a mathematical notation used to describe the performance or complexity of
an algorithm - in relation to the time take or memory used
- describes worst case scenario eg the max no. comparisons to find a value in a list using a search algorithm

Question 11

linear search code

Answer 11

found <- FALSE
i <- 0
upperbound <- LEN(array)
WHILE not found AND index<upperbound
IF item = array[i]
found <- TRUE
i = i + 1
IF found
OUTPUT ‘found’
ELSE
OUTPUT ‘ not found’

Question 12

binary search code

Answer 12

found <- FALSE
UB <- LEN(array)
LB <- 0
WHILE not found AND LB != UB
i = (UB + LB)/2
IF item = array[i]
found<- TRUE
IF item> array[i]
LB <- i+1
IF item < array[i]
UB <- i-1

IF found
OUTPUT ‘found’
ELSE
OUTPUT ‘ not found’

Question 13

bubble sort

Answer 13

sorting data in an array into alphabetical or numerical order by comparing adjacent items and swapping them if they are in the wrong order

Question 14

bubble sort code

Answer 14

UB <- LEN(array)
LB <- 0
swap <- TRUE
WHILE swap AND UB != 0
FOR i = LB TO UB-1
swap <- FALSE
IF array[i]>array[i+1]
temp <- array[i]
array[i] <- array[i+1]
array[i+1] <- temp
swap <- TRUE
UB <- UB -1

Question 15

insertion sort code

Answer 15

UB <- LEN(list)
LB <- 0
FOR i <- LB +1 TO UB
item <- list[i]
place<- i-1
IF list[place] > item
WHILE place >= LB AND list[place] >item
temp <- list[place+1]
list[place+1] <- list[place]
list[place] <- temp
place <- place -1
list[place+1] <- item

Question 16

what affects the performance of a sorting routine

Answer 16

the initial order of the data and the number of data items

Question 17

ADT

Answer 17

collection of data and a set of operations on that data
- find an item thats stored
- adding a new item
- deleting an item

Question 18

stack data structure code

Answer 18

stack = [0]*10
basePointer = 0
topPointer = -1
maxLen = 10

Question 19

stack pop code

Answer 19

if topPointer == basePointer -1:
print(‘stack empty’)
else:
item = stack[topPointer]
topPointer = topPointer -1

Question 20

stack push code

Answer 20

if topPointer < maxLen -1:
topPointer = topPointer +1
stack[topPointer] = item
else:
print(‘stack full’)

Question 21

queue data structure code

Answer 21

queue = [0]*10
frontPointer = 0
rearPointer = -1
length = 0
maxLen = 10

Question 22

enqueue code

Answer 22

if length < maxLen:
if rearPointer < length -1
rearPointer = rearPointer +1
else
rearPointer = 0
length = length + 1
queue[rearPointer] = item
else:
print(‘full’)

Question 23

dequeue code

Answer 23

if length == 0:
print(‘empty’)
else:
item = queue[frontPointer]
if frontPointer == length -1
frontPointer = 0
else:
frontPointer = frontPointer -1

Question 24

linked list code

Answer 24

list <- []11
listpointers <- []11
pointerStartPointer <- 0
startPointer <- -1
FOR i (0,11)
listpointer[i]<- i+1
listpointers[11] <- -1

Question 25

search linked list code

Answer 25

found <- FALSE
itemPointer <- StartPointer
WHILE (itemPointer<> nullPointer) AND NOT found
IF list[itemPointer] = itee
found<- TRUE
ELSE
itemPointer<- listpointers[itemPointer]
prin(itemPointer)

Question 26

inserting items into linked list code

Answer 26

IF pointerStartPointer = -1
OUPUT ‘list full’
ELSE
tempPointer <- startPointer
startPointer<- pointerStartPointer
pointerStartPointer <- pointerlist[pointerStartPointer]
list[startPointer] <- item
listPointer[startPointer] <- tempPointer

Question 27

removing items linked list code

Answer 27

IF startPointer = nullPointer
OUTPUT ‘list empty’
ELSE
index <- startPointer
WHILE list[i] <> item AND item <> nullPointer
oldIndex <- i
i <- listpointers[i]
IF i = nullPointer
OUTPUT ‘not found
ELSE
tempPointer <- listpointers[i]
listpointers[[i]<- startPointer
startPointer <- i
listpointers[oldindex] <- tempPointer

Question 28

binary trees - how they store data

Answer 28

hierarchical data structure
- each parent node can have a max of 2 child nodes
uses - syntax analysis, compression algorithms, 3D video games
root pointer points to first node - left and right pointers show what node is below on the left or right

Question 29

finding item in binary tree code

Answer 29

rootPointer <- 0
itemPointer <- rootPointer
WHILE tree[itemPointer].item <> itemSearch AND itemPointer <> nullPointer
IF tree[itemPointer].item > itemSearch
itemPointer <- tree[itemPointer].leftPointer
ELSE
itemPointer <- tree[itemPointer].rightPointer

Question 30

inserting items in binary tree

Answer 30

needs free nodes
code in textbook

Question 31

how to implement ADTS using another ADT

Answer 31

eg linked list - integers for pointers and string for item

Question 32

dictionary implements

Answer 32

using a linked list
- key is a linked list
- value is an array of strings

Question 33

bug O order of time complexity

Answer 33

O(1)
O(N)
O(N²)
O(2^N)
O(LogN)

Question 34

O(1) - time

Answer 34

describes an algorithm that always takes the same time to perform the task
eg deciding if a no is even or odd

Question 35

O(N) - time

Answer 35

describes an algorithm where the time to perform the task will grow linearly in direct proportion to N (the number of
items of data the algorithm is using)
eg linear search

Question 36

O(N²) - time

Answer 36

describes an algorithm where the time to perform the task will grow linearly in direct proportion to the square of N, the number of items of data the algorithm is using
eg bubble sort, insertion sort

Question 37

O(2^N) - time

Answer 37

describes an algorithm where the time to perform the task doubles every time the algorithm uses an extra item of data
eg calc of fibonacci numbers using recursion

Question 38

O(LogN) - time

Answer 38

describes an algorithm where the time to perform the task goes up linearly as the number of items goes up exponentially
eg binary search

Question 39

big O order of space complexity

Answer 39

O(1)
O(N)

Question 40

O(1) - space

Answer 40

describes an algorithm that always uses the same space to perform the task
eg algorithm that just uses variables

Question 41

O(N) - space

Answer 41

describes an algorithm where the space to perform the task will grow linearly in direct proportion to N, (the number of items of data the algorithm is using)
eg any algorithm that uses arrays eg a loop to calc the total of value in an array of N elements

Question 42

recursion

Answer 42

a process using a function or procedure that is defined in terms of itself and calls
itself
- defined using a base case - terminating solution thats not recursive
- and a general case - solution that is recurisvely defined

Question 43

base case

Answer 43

a terminating solution to a process that is not recursive

Question 44

general case

Answer 44

a solution to a process that is recursively defined

Question 45

winding

Answer 45

the statements after the recursive call arent executed until the base case is reached

Question 46

unwinding

Answer 46

after the base cased is reached and can be used in the recursive process the function is unwinding

Question 47

benefits of recursion + negative

Answer 47

+ contain fewer statements than iterative
+ can solve complex problems in a simpler way
- if recursive calls are repetitive, there is very heavy use of the stack which can lead to stack overflow eg 100 factorial needs 100 function calls on the stack

Question 48

how compiler implements recursion

Answer 48

a compiler must produce object code that pushes return addresses and values of local variables onto the stack with each recursive call, winding
the object code then pops the return addresses and values of local variables off the stack, unwinding