Pseudo Coding Non Recursive Procedure Computer Algorithm Solved Practice

Homework Assignment
Computer Algorithms I
Problem 1. Construct a non-recursive procedure capable of reversing a single linked list
of n elements, which runs in O(n) time. Can the same be achieved in Ω(n) time? If so,
construct it.
Problem 2. Using the procedure TREE-SUCCESSOR and TREE-MINIMUM, write a
function F(x), where x is a node in a binary search tree, to produce the output that INORDERTREE-WALK function would produce. Determine the upper bound running time complexity
of F(x) and prove its correctness.
Problem 3. Let n be an integer. Write dynamic programming algorithm which determines
in how many ways, with repetitions, can n be written as the sum of 1,2,4 and prove its
time complexity. For what integer values k, where k is a function of n, ie. k(n), will this
algorithm’s time complexity be exponential?
Problem 4. Determine, citing valid reasons, why memoization fails to improve the MERGESORT’s time complexity.
Problem 5. Write a dynamic programming based version of the factorial function and
prove its time complexity.