CSI 3105 Final

Fall 2025 uOttawa

decision problem

a problem with a solution that is either yes or no

polynomial running time

O(n^c) for some constant c > 1

euler cycle

a cycle that traverses each edge in a graph exactly once

hamiltonian cycle

a cycle that traverse each vertex in a graph exactly once

clique

a subgraph of a graph that is complete

independent set

a subset of vertices in a graph where none of the vertices share an edge

vertex cover

a subset of vertices in a graph where for each edge (u,v) ∈ E, at least u or v are in the subset

3sat formula

a boolean formula with n variables and m clauses. within each clause are 3 literals, making it 3 sat, with a literal being a variable or a negation of a variable. these formulas are of the form C₁∧C₂∧C₃∧…∧C_m with each clause C_i being of the form L₁ⁱ∨L₂ⁱ∨L₃ⁱ. these formulas are satisfiable if and only if there exists a truth assignment for the n variables such that the formula is true

language of a decision problem

the set of all inputs for which the answer is yes

ex: CLIQUE = {(G,K)| G is an undirected graph, k is an integer, and G contains a clique of size k}

complexity classes

sets of decision problems that have a specific run time complexity

what does it mean for a problem to be in P

the problem L is in polynomial P if:

• L is a decision problem

• there exists an algorithm A and a constant c >1 such that for any input x, x∈L if and only if

  • A(x) = yes

  • A is O(|x|^c)

what does it mean for a problem to be in NP

the problem L is in non-deterministic polynomial NP if:

• L is a decision problem

• there exists an algorithm V and a constant c >1 such that for any input x, x∈L if and only if

  • there exists a certificate y such that |y| is O(|x|^c)

  • V(x,y) = yes

  • V is O(|x|^c)

P and NP relation

• P⊆NP - P’s verification algorithm simply runs P’s algorithm ignoring the certificate, as P’s A is already polynomial

• it’s unknown whether P=NP. for all NP problems, we either know they are in P or we don’t know they aren’t. we’d need to prove there exists an NP problem that is not in P, or prove that there exists an NP Complete problem in P

polynomial time reduction

• a way to say a decision problem is more complex than another decision problem

• L ≤_p L’ means L can be solved using the algorithm for L’ and f

• L ≤_p L’ means L’ is at least as complex as L

• reduction is transitive, so if L ≤_p L’ and L’ ≤_p L’’, then L ≤_p L’’

how to prove L ≤_p L’

L ≤_p L’ (L is polynomial time reducible to L’) if there exists a function f such that

• f maps inputs of L to inputs of L’

• x∈L ↔ f(x)∈L’

• for every possible x, f(x) can be computed in O(|x|^c)

what does it mean for a problem to be NP Hard

the problem L is NP Hard if for all L’∈NP, L’ ≤_p L, though L does not have to be in NP

what does it mean for a problem to be NP Complete

the problem L is NP Compete if for all L’∈NP, L’ ≤_p L and L∈NP

conventions of NP Complete problems

• given that L is NP Complete, L∈P if and only if P=NP. this provides another way to prove whether P=NP or not, using reductions

• all NP Complete problems have the same level of difficulty

• all NP problems (excluding the P problems) discussed in class are NP Complete

how to prove a problem is NP Complete

to prove the problem L is NP Complete:

1. prove that L∈NP

2. find a similar problem L’ that is NP Complete

3. prove that L’ ≤_p L

are there NP problems that aren’t NP Complete

P problems, proven with the Trivial problem in which all inputs produce the same output

are there problems in NP not in P that are not NP Complete

because we don’t know if there are NP problems not in P, this is undecided.

• if P=NP, then there are not (because NP/P = ∅)

• if P≠NP, then there is a theoretical type of problem called NP Intermediate that is not in P nor is NP Complete

boolean logic facts

• ∧ is ‘and’

• ∨ is ‘or’

• DeMorgan’s Law: (p∨q)’ ≡ (p’∧q’) AND (p∧q)’ ≡ (p’∨q’)

• p→q ≡ p’∧q

decision tree model

used for assigning lower bounds to problems that be solved using only comparisons, that represents the problem as a binary tree where each node is a comparison of A[i] : A[j], and each node has an outgoing edge that is represents whether A[i] ≤ A[j] is true or if A[i] > A[j] is true. this works for:

• sorting arrays

• searching in an array

• deciding whether all elements in an array are the same or different

• finding the maximum or minimum element in an array

intuitively, what is the lower bound for the decision tree model

Ω(log(# of possible outputs))

what is the lower bound for sorting an array of n numbers, as seen by the decision tree model

Ω(nlogn)

how to read big-Oh and big-Omega in plain english

• an algorithm being O(f(n)) means the algorithm takes no more than f(n) time

• an algorithm being Ω(f(n)) means the algorithm takes no less than f(n) time

NP Problems: HAM-CYCLE

• problem: does this graph contain a hamiltonian cycle?

• input: an undirected graph

• certificate/solution: a list of vertices

• verification algorithm:

  • checks that the size of the solution is equal to n

  • checks that there are no duplicate vertices in the solution

  • checks that each vertex in the solution shares an edge its succeeding vertex, and that the last vertex in the solution share an edge with the first vertex

  • takes O(n²)

NP Problems: TSP - Travelling Salesman

• problem: does this graph contain a hamiltonian cycle with a weight no larger than k?

  • used for deliveries!

• input: a complete, directed, and weighted graph and an integer k

• certificate/solution: a list of vertices

• verification algorithm:

  • checks that the size of the solution is equal to n

  • checks that there are no duplicate vertices in the solution

  • checks that each vertex in the solution shares an edge with its succeeding vertex, and that the last vertex shares an edge with the first vertex

  • checks that the sum of each edge implied by the order of vertices in the solution, including the one between the first and last vertex, are less than or equal to k

  • takes O(n²)

NP Problems: SUBSET-SUM

• problem: does this set contain a subset with a sum equal to t?

• input: a set of integers and an integer t

• certificate/solution: a set of integers

• verification algorithm:

  • checks that the solution is a subset of the input

  • checks that the sum of the solution is equal to t

  • takes O(n²)

NP Problems: CLIQUE

• problem: does this graph contain a clique of size k?

• input: an undirected graph and an integer k

• certificate/solution: a set of vertices

• verification algorithm:

  • checks that the solution is a subset of V

  • checks that the size of the solution is equal to k

  • checks that for every u,v ∈ solution where u ≠ v, the edge {u,v}∈E

  • takes O(n²)

NP Problems: INDEP-SET

• problem: does this set contain an independent set of k vertices?

• input: an undirected graph and an integer k

• certificate/solution: a set of vertices

• verification algorithm:

  • checks that the solution is a subset of V

  • checks that the size of the solution is equal to k

  • checks that for every u,v ∈ solution where u ≠ v, the edge {u,v}∉E

  • takes O(n²)

NP Problems: VERTEX-COVER

• problem: does this graph contain a vertex cover of size k?

• input: an undirected graph and an integer k

• certificate/solution: a set of vertices

• verification algorithm:

  • checks that the solution is a subset of V

  • checks that the size of the solution is equal to k

  • checks that for every edge {u,v}∈E, (u∨v)∈ solution

  • takes O(n²)

NP Problems: 3SAT

• problem: is this 3sat formula satisfiable?

• input: a 3sat formula

• certificate/solution: a list of truth assignments

• verification algorithm:

  • checks that the size of the solution is equal to n

  • checks that the execution of the formula with the solution’s assignments outputs true

  • takes polynomial time

NP-Problems: CIRCUIT-SAT

• problem: is it possible to assign a truth value to each unknown variable in this circuit such that the output is true?

• input: a directed acyclic graph where vertices are gates of type AND, OR, NOT, input, or output. input gates have indegree 0 and either have the value True, False, or unknown for an unknown variable. AND and OR gates have indegree 2 and NOT gates have indegree 1. the output gate has outdegree 0.

• certificate/solution: a list of truth assignments

• verification algorithm:

  • checks that the size of the solution is equal to the number of unknown gates

  • checks that the output gate is equal to true when the solution’s assignments are used

  • takes polynomial time

CIRCUIT-SAT’s NP Complete proof logic

for all L∈NP, L ≤_p CIRCUIT-SAT because the inputs of CIRCUIT-SAT are representations of computer logic, and all L∈NP can be represented by computer logic

Reductions: INDEP-SET ≤_p CLIQUE

• the f() function takes advantage of the fact that a graph has an independent set of size k if and only if it has a clique of size k in its inverse.

• f((G,k)) = (G’,k) for CLIQUE to compute

• f() is O(n²)

Reductions: CLIQUE ≤_p VERTEX-COVER

• the f() function takes advantage of the fact that graph has a clique of size k if and only if it has a vertex cover of size n-k in its inverse

• f((G,k)) = (G’, n-k) for VERTEX-COVER to compute

• f() is O(n²)

Reductions: 3SAT ≤_p INDEP-SET

• the f function creates a graph of the 3sat formula where each literal is a vertex and each clause is a 3-clique of its literals, with additional edges between opposing literals

• f(θ) = (G, m) for INDEP-SET to compute (where m is the number of clauses in θ)

• f() is O(m²)

Reductions: CIRCUIT-SAT ≤_p 3SAT

• the f function transforms each gate into a clause, including inputs and outputs, using boolean logic transformations

• f(G) = θ for 3SAT to compute

• takes O(|gates|)

why doesn’t reducing CIRCUIT-SAT to another NP problem disprove that it’s NP Complete?

the proof for CIRCUIT-SAT works for ANY NP problem, and reducing L to L’ doesn’t prove that L isn’t less complex than L’

Reductions Order

CIRCUIT-SAT ≤_p 3SAT ≤_p INDEP-SAT ≤_p CLIQUE ≤_p VERTEX-COVER

Greedy Algorithms: Making Change

• problem: finds the smallest combination of a set of coins to create a given amount of money

• running time: O(number of counts in set)

• input format: a number x

• output format: a list containing the number of each coin needed to create x

• trace: starts by adding as much of the largest coin as possible, then the second-largest, and so on until x is achieved

  • this does not work with all sets of coins

Greedy Algorithms: Indiscrete Knapsack

• problem: find a way to pack a knapsack with the most amount of value possible without going over a certain weight, and the items can be split

• running time: O(nlogn)

• input format: a list of n items, each with a value v_i and a weight w_i, as well as a maximum weight W

• output format: a list with each entry corresponding to an item in the collection, where each value is 0-1 for how much of the item should be brought for the maximum value

• trace: starts by calculating the ratio of value to weight for each item, then sorting the list and taking all of the item with the highest ratio and then the next, and so on until there is an item that can only be partially brought and every other item must be left behind

Greedy Algorithms: Kruskal

• problem: finds the minimum spanning tree of a graph

• running time: O(mlogn)

• input format: an undirected, connected, and weighted graph

• output format: a list of edges in the minimum spanning tree

• trace: starts by sorting all of the edges by weight, then puts each vertex into its own set, and combines sets by the smallest edge, taking care that if an edge has both endpoints in the same set, it is not added to the list to prevent the creation of a cycle in the tree

Greedy Algorithms: Prim-Jarnik

• problem: finds a minimum spanning tree for a graph

• running time: O(mlogn)

• input format: an undirected, connected, and weighted graph

• output format: a list of edges in the minimum spanning tree

• trace: starts by choosing an arbitrary vertex r to start, then adds it into a set of all of the vertices in the minimum spanning tree, A. then for each vertex y, the algorithm establishes 3 values; minweight(y) which contains the weight of the smallest edge connecting y to A and is infinity if there isn’t, closest(y) which stores the vertex on the other end of the minweight(y) edge or nil if there is none, and a boolean value to check if y is in A or not. for each y where edge (r,y) exists, these values are properly set. then a minheap Q is created to store all vertices not in the minimum spanning tree, using minweight(y) as the key. then the top vertex of Q is systematically removed and added to A, storing its edge in the return set and updating its neighbouring vertices’ minweight() and closest()

Dynamic Algorithms: Longest Common Subsequence

• problem: finds the largest common subsequence for two sequences

• running time: O(mn)

• input format: two subsequences, one of length n and the other m

• output format: a matrix A of size n×m, where A[i,j] stores the length of the longest common subsequence between sequence one of up to its ith element and sequence two of up to its jth element

• trace: starts by creating the matrix, then setting every A[i,j] where i or j = 0 as 0. then iterates through every j for each i

  • if the ith element and the jth element are the same, that entry is equal to A[i-1, j-1] + 1 as that element is in the subsequence for certain

  • if the ith element and the jth element are not the same, that entry will be the maximum of either A[i-1, j] or A[i, j-1], depending on whether the element is in the subsequence

• backtracking for the solution: start by considering A[n, m], continue until the current entry being considered is 0

  • if A[n-1,m] or A[n, m-1] = A[n, m], move to consider the equal entry

  • otherwise, add the nth element of the first sequence to the end of the subsequence and move to consider A[n,-1, m-1]

Dynamic Algorithms: Matrix Chain Multiplication

• problem: finds the cheapest way to multiply a list of 2D matrices by finding where to chunk up the list

• running time: O(n³)

• input format: a list of matrices x₁, x₂, …, x_n where each matrix has the dimensions p_i-1×p_i

• output format: a matrix M of size n×n, where M[i,j] stores the cheapest way to multiply the ith to jth matrices in the list as well as the latest split point k

• trace: starts by creating the matrix and setting the cost and k of every M[i,j] where i=j as 0, because there is no multiplication needed for one matrix. then, going through every position where j=i+1, and then j=i+2, and so on, always stopping when j is larger than n, the algorithm sets the cost to be the minimum of, for every i ≤ k < j, M[i,k] + M[k+1, j] + (p_i-1*p_k*p_j), then sets the k as the one that provided the minimum

• backtracking for the solution: start by considering the k at M[i,n]. the split point will be after the x_k matrix in the list, and you must move on to consider entries at M[i,k] and M[k+1, j]. stop each branch when k=0

Dynamic Algorithms: Discrete Knapsack

• problem: find a way to pack a knapsack with the most amount of value possible without going over a certain weight, and the items cannot be split

• running time: O(nW)

• input format: a list of n items, each with a value v_i and a weight w_i, as well as a maximum weight W

• output format: a matrix K of size n×W, where K[i,j] stores the maximum value for up to the ith item for a maximum weight of j

• trace: starts by creating the matrix and setting all entries with no items (i=0) or no weight (j=0) as 0. then, for iterating through every j for each i, the algorithm checks if w_i>j. if it is, the entry is set to K[i-1, j], because that item is not brought at all. otherwise, the entry is set to the maximum of either K[i-1, j] and K[i-1, j-w_i] + v_i

• backtracking for the solution: start by considering K[n,W]. stop when the entry being considered has a value of 0. for each K[i,j]

  • if K[i-1, j] is equal, move to consider K[i-1, j] and set the ith element to 0

  • if K[i-1, j-w_i] is equal to K[i,j] - v_i, move to consider K[i-1, j-w_i], and set the ith element to 1

  • both may be true, either provides a valid solution

Dynamic Algorithms: Floyd-Marshall

• problem: finds the length of the shortest path between all pairs of vertices

• running time: O(n³)

• input format: a weighted and directed graph with ordered vertices

• output format: a matrix F of size n×n×n, where F[i,j,k] stores the length of the shortest path between i and j that allows the visitation of vertices up to and including k

• trace: starts by creating the matrix and setting every F[i,j,0] where i=j to be 0, as no travel is needed. every other F[i,j,0] is set to infinity unless (i,j)∈E, in which case the entry is the weight of that edge. then, iterating through j for every i, for each k, F[i,j,k] is set to the minimum of either F[i,j, k-1], where the kth vertex doesn’t help, or F[i,k, k-1] + F[k,j, k-1], where it does

• backtracking for the solution: say we are trying to find the shortest path from i to j. start by considering F[i,j,n], and add i and j to the set of vertices in the path. for each F[i,j,k], if F[i,j, k-1] is the same, move to consider F[i,j, k-1], otherwise add k to the set and move to consider F[i,k, k-1] and F[k,j, k-1]. continue until k=0

the difference between the reverse of a graph and the complement of a graph

the reverse of a graph G^R reverses the directions of the edges in a directed graph, while the complement of a graph G’ only has edges that connect vertices that weren’t connected in the undirected graph

what makes an algorithm greedy and what does it need to be correct

the algorithm makes decisions for a solution based off of what looks best in the moment. to be correct, locally optimal in the problem must also mean globally optimal

graph conventions (3)

• there are n-1 edges in a tree of n vertices

• in an undirected graph, m ≤ (n(n-1))/2

  • in an undirected graph, logm is O(logn)

• in a connected graph, n-1 ≤ m

spanning tree

a subgraph of a given graph that contains all of its vertices while also being a tree

minimum spanning tree

a spanning tree with the smallest combined weight of edges possible

fundamental lemma of minimum spanning trees

for an undirected, connected, and weighted graph, when the vertices are split into two groups, the smallest edge connecting the two groups must be a part of the graph’s minimum spanning tree

union-find sequence

a sequence of n-1 union operations and m find operations, where union combines two sets and find(x) finds the name of x’s set.

• when sets are stored as a doubly linked list, having the head as the set name, the next pointer pointing at the next node, and the back pointer pointing to the head, union takes O(p) where p is the length of the smaller set and find(x) takes O(1). with this arrangement, union-find takes O(m+nlogn)

why is it important to write deg(v) when applicable

the handshaking lemme may allow the runtime to be O(m) rather than O(nm)

handshaking lemma

∑_v∈V deg(v) = 2m, ∑_v∈V 1+deg(v) = n + 2m

fundamental difference between kruskal and prim-jarnik approaches

Kruskal is edge focused, adding edges to the MST when they are the smallest available, while Prim-Jarnik is vertex-focused, adding edges to the MST when a vertex has the smallest weight between it and the MST set. They still have the same runtime

what makes an algorithm dynamic and what does it need to be correct

the algorithm is recursive and divides problems into subproblems, but unlike divide & conquer, these subproblems are not of equal size. dynamic problems need optimal substructure to be correct

optimal substructure

when the subproblems of a problem have no overlap, and the combined optimal solutions for the subproblems is the optimal solution for the main problem

how to design a dynamic algorithm

1. consider how the solution might change if the input was a little bit smaller, either with one less element or split in the middle somewhere optimal

2. consider the different options the algorithm might take when increasing the size of a subproblem

3. consider the base cases of the algorithm

4. build the recurrence bottom-up

why can’t the longest common subsequence be used to find palindromes

palindromes are strings or consecutive sequences, and LCS only finds inconsecutive subsequences, not consecutive substrings

Sorting Algorithm: Insertion Sort

• running time: O(n²)

• input format: an array A of n integers

• output format: a sorted A

• trace: start at A[1]. at A[i], if A[i] < A[i-1], then the elements swap positions, then the new A[i-1] is compared to A[i-2], and if it’s smaller, it gets swapped again, and then with A[i-3] and so on until there is no swapping or i-j = 0. then i gets incremented. 1< i ≤n

Sorting Algorithms: Selection Sort

• running time: O(n²)

• input format: an array A of n integers

• output format: a sorted A

• trace: for 1≤ i<n. finds the smallest element in A[i…n] and swaps it with the element at A[i], then increments i.

Divide and Conquer Algrithms: Merge Sort

• problem: sorting an array

• running time: O(nlogn)

• input format: an array A of n integers

• output format: a sorted A

• trace: starts by splitting the list into half again and again until the list is just chunks of individual elements, then sorts and combines each pair of chunks until the full list is sorted

Divide and Conquer Algorithms: 1D Peak

• problem: finds a peak in a 1D array

• running time: O(logn)

• input format: a 1D array A of n integers

• output format: a peak in A

• trace: starts by checking if the middle of A is a peak. if not, the algorithm then checks which of its neighbours are larger, then iterates on that half of the list including the middle element, and continues iterating until a peak is found

Divide and Conquer Algorithms: 2D Peak

• problem: finds a peak in a 2D array

• running time: O(n)

• input format: a 2D array A of size n×n where n = 2^k+1 for k≥1

• output format: a peak in A

• trace: starts by checking if the largest element in the window frame of the array is a peak. if not, the algorithm iterates on the pane of the array where its largest neighbour is, including the borders of the pane. continues until a peak is found

formula for finding the middle element in a list of size n

⌊(n+1)/2⌋

what is a peak

an element in an array that is at least the same size as all of its neighbours

multiplying matrices A n×m and B m×p

• C[i,j] = A[i,0] * B[0,j] + A[i,1] * B[1,j] + … + A[i,m] * B[m,j]

• C is size n×p

• The cost for calculating C is n*m*p

• The cost for calculating C*D if D is p×s is n*p*s + n*m*p

Divide and Conquer Algorithms: Strassen

• problem: finds the result of multiplying two matrices cheaper than O(n³)

• running time: O(n^log7)

• input format: two matrices

• output format: the product of the two matrices

• trace: uses addition

Divide and Conquer Algorithms: Binary Search

• problem: finds an element in an array

• running time: O(logn)

• input format: a sorted array A of n integers

• output format: the position of the element

• trace: starts by checking the middle element, then iterating on either the higher or lower half depending on the desired element, until the desired element is found

Divide and Conquer Algorithms: BFPRT

• problem: finds an element in an array such that no more than 7/10 of the array are either greater or smaller than it

• running time: O(n)

• input format: an unsorted array A of n integers

• output format: an element that is close to the median

• trace: splits the list into n/5 groups of size 5 and computes their medians, then recurses on the list of n/5 medians just found to find the median of the medians, iterating again and again until the median of a list of size ≤5 is found

Divide and Conquer Algorithms: Selection

• problem: finds the kth smallest element in an array

• running time: O(n)

• input format: an unsorted array A of n integers and an integer k

• output format: the kth smallest element

• trace: starts by using BFPRT to find a near-median for the pivot, then splits the list into three groups; greater, equal, and less than the pivot

  • if k is larger than the number of elements in the equal and less than groups, the algorithm iterates on the greater than group with an adjusted k

  • if k is smaller than the number of elements in the less than group, the algorithm iterates on the less than group

  • otherwise the pivot is returned

  • if the list is of size 1, that element is returned

Graph Algorithms: Explore

• problem: finds all vertices reachable from one vertex

• running time: O(n+m) for an adjacency list, O(n²) for adjacency matrix - for directed and undirected

• input format: a graph and a vertex v

• output format: a visited/non-visited assignment to all vertices

• trace: starts with the pre-event for v, then marks v as visited. the algorithm then goes through all of v’s neighbours, checking if they are visited and iterating on them if not. once all of the neighbours of a vertex have been explored, the post-event for that vertex occurs

Graph Algorithms: Depth-First Search

• problem: finds all of the vertices in a graph in a specific order based on its edges

• running time: O(n+m) for adjacency list, O(n²) for adjacency matrix

• input format: a graph

• output format: depends on the use

• trace: goes through all of the vertices in the graph one by one and calls explore on the vertices that are not marked as visited

Graph Algorithms: Connected Components

• problem: finds the number of connected components in a graph

• running time: O(n+m) for adjacency list, O(n²) for adjacency matrix

• input format: an undirected graph

• output format: an assigned ccnumber to each vertex that corresponds to its connected component

• trace: calls DFS on the graph, but with the pre-event of explore assigning the ccnumber to the vertex. each time explore ends and DFS must look at the next vertex, the ccnumber is incremented

Graph Algorithms: Pre/Post Numbers

• problem: labels the order DFS visits and closes each vertex

• running time: O(n+m) for adjacency list, O(n²) for adjacency matrix

• input format: a graph

• output format: assigned pre and post numbers for each vertex

• trace: calls DFS on the graph, but during explore the pre event assigns the pre number to the vertex and the post number assigns the post number. pre and post share a clock that increments after every assignment

Graph Algorithms: Edge Labelling

• problem: labels the type of edge for each edge in a graph

• running time: O(n+m) for adjacency list, O(n²) for adjacency matrix

• input format: a graph

• output format: assigned types for each edge

• trace: calls DFS with pre and post numbers on the graph, assigning all pre and post numbers as ∞ initially, but when checking if a vertex v is visited (pre ≠ ∞) within explore(u), the edge is labelled

  • if pre(v) = ∞, the edge is a tree edge and explore(v) is called

  • if post(v)<pre(u), the edge is a cross edge

  • if pre(v)<pre(u), the edge is a back edge

  • if none of this above is true, the edge is a forward edge

Graph Algorithms: Topological Ordering

• problem: assigns topological ordering to a graph

• running time: O(n+m) for adjacency list, O(n²) for adjacency matrix

• input format: an acyclic, directed graph

• output format: a list of the graph’s vertices in topological order

• trace: calls DFS with pre and post numbers, then sorts the vertices by post number (with Bucket Sort O(n)). The reverse sorted order is a topological order of the vertices

topological ordering

an ordering assigned to vertices in an acyclical directed graph where the vertex in first position has an indegree of 0, and for every (u,v)∈E, u has a lower position than v

Graph Algorithms: Reversing

• problem: finds the reverse of a graph using adjacency list

• running time: O(n+m) for adjacency list, O(n²) for adjacency matrix

• input format: a directed graph

• output format: the reverse of the graph

• trace: runs through each vertex v in the adjacency list. for each u in v’s entry, v is placed in u’s entry

Graph Algorithms: Dijkstra

• problem: finds the length of the shortest path to all vertices from a specific vertex

• running time: O((m+n)logn) in class, O(nlogn +m) with a Fibonacci Heap

• input format: a weighted graph G and a vertex v

• output format: a list of the path lengths for each vertex from v

• trace: starts by assigning all vertices a distance of ∞, and assigning v a distance of 0. the algorithm then creates two arrays, an empty one called S and a min-heap Q containing all vertices with their distance from v as their key. while Q is non-empty, the algorithm removes the vertex u with the shortest distance, starting with the origin, and adds it to S. for each outgoing neighbour, if the distance of u plus the weight of the connecting edge is smaller than the neighbours current distance, the distance is reassigned

Graph Algorithms: Dijkstra’s Unique Shortest Path

• problem: finds if the shortest paths found by dijkstra are unique

• running time: O((m+n)logn) in class, O(nlogn +m) with a Fibonacci Heap

• input format: a weighted graph G and a vertex v

• output format: a list of whether the path for each vertex from v is unique

• trace: all vertices start with a true unique value. when checking the outgoing neighbours distance in dijkstra, the algorithm checks if the new distance to u including v is smaller, but also if its the same. if it’s smaller, diijkstra still replaces the distance, but also assigns to u v’s uniqueness value. if it’s the same, the algorithm assigns u a false unique value

Graph Algorithm: Dijkstra’s Shortest Path Contains Vertex

• problem: finds whether a specific vertex is within the shortest path between vertices a and b

• running time: O((m+n)logn) in class, O(nlogn +m) with a Fibonacci Heap

• input format: a weighted graph G and vertices a, b, and v

• output format: true or false

• trace: calls dijkstra once from a and again from v. if the distance between a and b in the first call is equal to the distance between a and v in the first call plus the distance between v and b in the second call, the algorithm returns true

adjacency matrix facts

• takes θ(n²) space

• takes O(1) to check if an edge exists

• takes θ(n) to find all neighbours of v in an undirected graph

• takes θ(n) to find all outgoing neighbours of v in a directed graph

• takes θ(n) to find all incoming neighbours of v in a directed graph

adjacency list facts

• takes θ(n + m) space

• takes O(1 + deg(v)) to check if an edge exists

• takes θ(1 + deg(v)) to find all neighbours of v in an undirected graph

• takes θ(1 + deg(v)) to find all outgoing neighbours of v in a directed graph

• takes θ(n + m) to find all incoming neighbours of v in a directed graph

types of edges and their pre/post order for u→v

• tree edge - direct child - pre(u) < pre(v) < post(v) < post(u)

• cross edge - connects to a different subtree, only occurs in directed graphs - pre(v) < post(v) < pre(u) < post(u)

• back edge - a cycling edge - pre(v) < pre(u) < post(u) < post(v)

• forward edge - a grandchild edge - pre(u) < pre(v) < post(v) < post(u)

why can’t a cyclic graph have topological ordering

in a cycle, there will always be an edge (u,v) where u has a higher position than v

Graph Algorithms: IsCyclic

• problem: finds if a graph is cyclic

• running time: O(n+m) for adjacency list, O(n²) for adjacency matrix

• input format: a graph

• output format: true or false

• trace: calls edge labelling, returns true if a back edge is found

fastest shortest path algorithm run time

O(mlog^2/3n)

barometer instruction

an instruction that is executed at least as often as any other instruction in the algorithm. the running time is in the order of the number of executions of the barometer instruction

big oh

an algorithm takes O(T(n)) time if there exists a strictly positive constant c such that for all inputs the algorithm takes at most c*T(n) time for any input of size n. a function in O(1) can also be O(n²)

big theta

an algorithm takes θ(T(n)) time if there exists two strictly positive constants c₁ and c₂ such that for all inputs the algorithm never takes more than c₁*T(n) time and never less than c₂*T(n) time for any input of size n. a function is θ(T(n)) if it is both O(T(n)) and Ω(T(n))

big omega

an algorithm takes Ω(T(n)) time if there exists a strictly positive constant c such that for all inputs the algorithm takes no less than c*T(n) time for any input of size n. if f(n) is Ω(g(n)), then g(n) is O(f(n))

Data Structure Complexities: Singly-linked List

• insertion at head: O(1)

• insertion otherwise: O(n)

• deletion at head: O(1)

• deletion otherwise: O(n)

• search: O(n)

• find min/max: O(n)

Data Structure Complexities: Doubly-linked List

• insertion at head or tail: O(1)

• insertion otherwise: O(n)

• deletion at head or tail: O(1)

• deletion otherwise: O(n)

• search: O(n)

• find min/max: O(n)

Data Structure Complexities: Dynamic 1D Array

• insertion at tail: O(n)

• insertion otherwise: O(n)

• deletion at tail: O(n)

• deletion otherwise: O(n)

• search: O(n)

• find min/max: O(n)

• access element by index: O(1)

Data Structure Complexities: Min/Max Heap

• insertion: O(logn)

• deletion: O(logn)

• search: O(n)

• find min/max (respective heap): O(1)

• find min/max (non-respective heap): O(n)

• build: O(n)