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 INORDER- TREE-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.
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 INORDER- TREE-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.
Related questions
Question
Please answer all questions in detail and with pseudo codes.
Transcribed Image Text: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 INORDER-
TREE-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.
Problem 4. Determine, citing valid reasons, why memoization fails to improve the MERGE-
SORT's time complexity.
Problem 5. Write a dynamic programming based version of the factorial function and
prove its time complexity.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 4 steps
