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