Best代写-最专业靠谱代写IT | CS | 留学生作业 | 编程代写Java | Python |C/C++ | PHP | Matlab | Assignment Project Homework代写

算法代写|ECE 2574 Midterm

算法代写|ECE 2574 Midterm


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
D(1) W
m 1
while m < n − 1 do
D(2m) Mystery2(D(m), D(m))
m 2m
return D(n)

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
Ci;j 1
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