CSI 2101 - final

S = x^d+x^d-1+…+x⁰ evaluated

S = (x^d+1 - 1)/(x-1)

S = 1^x + 2^x + … + n^x evaluated

S = an³ + bn² + cn + d

order of growth

1 < logn < sqrt(n) < n < n * logn < n² < n³ < 2ⁿ < 3ⁿ < n!

Big-Oh

a function f is big-oh of another function of g if there exists a constant C>0 such that g is greater than f for any sufficiently large input. with limits, the limit of x approaching infinity of f/g should be less than infinity

big-oh facts

the big-oh of any n within a logarithmic function (eg log(n⁵)) is logn

big-theta

a function f is big-theta of g if f is O(g) and g is O(f). with limits, the limit of x approaching infinity of f/g is between 0 and infinity

big-theta facts

the log of any polynomial in n is big theta of logn. logn is big theta of ln n

little-oh

a function f is little-oh of another function g if for EVERY constant c>0, f< c*g. with limits, the limit as x approaches infinity of f/g is 0

little-oh facts

• if f is o(g) it’s also O(g)

• n^a is o(n^b) if a<b

• Bⁿ is o(Cⁿ) if 0<B<C

• for all a,b > 0, log(n)^a is o(n^b)

• for a>0 and B>1, n^a is o(B^x)

unfolding recurrences

expand a recurrence and spot the pattern. if f(n-1) is the inner term, the steps it takes to get from f(n-1) in the function to f(1) is n-1. if f(n//2) is the inner term, the steps it takes to get from f(n/2) in the function to f(1) is logn

homogenous linear function

you can turn a recurrence of form f(n) = Af(n-1) + Bf(n-2) into an equation of the form f(n) = s*xⁿ + t*xⁿ by transforming the recurrence into x²= Ax + B and solving for x using the quadratic formula and solving for s and t with f(0) and f(1)

injective

for a function f:X→Y, it’s injective if every element in X has a distinct Y. This means |Y|>=|X|

surjective

a function f: X → Y is surjective if every element in Y is mapped by some x. surjective implies |X|>=|Y|

bijective

a function is bijective if it is both surjective and injective. it implies |X|=|Y|

the division rule

if f:X→Y is k-to-1 then |Y|=|X|/k

generalized pigeonhole principle

for every pair of sets where |X|>k*|Y|, for any function f:X→Y, there exists k+1 elements mapped to the same value of Y

calculating the number of k-sized subsets of S where order doesn’t matter

(1,2)=(2,1) use (n k) = n!/(k!(n-k)!)

degrees and edges relationship

the sum of all degrees of vertices is equal to twice the amount of edges

bipartite graph

a graph whose vertices can be partitioned into two groups such that each edge has a vertex in each partition

facts about bipartite graphs

• the sum of degree in each partition is equal

• cannot have a cycle of odd length

• a graph whose edges are the unions of two matchings is bipartite

matching

a subset of edges such that no edges share a vertex

perfect matching

a matching that covers all vertices. can only exist if theres an even number of matchings

hall’s theorem

there exists a perfect matching in a bipartite graph only if for every subset of vertices the number of neighbours of those vertices is greater than the number of vertices

stable matching

a matching of a ranked graph with no rogue couples

gale-shapley algorithm

for a complete ranked bipartite graph where the partitions, M and W, have an equal number of vertices, each element in M proposes to the most preferable element in W that has not rejected M. When an element in W receives two proposals, it rejects the one from the least desirable M. This creates a stable matching

Gale Shapley Facts

• for every m,w, if w rejects m then they are not part of ANY stable matching

• elements of W will end in a couplle with an m that is more or equally as desirable as its first proposal

connected

a graph is connected if there is a path between every vertex

connected component

a subgraph where all vertices are connected to a given vertex

forest

a graph with no cycles

tree

a connected forest

forest facts

• every forest has |V|-|E| connected components

• in a tree, |V|=|E|+1

• every connected graph has a spanning tree

digraph

a directed graph where edge (u,v) does not equal edge (v,u)

topological sort

the ordering of all vertices in a digraph so that for evefy edge (u,v) u comes before v in the order

topological sort facts

• if there is a cycle a topological sort isn’t possible

• a sink is at the end of a top sort, a vertex with no outgoing edges

DAG

acyclic digraph

parallel scheduling

a type of topological sort that denotes the latest each vertex could occur

parallel scheduling facts

for every dag, if the longest path has length L then the longest the parallel scheduling can be is L+1

antichain

a subset with no edges

antichain facts

a dag of n vertices has a path of length >=L or an antichain of size >= n/L

vertex disjoint

a collection of paths is vertex disjoint if each vertex in the collection only appears oncein any path of the collection.

switching network

a network where for every pairing of source and sink there exists a vertex-disjoint collection of paths from each source to sink

how to build up a benes network

splits the vertices you’re connecting edges to into two groups, top and bottom. your first two sources will connect to the same vertices, the topmost vertex in top group and the bottom group. continue the pattern for the next two sources. to connect your sinks, do the same but with incoming edges instead of outgoing.

1+2+3+4+…+n

(n(n+1))/2

log rules

log(a/b)= log(a)-log(b)