Chapter 4 Decrease and Conquer

Question 1

What is Topological Sorting

Question 2

Outline an algorithm to print a topological sort of a digraph or detect that the graph has a cycle. What will be the time and space complexity of your algorithm?

Question 3

Consider the partition problem: Given n positive integers, partition them into
two disjoint subsets with the same sum of their elements. (Of course, the problem may not have a solution.) Design an exhaustive-search algorithm for this problem. You do not have to write pseudocode

Question 4

Discuss Khans Algorithm

Question 5

Write pseudocode for the insertion sort algorithm. Also, discuss the time compleixty.

Question 6

write pseudocode for recursive binary search tree algorithm. Discuss the time complexity

Question 7

write an algorithm to compute the product of two integers (russian peasant multiplication). Discuss the time complexity.

Question 8

write psuedocodee for euclids algorithm. Discuss the time complexity

Question 9

write pseudocode to find the kth smallest element in a kist of n numbers. Discuss the time complexity.

Question 10

write pseudocode for Lomutos partitioning algorithm. Disucss the time complexity

Question 11

write pseudocode for the quickselct algorithm. Discuss the time complexity.