Algorithms Answers

Write and apply the partition procedure of Quick Sort algorithm to the following array. Show all the intermediate steps. 25 27 15 35 13 50 33 14 40 27

Solve the following recurrence relation using recurrence tree and iteration methods

T(n) = T(n-1) + n

Briefly describe Insertion sort algorithm using the following array of numbers. 10, 5, 15, 3, 12 ii Write an algorithm in pseudocode for the Insertion sort. (15 marks ) (10 marks) Analysing the following algorithm given in pseudocode. After executing the program what will be printed on the screen, if n-5 and elements of the array A is initialized to (10,5,15, 3, 12), Write the steps to show how you decide your answer. I/ lambda 10 an array of n Funct (A, n) for 1=n-1 to 1 for 1 to i if A1 temp Al A(j) = A(j + 1) Aff + 11 = temp for 1 - 1ton print Alil A[j+1] elements -A(1,..n) (15 marks) According to the algorithm given in the above question 1.iii, how many times will the comparison statement be executed.

consider the simple problem of placing four coloured balls:red,blue,green and white in 15 boxes.what are the numbers of distinct ways in which balls can be placed in these boxes,if each box can hold only one ball ?also write the generalized formula for this numerical result.

Consider the following preemptive variant of the Load Balancing problem: There are m identical machines, and n jobs with processing times t1, t2,...., tn respectively. Each machine can process at most one job at a time. Each job can run on more than one machines but must run on at most one machine at any time. Let T = max { max _(1<=j<=n) t_j , 1/ m "summation" _(1<=j<=n) t_j }

Implement Binary Search Tree class with insertion, deletion, preorder, postorder, and inorder traversal functions in javascode.

 Consider the following instance of load balancing problem. There are m machines and n=2m+1 jobs, 3 jobs are of length m and 2 jobs of m+i for each 1<= i <= m-1. Show that on this instance the list-scheduling algorithm with the LPT rule achieves the approximation ratio 4/3-1/3m.  

. Write an algorithm/pseudocode for a movie rental company that wants to screen their customers from 18years and above. The system should be able to deny access to customers that appear below 

The general greedy method for the Knapsack problem first sorts the objects by some rule, and then puts the items into the knapsack according to this order subject to the capacity constraint. Consider the following three ordering rules: (a) Sort by size in increasing order. (b) Sort by profit in decreasing order. (c) Sort by profit/size in decreasing order. For each of the three above rules, give an instance to show that the approximation ratio of the greedy method using such rule can be arbitrarily large.