Foundation Exam

Front 1

Injective Function (one-to-one)

Back 1

f(a) = f(b) -> (a=b) for all a & b in domain f

Never more than one incoming arrow, but not always an arrow from left to all of right values if A ->B then |A| <= |B|

Front 2

Surjective (onto)

Back 2

For all b in B, there exists an a in A such that f(a) = b Multiple arrows can go to an answer on the right, and every value on right will have an arrow going to it. if A->B then |A|>=|B|

Front 3

Bijective

Back 3

Both injective and Surjective. One-to-one and only functions to have inverses if A->B then |A|=|B|

Front 4

What value is in every set

Back 4

Null

Front 5

A = {1} B = {2} AUB = ?

Back 5

{1,2}

Front 6

A = {1} B = {2} AnB = ?

Back 6

{NULL}

Front 7

Assume:

p

p->q

Then q

Back 7

Modus Ponens

Front 8

Assume:

p->q

q->r

Then p->r

Back 8

law of syllogism

Front 9

Assume:

p->q

-p

Then -q

Back 9

Modus Tollens

Front 10

A|B means

Back 10

A divides B so A is a factor of B

Front 11

A|B and A|C implies?

Back 11

A|(B+C)

Front 12

What are the three parts of Inductions

Back 12

Base Case, Inductive Hypothesis, Inductive Step

Front 13

A = R(mod B) is equivalent to

Back 13

A = Bn + R

Front 14

Reflexive

Back 14

aRa for every element a in A

Front 15

Irreflexive

Back 15

a does not Ra for every element a in A

Front 16

Symmetric

Back 16

if aRb -> bRa for all a, b in A

Front 17

Antisymmetric

Back 17

if aRb and bRa -> a=b for all a,b in A

Front 18

Transitive

Back 18

if aRb & bRc -> aRc for all a,b,c in A

Front 19

[x] = {a|a is an element of A ^ aRx} is an example of

Back 19

Equivalence classes

Front 20

Big O best and worst case of Insert of linked list

Back 20

Best: O(1) Average: O(n) Worst: O(n)

Front 21

Big O best and worst case of Quick sort

Back 21

Best: O(nlogn) Average: O(nlogn) Worst: O(n^2)

Front 22

Big O best and worst of hash table access of value

Back 22

Best: O(1) Worst: O(n)

Front 23

Big O best, average, worst of binary tree search

Back 23

Best: O(1) Average: O(lgn) Worst: O(n)

Front 24

Big O of Bubble sort

Back 24

Best: O(n) Average & Worst: O(n^2)

Front 25

Big O of Merge sort

Back 25

O(nlgn)

Front 26

Definition of set difference

Back 26

n(negC U negB) becomes - (CnB)

Front 27

Definition of implication

Back 27

(q->r) == (-q v r)

Front 28

Equivalence relation

Back 28

reflexive, symmetric, and transitive

Front 29

Partial Ordering Relation

Back 29

Reflexive, Anti-symmetric, and transitive

Front 30

Binary Search on sorted list Average and worst case, Space time complexity

Back 30

Avg: O(logn) Worst: O(logn) Space complexityO(1)

Front 31

Quicksort

Back 31

Best: O(n log(n)) Avg: O(n log(n)) Worst: O(n^2) Space complex. worst: O(n)

Front 32

Mergesort

Back 32

Best: O(n log(n)) Avg: O(n log(n)) Worst: O(n log(n)) Space worst: O(n)

Front 33

Heapsort

Back 33

Best: O(n log(n)) Avg: O(n log(n)) Worst: O(n log(n)) Space worst: O(1)

Front 34

Bubble Sort

Back 34

Best: O(n) Avg: O(n^2) Worst: O(n^2) Space: O(1)

Front 35

Insertion Sort

Back 35

Best: O(n) Avg: O(n^2) Worst: O(n^2) Space: O(1)

Front 36

Selection Sort

Back 36

Best: O(n^2) Avg: O(n^2) Worst: O(n^2) Space: O(nk)

Front 37

Bucket Sort

Back 37

Best: O(n+k) Avg: O(n+k) Worst: O(n^2) Space: O(nk)

Front 38

Radix Sort

Back 38

Best: O(nk) Avg: O(nk) Worst: O(nk) Space: O(n+k)