19 - computational thinking Flashcards
binary search
method of searching an ordered list by testing the middle value of the list and rejecting the half that doesn’t contain the value
conditions for binary search
data has to be sorted
how performance of binary search varies with no. data items
as you double your data size, you’ll have to do twice as many checks to find an item
insertion sort
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
binary tree
a hierarchical data structure in which each parent node can have a maximum of
two child nodes.
graph
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
path and cycle in a graph
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
graph uses in real life networks
- 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
dictionary
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
-
big O notation
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
linear search code
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’
binary search code
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’
bubble sort
sorting data in an array into alphabetical or numerical order by comparing adjacent items and swapping them if they are in the wrong order
bubble sort code
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
insertion sort code
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
what affects the performance of a sorting routine
the initial order of the data and the number of data items
ADT
collection of data and a set of operations on that data
- find an item thats stored
- adding a new item
- deleting an item
stack data structure code
stack = [0]*10
basePointer = 0
topPointer = -1
maxLen = 10
stack pop code
if topPointer == basePointer -1:
print(‘stack empty’)
else:
item = stack[topPointer]
topPointer = topPointer -1
stack push code
if topPointer < maxLen -1:
topPointer = topPointer +1
stack[topPointer] = item
else:
print(‘stack full’)
queue data structure code
queue = [0]*10
frontPointer = 0
rearPointer = -1
length = 0
maxLen = 10
enqueue code
if length < maxLen:
if rearPointer < length -1
rearPointer = rearPointer +1
else
rearPointer = 0
length = length + 1
queue[rearPointer] = item
else:
print(‘full’)
dequeue code
if length == 0:
print(‘empty’)
else:
item = queue[frontPointer]
if frontPointer == length -1
frontPointer = 0
else:
frontPointer = frontPointer -1
linked list code
list <- []11
listpointers <- []11
pointerStartPointer <- 0
startPointer <- -1
FOR i (0,11)
listpointer[i]<- i+1
listpointers[11] <- -1
