Coursework 02 Revision

Recurrence Relations

• Is a recursively-defined function. Applied to the case when the function is some measure of resources.
• The runtime of a program is $T(n)$, then a recurrence relation will express $T(n)$, then a recurrence relation will express $T(n)$ in terms of its values at other (smaller) values of $n$.
• Solving Recurrence:
  1. Starting from the base case, use the recurrence to work out many cases, by directly substituting and working upwards in values of n.
  2. Inspect the result, look for a pattern and make a hypothesis for the general results
  3. Attempt to prove the hypothesis - typically using some form of induction
• Often then extract the large n behaviour using big-Oh family. Can be long, tedious, and error-prone, but many cases are covered by a general rule with the name of "Master Theorem"

Master Theorem

$T(n)=aT(n/b)+f(n)$ -> Results are split into 3 cases, according to comparing the growth rate of $f(n)$ to $n^{(\log_b(a))}$

• Case 1: $f(n)$ grows slowly. Recurrence term dominates. Solution ignores $f$
  • $f(n)$ is $O(n^c)$ with $c<\log_ba$
  • $T(n)$ is $\theta(n^{\log_ba})$
• Case 2: $f(n)$ grows same - up to log factors - "mix of recurrence with a,b, and also the $f(n)$ term"
  • $f(n)$ is $\theta(n^c(\log n)^k)$ with $c=\log_ba$ and $k\ge0$
  • $T(n)$ is $\theta(n^c(\log n)^{(k+1)})$
• Case 3: $f(n)$ grows faster. "Solution ignores recurrence terms and a,b"
  • $f(n)$ is $\Omega(n^c)$ with $c>\log_ba$
  • $f(n)$ satisfies the regularity condition
  • $af(n/b)\le kf(n$) for some $k<1$

Vectors and amortised complexity

• Vector - Abstract Data Type, ADT, corresponding to generalising the notion of the Array. Stores a sequence of arbitrary objects
• Rank - Number of elements preceding it (index)
• Application - No automatic limit on the storage size, direct applications (sorted collection of objects), indirect applications (auxiliary data structure)

• Operation elemAtRank(r) - $O(1)$
• Insertion - insertAtRank(r,o), need to make room for the new element by shifting forward the n-r elements. Worst case $(r=0)$ takes $O(n)$
• Deletion - removeAtRank(r), need to fill the hole left by the removed element by shifting backward the $n-r-1$ elements. Worst case $(r=0)$ takes $O(n)$
• Performance - In the array-based implementation of a Vector
  • Space used by the data structure is $O(n)$
  • size, isEmpty, elemAtRank and replaceAtRank run in $O(1)$
  • insertAtRank and removeAtRank run in $O(n)$ time
  • push runs in $O(1)$ time, as do not need to move elements
  • pop runs in $O(1)$ time
• Growable Array-based Vector - In a push operation, when the array is full, instead of throwing an exception, can replace the array with a larger one. Has a high cost of $O(n)$.
  • Incremental Strategy - Increase size by a constant c
  • Doubling Strategy - Double the size
• Amortize - Time of a push operation the average time taken by a push over the series of operations

Why is amortised analysis different from the average case analysis

Amortised - (long) real sequence of dependent operations Average - Set of (possibly independent) operations

ADTs/CDTs Stacks/Queues using linked lists

ADT - Only concerned with specifying the interface. Behaviour as seen from the outside. Specifies the methods provided - and possibly requirements on their complexity (Interface) CDT - Some structure and algorithm used for an actual implementation. Behaviour as seen from the outside (Implementation)

Performance and Limitation of Array-based Stack

Performance

• Let $n$ be the number of elements in the stack
• The space used is $O(n)$
• Each operation runs in time $O(1)$
• Max size of the array-based stack must be defined in advance and cannot be changed dynamically
• Trying to push a new element into a full stack causes an implementation-specific exception

Narrow - Small set of methods. Stack ADT, less flexible to use, more flexible to implement, maybe more efficient Wide - Large set of methods. Java Stack, more flexible to use, possibly more difficult to implement efficiently

Linked List vs. Array based CDTs

Array

• Con - Fixed size - might need a lot of unused space
• Pro - Contiguous in memory. Localised memory access, gives better use of the (CPU) cache - e.g. machine level "pre-fetch" will tend to do the right thing Linked List
• Pro - size grows and shrinks automatically
• Con - Can be scattered around memory, and give poor usage of the cache
• Con - Storage of the next references doubles the space usage

Priority Queues and Heaps

Can use a heap to implement a priority. We store a (key, element) item at each node. We keep track of the position of the last node.

Implementing PQ with a Heap

• Initialise a heap
• Insert in the head
• Ask for the value of the root of the heap (minimal key)
• Remove the root ad return the value stored there (dequeue the highest priority)

Heap-sort

• Consider a priority queue with $n$ items implemented by means of a heap
  • Space used is $O(n)$
  • methods insert and removeMin take $O(\log n)$ time
  • methods size, isEmpty, and min take time $O(1)$
• Using a heap based priority queue, can sort a sequence of $n$ elements in $O(n\log n)$ time