IADs
Measuring Algorithm Efficiency
Space Complexity
Time Complexity
Algorithms
Important Algorithms
Insert sort (in place or not)
Merge sort (recursive/ iterative)
Asymptotic notation
f is o(g). f < g for a large enough input of n
f is O(g): f ≤ g for a large enough input of n
f is Θ(g): f = g for a large enough input of n
f is ω(g): f > g: for a large enough input of n
f is Ω(g): f ≥ g for a large enough input of n
Formal definition for all of them
f grows slower than g
f grows faster than g
tight bound vs loose bound
f is an asymptotically tight bound for g. g is between two values c1 and c2 for f over a large enough input.
Tricky example 2^2n != O(2^n). 2^2n/2^n tends to infinity
f grows at maximum the same speed as g (as it can be asymptotically tight)
Best case, worst case, average case
See slide 4 in lecture 5 for examples on how to use them
Example: Modular exponentiation
click to edit
Number of comparisons
insert sort, exactly n(n-1)/2 comparisons
Representing Data
Memory
The Stack
The stack is contiguous memory so items on the stack have fixed size.
Stack items usually contain a basic value, or a reference to something on the heap
Heap
Memory set aside for dynamic allocation. Allows items to grow and shrink.
Not contiguous, items can be stored anywhere on the heap
Heap objects can become unreachable, garbage collectors then deal with them.
Equality testing: by reference or by content
Shallow copy vs deep copy
Shallow copy only copies the reference(s)
Deep copy creates a fresh copy of the entire structure
Accessing an object from a reference is called dereferencing. As you are getting the value instead of the reference.
Program variables are stored in the stack
Data Structures
Concrete Implementations
Array
Allocating is O(1), initialising is not
Why is insert O(n) and append is O(1)
Fixed size
Extensible
It assigns more space than is currently needed by some factor r.
s=logr(m/a). s:number of steps(array copies), r:extend factor, a original array size, required array size
click to edit
Operations
set: overwrite at position
append: add item to the end of the structure
add item to middle of strucutre (displaces items, but doesn't overwrite or delete)
Abstract Interface
Queues
Stacks
linked list
array
linked list
Dictionary
data not stored in sequential order
stored as key value pairs
Usually implemented as a HashMap
no two items have the same key
Set
same idea as a mathematical set
There is no order to the items
Trees
Can represent hierarchical relations in data
Linked List
array
Times for all ops
HashMap
Hashing rules. What are good criteria for hashing algorithms
How to deal with clashes
Depending on implementation can provide worst case operations of O(log(n))
Self balancing trees
AVL
Red Black tree
2-3
Root and all null nodes are black (all leaves have two null children nodes)
All paths from root to leaves have the same number of black nodes
On all paths there are never two red nodes consecutively. Red nodes can only have black children
min path length of b max path length of 2b-1
click to edit
Recursive Functions
Master Theorem
What is the formula, what does each term mean?
what are: a,b,e,k
different time complexities for ways in which e compares to k
why is it a compares to b^k rather than a compares to n^k/b
IADs ToDo: 1. Write up master theorem, learn best case, average case worst case for all structures, hashmaps buckets insert probe clash probability, detailed knowledge of byref byval, extensible arrays formulas, red black tree formulae and balancing rules, merge sort insert sort rules. DO QUESTIONS FROM TEXTBOOK ON EACH SECTION
Unbalanced binary tree
Creating a binary tree from n an array of length n is n*lg(n) (as there are n inserts)
Graphs
Representation
Adjacency list
Adjacency Matrix
Search
graph G = (V,E) vertices and edges
It can be directed or undirected
It can be weighted or unweighted
Breadth First Search
Finds shortest path (by smallest number of edges) to all vertices in the graph
produces tree with all reachable vertices
white node undiscovered, grey node discovered not visited, black node discovered and visited.
Uses a queue to visit the nodes in a breadth first fashion. This means that for each depth level (number of edges away from start node)) it visits all the nodes before descending to another depth level.
Time complexity is O(V + E)
Depth First Search:
Can perform topological search for DAG
Decomposing DAG into strongly connected components. Strongly connected if every component can reach every other component
Max/min Heap
Not total ordering only provides a good way of getting max value
every node >= its child nodes
all leaves must be at either h-1 or h. The tree needs to be complete or almost complete
Operations
Heap max - max on heap O(1)
Max heapify - maintain the max heap O(lgn)
Heap Extract Max - Pops max value of heap and maintains heap properties O(lgn)
Max Heap Insert - Inserts new item into stack O(lg n) while maintaining heap properties
Build max heap - takes array and produces heap
Assumes left node and right node are both valid max/min heaps and that i is the problem node
swaps nodes down tree until valid heap
Insert node into next available spot in the level and bubble up the tree
Heap sort is O(n lgn), it is inplace, it is not stable
Priority queue
Max heap
Red black tree. Has O(lg n) max heap so isn't as good as max heap
Quicksort
Graph: a set of vertices and edges connecting vertices
can be directed or undirected
Implementations
Adjacency matrices
Adjacency lists