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
search linked list code
found <- FALSE
itemPointer <- StartPointer
WHILE (itemPointer<> nullPointer) AND NOT found
IF list[itemPointer] = itee
found<- TRUE
ELSE
itemPointer<- listpointers[itemPointer]
prin(itemPointer)
inserting items into linked list code
IF pointerStartPointer = -1
OUPUT ‘list full’
ELSE
tempPointer <- startPointer
startPointer<- pointerStartPointer
pointerStartPointer <- pointerlist[pointerStartPointer]
list[startPointer] <- item
listPointer[startPointer] <- tempPointer
removing items linked list code
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
binary trees - how they store data
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
finding item in binary tree code
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
inserting items in binary tree
needs free nodes
code in textbook
how to implement ADTS using another ADT
eg linked list - integers for pointers and string for item
dictionary implements
using a linked list
- key is a linked list
- value is an array of strings
bug O order of time complexity
O(1)
O(N)
O(N²)
O(2^N)
O(LogN)
O(1) - time
describes an algorithm that always takes the same time to perform the task
eg deciding if a no is even or odd
O(N) - time
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
O(N²) - time
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
O(2^N) - time
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
O(LogN) - time
describes an algorithm where the time to perform the task goes up linearly as the number of items goes up exponentially
eg binary search
big O order of space complexity
O(1)
O(N)
O(1) - space
describes an algorithm that always uses the same space to perform the task
eg algorithm that just uses variables
O(N) - space
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
recursion
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
base case
a terminating solution to a process that is not recursive
general case
a solution to a process that is recursively defined
winding
the statements after the recursive call arent executed until the base case is reached
unwinding
after the base cased is reached and can be used in the recursive process the function is unwinding
benefits of recursion + negative
+ 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
how compiler implements recursion
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
