comp 202 EXAM

What is the correct asymptotic relationship between 2^n and n^100? and what are the steps to answering

2^n = Ω(n^100)

Ω A grows faster than or equal to B

O A grows slower than or equal to B

Θ A grows at the same rate as B

Using the Master Theorem, what is the solution to T(n) = 4T(n/2) + 7n^(8/5)? and how?

Θ(n^2)

1. aT(n/b)

2. f(n) = 7n^(8/5) = n^8/5

3. n^[logb (​a)]

4. compare n^[logb (​a)] with f(n) biggest wins

Using the Master Theorem, what is the solution to T(n) = 2T(n/2) + n?

Θ(n log n)

if f(n) and logb (a) are the same it becomes xlogn x = logb (a)

How many subproblems does Strassen’s matrix multiplication reduce n×n multiplication into?

7

What is the expected number of rolls until a fair 6-sided die shows a 6?

6

If a ball numbered 1–100 is chosen uniformly at random, what is the probability that 7 ≤ n ≤ 16?

1/10

What is the expected running time of randomized Quicksort?

O(n log n)

What property must a max heap satisfy?

Every parent node is greater than or equal to its children

time complexity merge sort

nlogn

Heap week 4

Time complexity of insertItem

logn

Heap week 4

Time complexity of remove max

logn

Time complexity of heap sort

nlogn

Time complexity of counting sort

O(n + k)

Time complexity of radix sort

O(d * n)

how does radix sort work

132 315 827 469 507 193 657 274

1. order the numbers by smallest digit first

2. 132 193 274 315 827 507 657 469

3. Then the next largest digits

expected length in a randomised quick sort

2 log4/3 n

Time complexity of the knapsack problem

O(nW )

Time complexity of repeating squares (fibonacci)

O(log n)

The time complexity of the fractional knapsack problem

O(nlog(n))

time complexity of interval scheduling

O(n log n)

What is does an undirect graph look like

What is a digraph?

A directed graph — a graph where all edges are directed.

What does it mean for two vertices to be adjacent?

2 vertices connected by an edge

What is an incident edge?

An edge connected to a specific vertex

Define degree, in-degree, and out-degree.

Degree deg(v) = number of edges incident to v. In-degree indeg(v) = number of incoming directed edges. Out-degree outdeg(v) = number of outgoing directed edges.

If G is undirected with m edges, what is the sum of all vertex degrees?

Sum of deg(v) = 2m.

If G is a directed graph with m edges, what do the in-degree and out-degree sums equal?

Sum of indeg(v) = Sum of outdeg(v) = m.

What is a simple graph?

A graph where there is at most one edge between any pair of vertices (and no self-loops).

Upper bound on edges in a simple undirected graph with n vertices?

m

Upper bound on edges in a simple directed graph with n vertices?

m

What is a walk in a graph?

What is a path?

A walk where every vertex visited is distinct.

What is a circuit?

What is a cycle?

What is a subgraph? What is a spanning subgraph?

A subgraph H of G has vertices and edges that are subsets of G's. A spanning subgraph contains all vertices of G but only some edges.

What is a connected graph

What is a forest? What is a tree?

A forest is a graph with no cycles. A tree is a connected forest (connected, acyclic graph).

What is a spanning tree?

Contains all vertices of the original graph

graph must be connected

graph must have no cycles

For an undirected graph with n vertices and m edges, what are the upper bounds for connected, tree, and forest?

Connected: m >= n-1. Tree: m = n-1. Forest: m

what does an adjacency list look like

Explain DFS

• Visit a neighbour

• Keep going deeper

• Backtrack when stuck

What is a weighted graph?

A graph where each edge e has a numerical weight w(e). Weights may represent distances, costs, etc.

Define the Single-Source Shortest Path (SSSP) problem.

Given a fixed source vertex v, find the minimum-weight path from v to every other vertex u in the graph.

A-B

A-C

A-D

What is the length/weight of a path P with edges e1 to ek?

w(P) = sum of w(ei) for i = 1 to k.

What is Dijkstra's algorithm and what is its key requirement?

A greedy algorithm for SSSP that performs a weighted BFS. Requirement: all edge weights must be non-negative.

Why can't Dijkstra's algorithm handle negative-weight edges?

Its greedy logic assumes once a vertex is settled its distance is final. Negative edges can provide shorter paths discovered later, violating this assumption.

What is the Bellman-Ford algorithm's time complexity?

O(|V| x |E|).

What is the All-Pairs Shortest Path (APSP) problem?

Find shortest-path distances between every pair of vertices in the graph, not just from a single source.

Time complexity APSP using Bellman-Ford

Time: O(|V|^2 x |E|) potentially O(|V|^4).

Time complexity Floyd-Warshall algorithm for APSP?

Solves APSP in O(n^3) using dynamic programming

what is a directed walk

what does an adjaceny matrix look like

Explain bfs

• Visit all immediate neighbours

• Then neighbours of those neighbours

• Continue outward

Time complexity of DFS and BFS

O( V + E) V = vertices, E = edges

Strongly connected digraph

A digraph in which every pair of distinct vertices can reach each other.

Directed cycle

It means you can start at a vertex, follow the arrows on the edges, and eventually return to the starting vertex without ever going against an arrow.

Acyclic digraph

A directed graph with no directed cycles.

Flow network

A directed graph where each edge has a non-negative integer capacity.

Capacity of an edge

The maximum amount of flow that can pass through an edge.

Source vertex in a flow network

The starting vertex s from which flow originates.

Sink vertex in a flow network

The ending vertex t where flow is collected.

Flow conservation

For every vertex except s and t, total inflow equals total outflow.

Maximum flow problem

Finding the greatest possible flow from source s to sink t in a flow network.

Forwards edge in a residual network

An edge with remaining unused capacity.

Complexity of finding an augmenting path

O(m).

Time complexity of Ford-Fulkerson networks

O(|f*|m).

Time complexity of Edmonds-Karp

O(nm^2).

Bipartite graph

a graph where the vertices can be split into two separate sets so that:

• every edge goes between the two sets

• no edge connects two vertices in the same set

Matching in a bipartite graph

each vertex can appear in at most one selected edge

2 vertices cannot share the same endpoint

Complexity of maximum bipartite matching using flow Ford-Fulkerson

O(nm) .

Meaning of |f*|

The value of a maximum flow.

Meaning of n in complexity analysis

The number of vertices in the graph.

Meaning of m in complexity analysis

The number of edges in the graph.

strassen algorithm time complexity

what is the formula for Strassen matrix T(n)

What is a symmetric encryption scheme?

An encryption scheme where the same secret key K is used by both sender and receiver for both encryption and decryption.

What is a substitution cipher?

A symmetric cipher where the secret key is a permutation π of the alphabet; each character x is replaced by y = π(x). Decryption uses the inverse: x = π⁻¹(y).

What is the Caesar cipher?

A substitution cipher where each character x is replaced by y = (x + k) mod n, where n is the alphabet size and k is the secret key. Julius Caesar used k = 3.

How can substitution ciphers be broken?

By frequency analysis

What is the one-time pad?

The most secure known symmetric cipher. Alice and Bob share a random bit string K as long as the message. Encryption: C = M ⊕ K. Decryption: M = C ⊕ K.

Why is the one-time pad secure?

The ciphertext C = M ⊕ K is computationally indistinguishable from a random bit string, provided K was chosen randomly.

What are the disadvantages of the one-time pad?

(1) Alice and Bob must share a very long key K. (2) The key can only be used once — reusing it breaks security.

What is the key distribution problem?

The challenge of securely distributing secret keys in symmetric encryption schemes.

What is a public-key cryptosystem?

A system with encryption function E (public) and decryption function D (private) satisfying: D(E(M)) = M

What is a one-way (trapdoor) function?

The encryption function E in a public-key system; knowledge of E gives no information about D. Anyone can encrypt, but only the holder of D can decrypt.

What is the RSA encryption scheme?

A public-key encryption method. Its security is based on the difficulty of factoring large numbers.

What are the RSA key generation steps? 4

Choose two large distinct primes p and q. Set n = p·q and (Euler's Totient)φ(n) = (p−1)(q−1). Choose e (a prime number) with 1 < e < φ(n) and gcd(e, φ(n)) = 1. Find d such that ed ≡ 1 (mod φ(n)). Public key: (e, n). Private key: d.

What is the RSA encryption formula?

C = M^e mod n, where M is the plaintext message, e and n are the public key.

What is the RSA decryption formula?

M = C^d mod n, where C is the ciphertext and d is the private key.

How are digital signatures created in RSA?

sender computes signature S = M^d mod n using his private key d. receiver verifies by checking M ≡ S^e (mod n) using Bob's public key e.

What makes RSA hard to break?

Breaking RSA requires computing φ(n) = (p−1)(q−1), which requires factoring n = p·q — a problem believed to be computationally infeasible for large n.

State Euclid's key theorem for the GCD algorithm.

If a ≥ b > 0, then gcd(a, b) = gcd(b, a mod b).

What is the time complexity of Euclid's algorithm?

O(log(max{a, b}))

time complexity of fast (repeated squaring) exponentiation?

O(log k)

What is the time complexity of RSA operations?

O(log n)

What is φ(n) (Euler's totient) in RSA?

For n = p·q (p, q distinct primes), φ(n) = (p−1)(q−1). It is used to choose the RSA keys e and d.

What is a decision problem?

A computational problem whose answer is either 'yes' or 'no'.

How can an optimization problem be converted to a decision problem?

Add a parameter k and ask whether the objective value is at most (or at least) k.

What is the complexity class P?

The set of all decision problems solvable in worst-case polynomial time.

What does 'polynomial time' mean for problem size?

complexity is O(n^k)