Question 1 (25 points)
Prove by induction that xn < 4 for all n ≥ 1.
If submitting a text file, use standard mathematical notation in writing your answer. For example, n2+1
would be written in the p1.txt file as n^(2+1).
Question 2 (25 points)
Analyze the worst-case time complexity of the following pseudocode of a mystery algorithm, which calls
another mystery method. Show your work.
Algorithm 1: Mystery1(W) //W is a matrix of size n × n
while m < n − 1 do
D(2m) Mystery2(D(m), D(m))
Algorithm 2: Mystery2(A, B) //A and B are matrices of size n × n
C new n × n matrix
for i 1 to n do
for j 1 to n do
for k 1 to n do
Ci;j min(Ci;j; Ai;k + Bk;j)
Question 3 (25 points)
(a) (13 points) Given a pointer, ptr, to a node in a link of nodes that is not the first or last node,
implement an algorithm (void deleteNode(Node<T> * ptr)) to delete the node in O(1). You
cannot create additional pointers. The Node class is described in Chapter 4.1.1 of your textbook.
(b) (12 points) Implement an algorithm (void deduplicate(Node<T> * headPtr)) to remove dupli
cate entries from a link of nodes that has runtime no worse than O(n2). The pointer headPtr points
to the first node in the link.
Question 4 (25 points)
A staircase with n steps can be ascended either one, two, or three steps at a time. Using recursion,
implement an algorithm (int stairs(int n)) to count how many possible ways the stairs can be