This does not need to be handed in.
Analyze bubble sort, as defined in Wikipedia; this is not a great algorithm, as Obama has said.
Show that multiplying two \(nxn\) matrices can be accomplished in \(O(n^3)\) steps.
Consider Horner’s
method for evaluating polynomials. Derive the stated complexities in the
article.
Code a bottom up version of merge sort
Suppose you have a linked list of say \(10\) nodes, how would you add/insert data into a new node at position \(5\) say?. To be concrete you can use this linked list. Your method should only assume you have access to header; that is, it should start from the header.
What would the complexity be for a merge sort where you did a \((1/3, 2/3)\) split?
Use the Master theorem to analyze Karatsuba’s multiplication algorithm.
In simple uniform hashing, with \(n\) keys and an array of length \(m\), what is the expected number of collisions? Hint: consider the indicator random variable \(X_{ij} = 1\) if the keys \(k_i\) and \(k_j\) collide, then bust through it by the power of linearity of expectation.
Code the BFS algorithm to generated the predecessor subgraph.
Is a path in a minimum weight spanning tree, also a minimum weight path?
What happens if I try to use Prim’s algorithm in the case where the edges are directed?
Let \(e_1, \ldots, e_n\) are the edges of a minimum weight path between two vertices \(s\) and \(t\), in a directed and nonegatively weighted graph. Suppose I relax the edges, starting from \(e_n\) and going back to \(e_1\). Is it possible that \(d.t \not = \delta(s,t)\).
Use memoization in a top-down coding of the Fibonacci sequence
How would you implement a ternary heap?
Describe in detail, how one deletes a node from a linked list.
What is:
Consider a finite set of integers \(S\) of size \(n\) Let \(z\) be a given integer.
Consider Dijkstra’s algorithm applied to a graph \(G = (V, E, w)\). Let \(S\) be the initial set that is set to be empty and eventually should be all of \(V\). Show that when we decide to add a node \(v\) to the set \(S\), at this instance, we must have that \(v\) is adjacent to \(S\).
Manually carry out Dijkstra’s algorithm in concrete example.
Consider the case of simple uniform hashing, with a hash function \(h\) mapping into the \(m\) slots of a hash table \(T\). On average, how many keys do I need, before every slot of the hash table is filled. Hint: Let \(W_i\) be the number of keys that are needed, after \(i-1\) slots have been filled; notice that \(W_1=1\).
Consider a hash function \(h\) with \(m\) slot and a hash table \(T[0, \ldots, m-1]\) that resolves collisions by chaining. Suppose that we have random keys \(K_1, \ldots, K_n\), and we do not have uniform hashing, but instead have \(h(K_1), \ldots, h(K_n)\) are iid random variables such that \(\mathbb{P}(h(K_1)=i) = p_i\). For each fixed key \(k\), find the average-case time of resolving an unsuccessful search.
Use the Master theorem to get the complexity of \(T\) where, \(T(n) = 7T(n/2) + \Theta(n^2)\).
Let \(A\) be an ordered array of integers of size \(n\). Write pseudocode for determining for an integer \(k\) in the array, that does better than \(O(n)\).
What is merge sort? Use the Master theorem to get the complexity of merge sort.
Give a simple example on four vertices to show that you really might need every relaxation performed by the Bellman-Ford algorithm.
Version: 08 November 2026