FINAL CHEAT SHEET.

Cheat Sheet > FINAL CHEAT SHEET.

McGill University COMP 250public class HockeyTeam extends SportTeam (SportTeam = superclass; constructor super()) HockeyTeam(input){ super(); ties = 0;} SportTeam bruins = new HockeyTeam(); —> legal HockeyTeam leafs = new SportTeam(); —> not legal —————————————————————— — ...[Show More]

McGill University
COMP 250public class HockeyTeam extends SportTeam

(SportTeam = superclass; constructor super())

HockeyTeam(input){ super(); ties = 0;}

SportTeam bruins = new HockeyTeam(); —> legal

HockeyTeam leafs = new SportTeam(); —> not

legal

——————————————————————

—

Algo: BubbleSort (int arr[])

Best case: O(1) —> ARRAY SORTED

Worst case: O(n^2)

for i=0 to N-2 {

for j = 0 to N-2-i { //-i because at

the end of the 1st loop, the largest

integer will be in the end of the array,

so on…

if list [i] > list[i+1] { swap

(list[i], list[i+1]) } } }

iterate through the list many times: swap if 2 elms

in the wrong order.

Algo: SelectionSort (int arr[])

O(N^2) FOR BEST CASE AND WORST CASE

for i=0 to N-2 { //repeat N-1 times

tmpIndex=i // take first elem in

unordered array

tmpMinValue= list[i] //let it be temp

min

for k=i+1 to N-1 { //for every other elem

in unordered arr

//n(n-1)/2 passes though inner loop

if (list[k] < tmpMinValue) { //if current

elem is < tmpMin

tmpIndex=k //then make it the new temp

min

tmpMinValue=list[k] }

if (tmpIndex != i) swap(list[i],

list[i+1]) //swap if necessary } }

1. scan numbers in rest and find smallest elem

2. put smallest elem in front of sorted array =

array[0]

3. scan remainder of array & look for smallest

elem & put it in array[1]

Algo: InsertionSort(int arr[])

Best case: O(N) —> LIST ALREADY SORTED

Worst case: O(N^2) —> LIST SORTED

BACKWARDS

for k=1 to N-1{

elemK= list[k] //elemK is 2nd elem

in arr

i=k // i is set to index

while(i > 0) and (list[i-1] > elemK){

// shift the elems in sorted portion

list[i]= list[i-1]

i= i-1 }

list[i]= elemK //when elem is in the

right

}

- look at first elem not in sorted portion and look

where it should be placed in sorted portion, then

increase sorted portion by 1 after insertion

- to make space to insert = req. shift all elems

after insertion pt

ITERATIVE ALGORITHMS

prob solved by iterating through loops

Algo: power(a,n)

product=1

for i = 0 to n do { product=product*a}

return product

RECURSIVE ALGOS

algo that solves the problem by calling itself

(needs a BASE CASE)

Algo: power(a,n)

if (n==0) then return 1 //base case

else {

previous = power(a,n-1) //

recursive call

return previous*a }

RECURSIVE BINARY SEARCH O(LOG N)

Algo uses binarySearch(array, strt, stop, key)

if (start=stop) {

if (array[start]= key) then return

start

else return -1

}

else {

mid = (start+stop)/2 //rounded down

if (array[mid] = key) position =mid

if (array[mid] > key)

position=binarySearch(array, strt, mid,

key) //scans left portion of

array

if (array[mid] < key)

position=binarySearch(array, mid+1,

stop, key) //scans right portion

of array

return position

FIBONACCI SEQUENCE (ITERATIVE)

Algo: IterFib(n)

In: int n out: n-th fibonacci number

if (n==0) return 0 ; if (n==1) return 1

prev = 0 //prev Fib term

current = 1 //current Fib term

for i =2 to n do

tmpCurrent = current

current= current + prev

prev = tmpCurrent

return current

RECURSIVE FIBONACCI O(2^N)

Algo: Fib(n) //position of number we are

looking for

in: int n ; out: n-th Fib

term

if (n == 0) return 0 ; if (n == 1)

return 1

first = Fib(n-1) ; second = Fib(n-2)

return first+second

—> not efficient: you compute the same fib

many times

MERGESORT

divide array into 2; recursively sort each half

(create a tmp array that will eventually contain

a sorted array)

Algo: Merge(Arr, left, mid, right) O(log n)

indexLeft = left //first pos. of left

indexRight =mid+1 //first pos. of

right

tmp = array of same type and size as

A

tmpIndex = left //tmpIndex= 1st index

of arr

while (tmpIndex <= right) do {

if (indexRight > right) or

(indexLeft <= mid && A[indexLeft]

<=[indexRight])

tmp[tmpIndex] = A[indexLeft]

indexLeft = indexLeft+1

} else {

tmp[tmpIndex] = A[indexRight]

indexRight = indexRight+1 }

tmpIndex = tmpIndex +1 }

for k=left to right do Arr[k] =

tmp[k]

Algo: mergeSort(Arr,left, right) O(N

LOG N)

if (left == right) do nothing //not

needed

if (left < right)

mid = (left+right)/2

mergeSort (A, left, mid) //

A[left..mid] is sorted

mergeSort(A, mid+1, right) //

A[mid+1 .. right] is sorted

merge(A, left, mid, right) //code

that actually moves elems

INDUCTION PROOFS

1. Base case: P(n0)

2. Induction step: n>= n0, if P(n) then P(n+1)

is also true

Ex: P(n) : 4n < n!. We prove that P(n) is true

for all n ≥ 9.

1)Base case. For n=9, we have 4n = n!.

2) Induction step. The induction hypothesis

is P(k) : 4k < k!. We then show that for any

k≥9, P(k) implies P(k+1):

4k+1 <(k+1)! , 4k+1 = 4·4k< 4·k!(byI.H.) <

(k+1)·k! (since k≥9) = (k+1)!

PROOFS W/ LOOP INVARIANTS

1. Init - LI true prior to first iteration (base

case)

2. Maintenance - LI remains true before next

iteration (ind. step)

3. Term - when loop terminates, LI gives

useful property that proves algo is correct

(Induction Proofs stop when loop terminates

but LI are used infinitely)

ex: MERGESORT

Inductive Hypothesis: Assume MergeSort

correctly sorts n=1, ... , k elements

Inductive Step: Show that MergeSort

correctly sorts n = k + 1 elements.

Proof:

- 1st rec call n1=qVp+1=(k+1)/2 ≤ k =>

subarray A[p .. q] is sorted

- 2nd rec call n2=rVq=(k+1)/2 ≤ k =>

subarray A[q+1 .. r] is sorted

- A, p q, r fulfill now the precondition of Merge

- The postcondition of Merge guarantees that

the array A[p .. r] is sorted => satisfied.

NOTE: for algos with nested loops, must find

LI for each loop

RUNTIME ANALYSIS

operations: Tassign, Tcall, Treturn, Tarith,

Tcomp, Tcond, Tindex, Tref

Σ(i=1 —> n) = n(n+1)/2

for(i=0; i<n; i++) —> runs n times

BIG O-NOTATION:

f(n) is O(g(n)) iff: there exists an int "n0" and

real num. "c", s.t for all n>= n0 f(n) <= c*g(n)

f(n) is Ω(g(n)) iff g(n) is O(f(n))

f(n) is Θ(g(n)) iff f(n) = O(g(n)) and f(n) =

Ω(g(n))

ex: PROVE n(sin(n)+1) is O(n) -->showE c

and n0 s.t.: n*(sin(n)+1)<=c*n for all n>=n0

n(sin(n)+1) <= n(1+1) (1 = max {sin(n)}) = 2n

= c*n (c=2)

So, n(sin(n)+1) <= c*n for all n>=n0 where

c=2 and n0=0

Algo: quicksort (Arr, start, stop)

BEST/ AVERAGE CASE: O(n log n)

WORST CASE: O(n^2) --> array sorted incr/decr

if (start == stop) do nothing //base

case

if ( start < stop)

pivot = partition (Arr, start, top) //

returns the index of the pivot

quickSort (Arr, start, pivot-1)

quickSort (Arr, pivot+1, stop)

- scan for elems > pivot A[0] --> right

- scan for elems < 0 A[length -2] <-- left

- swap elems larger than pivot and smaller than pivot

recursive pattern = choose a pivot on each half and

Quicksort on each half

Algo: partition (Arr, start, stop)

In: arr and indices

out: returns position where pivot was inserted so that

Quicksort knows which halves to look at

+ rearranges the elements of A

- first while loop: pivot is in last index

- LHS moves index until index points to elem larger

than pivot

- left <= right the point where LHS and RHS meet

Algo: partition (Arr, start, stop) O(n)

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 A[left] ↔

A[right] and A[stop] ↔ A[left]

return left

IN PLACE ALGO: CONSTANT AMT OF MEMORY

IN PLACE: SelectionSort, InsertionSort

NOT IN PLACE: MergeSort (temp array)

CAN BE DONE IN PLACE: QuickSort

LIST ADT - data stored = ordered set of objects [1, 2,

3]

ARRAY IMPLEMENTATION OF THE LIST ADT

1D array to store elems of list & int size to record #

obj

O(1): getFirst() ; getLast() ; getNth(n) ;

insertLast(Object o) ; removeLast() ; getSize() ;

O(n): insertNth(n, o) ; insertFirst(Object o) ;

removeFirst() ; removeNth(n) ; concatenate(List l)

insertNth(into n, Object o) { // req. shifting & is

slow

for i ← size downto n {

L[i] ← L[i-1]; }

L[n] ← o; size ← size +1 }

PROS: easy, space efficient

CONS: number of stored objects stored must be

known in advance, a lot of insertions and removals

LINKED LIST IMPLEMENTATION OF THE LIST

ADT

linked list: seq. of nodes; is a recursive data structure

linkedList a = new linkedList(head, tail);

O(1): node.getNext() ; node.getValue() ;

node.setValue(o) ; node.setNext(node) ;

list.getFirst() ; list.getLast() ; list.addLast(o) ;

list.addFirst(o) ; list.removeFirst() ;

O(n): list.getNth(n) ; list. insertNth(n,o) ;

list.removeLast() ; list.getSize()

- Node: [value | next]

node b = new node (object x, node next);

- List: ["Go" | --]--> [ "Habs" | --]---> ["Go" | -- ]-->

null

Head Tail

List l = new List();

public class node {

private Object value;

private node next; // constructor

public node(Object x, node n) {

value = x;

next = n; }

class linkedList {

node head, tail;

getFirst() { return head.getValue(); }

getLast() { return tail.getValue(); }

getNth() //req to go to 1 before Nth place (need to

loop from start until Nth-1)

void addLast(Object x) {

if (tail == null) tail=head=new node(x,

head);

else {

tail.setNext( new node(x,null) );

tail = tail.getNext(); } }

void addFirst(Object x) {

head = new node(x, head);

if (tail == null) tail = head; }

removeFirst() {

if (head==null) return false; // list

empty

head = head.getNext(); }

removeLast(){

if (head==null) return false;

node newtail = head;

while (newtail.getNext()!=tail)

{

newtail =

newtail.getNext(); }

newtail.setNext(null);

tail = newtail; }

Object getNth(int n){

if (n>=size()) throw new

IndexOutOfBoundsException();

node current=head;

while (n>0) { //it from head to n

current = current.getNext();

n--; }

return current; }

boolean insertNth(int n, Object x){

if (n>=size()) throw new

IndexOutOfBoundsException(“n too

big!");

node predecessor = head;

while (n>1) {

predecessor =

predecessor.getNext();

n--; }

node new elem = new node(x,

predecessor.getNext() );

predecessor.setNext(newelem);

return true; }

boolean remove(Object o) {

if (head==null) throw new

NoSuchElementException;

if (head.getValue().equals(x)) {

head=head.getNext();

if (head==null)

tail=null;

return true; }

node current = head;

while (current.getNext()!=null

&& !

current.getNext().getValue().equals

(x))

current = current.getNext();

if (current.getNext()==null)

return false;

else {

current.setNext(current.getNext().g

etNext());

if (current.getNext()==null)

tail=current; }

return true;

STACK ADT

First one in, last one out

Operations: push(object) ; object pop() ;

object top() (peek() in java) ; size() ;

isEmpty()

Stack In JVM : keeps track of chain of

active methods with a stack: When method

is called, JVM pushes on the stack a frame

containing: Local vars, return values, and

PC (pgm counter) to keep track of stmt

being executed. when method ends, frame

is popped from stack

STACK WITH ARRAYS

public class ArrayStack {

private Object S[ ];

private int top = -1; // index to

top element

public ArrayStack(int capacity)

{ // constructor

S = new Object[capacity]); }

ArrayStack s = new ArrayStack (int

capacity);

—> capacity fixes the size of the array

O(1); push(o) ; pop() ; top()/peek() ;

size()

- add elements left to right; var keep