Show Menu
Cheatography

COMP250 Cheat Sheet by

Algorithms

Definition
unambi­guous procedure executed in a finite number of steps
What makes a good algorithm?
Correc­tness, Speed, Space, Simplicity
Speed:
time it takes to solve problem
Space:
amount of memory required
Simpli­city:
easy to unders­tand, easy to implement, easy to debug, modify, update

Running Time

Definition
measur­ement of the speed of an algorithm
Dependent variables:
size of input & content of input
Best Case:
time on the easiest input of fixed size
meanin­gless
Average Case:
time on average input
good measure, hard to calculate
Worst Case:
time on most difficult input
good for safety critical systems, easy to estimate

Proofs by Induction (Examples)

Loop Invariants

Definition
loop property that holds before and after every iteration of a loop.
Steps:
1. Initia­liz­ation
If it is true prior to the iteration of the loop
2. Mainte­nance
If it is true before an iteration of the loop, it remains true before the next iteration
3. Termin­ation
When the loop termin­ates, the invariant gives us a useful property that helps show the algorithm is correct

QuickSort

Divide:
choose an element of the array for pivot
 
divide into 3 sub-gr­oups; those smaller, those larger and those equal to pivot
Conquer
recurs­ively sort each group
Combine
concat­enate the 3 lists

QuickSort

Algorithm partition(A, start, stop)
Input: An array A, indices start and stop.
Output: Returns an index j and rearranges the elements of A
such that for all i<j, A[i] ! A[j] and
for all k>i, A[k] " A[j].
pivot # A[stop]
left # start
right # stop - 1
while left ! right do
while left ! right and A[left] ! pivot) do left # left + 1
 while (left ! right and A[right] " pivot) do right # right -1
if (left < right ) then exchange A[left] $ A[right]
exchange A[stop] $ A[left]
return left
Time Comple­xities:
• Worse case:
– Already sorted array (either increasing or decrea­sing)
– T(n) = T(n-1) + c n + d
– T(n) is O(n2)
• Average case: If the array is in random order, the
pivot splits the array in roughly equal parts, so the
average running time is O(n log n)
• Advantage over mergeSort:
– constant hidden in O(n log n) are smaller for quickSort.
Thus it is faster by a constant factor
– QuickSort is easy to do “in-place”

In Place Sorting

Defini­tion:
Uses only a constant amount of memory in addition of that used to store the input
Import­ance:
Great for large data sets that take up large amounts of memory
Examples:
Selection Sort, Insertion Sort (Only moving elements around the array)
MergeSort:
Not in place: new array required
 

Object Orientated Progra­mming

Defini­tion:
User defined types to complement primitive types
 
Called a class
Contains:
Data & methods
Static members:
members shared by all objects of the class

Recursion Progra­mming

Definition
using methods that call themselves
Structure:
base case
a simple occurrence that can be answered directly
recursive case
A more complex occurrence of the problem that cannot be directly answered, but can instead be described in terms of smaller occurr­ences of the same problem.

Divide & Conquer

Divide
the problem into sub problems that are similar to the original but smaller in size
Conquer
the sub-pr­oblems by solving them recurs­ively. If they are small enough, solve them in a straig­htf­orward manner
Combine
the solutions to create a solution to the original problem

BIG O Definition

f(n) & g(n) are two non negative functions defined on the natural numbers N
f(n) is O(g(n)) if and only if:
there exists an integer n0 and a real number c such that Ɐn>= n0 f(n) <= c * g(n)
 
N.B. The constant c must not depend on n

Big O Visual­ization

Big O Recurrence

Sum of ai from 0 to n = (a(n+1) -1 )/(a-1)

Limita­tions of Arrays

Size has to be known in advance
memory required may be larger than number of elements
inserting or deleting an element takes up to O(n)

ADT: Queues

FIFO(First in first out)
Any first come first serve service
Operations
enqueue() - add to rear
 
dequeue() - removes object at front
 
front() - returns object at front
 
size() - returns number of objects O(n)
 
isEmpty() - returns true if empty
Double Ended Queues­(de­que): Allows for insertions and removals from front and back
- By adding reference to previous node - removals occur in O(1)

ATD: Stacks

Def:
Operations allowed at only one end of the list (top)
 
LIFO: (Last in first out)
Operat­ions:
push() - inserts element at top
 
pop() - removes object at top
 
top() - returns top element without removing it
 
size() - returns number of elements
 
isEmpty() - returns True if empty
Applic­ations
page visited history in web browser
 
JVM - keeps track of chain of active elements (allows for rec)
Perfor­mance:
space used: O(n)
 
operat­ions: O(1)
Limita­tions
max size must be defined prior
 
pushing to a full stack causes implem­ent­ation specific error
 

Binary­Search

BinarySearch(A[0..N-1], value) {
      low = 0
      high = N - 1
      while (low <= high) {
        mid = (low + high) / 2
          if (A[mid] > value)
              high = mid - 1
          else if (A[mid] < value)
              low = mid + 1
          else
              return mid
      }
      return not_found // value would be inserted at index "low"
  }
Invari­ants:
value > A[i] for all i < low value < A[i] for all i > high
Worst case perfor­mance: O(log n)
Best case perfor­mance: O(1)
Average case perfor­mance: O(log n)

Binary­Search (Recur­sive)

int bsearch(int[] A, int i, int j, int x) {
if (i<j) {
int e = [(i+j)/2];
if (A[e] > x) {
return bsearch(A,i,e-1);
} else if (A[e] < x) {
return bsearch(A,e+1,j);
} else {
return e;
}
} else { return -1; }
}
Time Comple­xity: log(ba­se2)(n)

Insertion Sort (Itera­tive)

For i ← 1 to length(A) - 1
 j ← i
 while j > 0 and A[j-1] > A[j]
 swap A[j] and A[j-1]
 j ← j - 1
 end while
end for
Time comple­xity: O(n2)
 

Merge-­the­n-sort

Algorithm ListIntersection (A,m, B,n)
Input: Same as before
Output: Same as before
inter ← 0
Array C[m+n];
for i ← 0 to m-1 do C[i] ← A[i];
for i ← 0 to n-1 do C[ i+m ] ← B[i];
C ← sort( C, m+n );
ptr ← 0
while ( ptr < m+n-1 ) do {
 if ( C[ptr] = C[ptr+1] ) then {
 inter ← inter+1
 ptr ← ptr+2
 }
 else ptr ← ptr+1
}
return inter
Time Comple­xity: (m+n) * (log(­m+n)) + m + n -1

MergeSort (Recur­sive)

MergeSort (A, p, r) // sort A[p..r] by divide & conquer
if p < r
   then q ← ⎣(p+r)/2⎦
      MergeSort (A, p, q)
      MergeSort (A, q+1, r)
      Merge (A, p, q, r)
Time Comple­xity: 2T(n/2) + k • n + c’

Primitive Operations

assignment
calling method
returning from method
arithmetic
compar­isons of primitive types
condit­ional
indexing into array
following object reference
Assume each primitive operation holds the same value = 1 primitive operation

Prove Big - Oh

Help Us Go Positive!

We offset our carbon usage with Ecologi. Click the link below to help us!

We offset our carbon footprint via Ecologi
 

Comments

No comments yet. Add yours below!

Add a Comment

Your Comment

Please enter your name.

    Please enter your email address

      Please enter your Comment.