Is the array with values {23, 17, 14, 6, 13, 10, 1, 5, 7, 12} a max-heap? Illustrate the operation of Heap Sort on array A = {5, 13, 2, 25, 7, 17, 20, 8, 4}. Show that the second smallest of N elements can be found with N + ceil(log N) - 2 comparisons in the worst case.

Discuss about greedy choice property and optimal substructure. Prove that the fractional knapsack problem has the greedy-choice property.

Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is  {5, 10, 3, 12, 5, 50, 6}. Which is a more efficient way to determine the optimal number of multiplications in a matrix-chain multiplication problem, enumerating all the ways of parenthesizing the product and computing the number of multiplications for each, or running Recursive Matrix Chain? Justify your answer.

Why do we need RAM machine? Justify the need of back tracking.

What do you mean by boundary conditions? Solve the recurrence relation T(n) = 7T(n/2) + O(n²) using Master Theorem.

What happens if you run sequential search on already sorted data? You have a file of 1 million entries that is already 99% sorted. Only a few recent entries at the very end are not sorted. Which algorithm should you use and why?

What is the running time of Quick Sort when all elements of the array have the same value? How would you modify Quick Sort to sort into non-increasing order?

Compute the edit distance between the strings "KITTEN" and "SITTING" using dynamic programming approach.

Trace the concept of backtracking to solve the subset sum problem through the set {3, 4, 5, 6} to find a sum of 9.

Find an integer X that leaves remainders 1, 2, 3 when divided by 9, 8, 7, respectively.

Show that the problem of determining the satisfiability of boolean formulas in disjunctive normal form is polynomial-time solvable.

What do you mean by a randomized primality test? Discuss about vertex cover problem.