CLRS Chapter 2 Solutions

Solutions to Cormen Chapter 2. Without further ado let’s get to business.

2.1.1 Using figure 2.4 as a model, illustrate the operations of Insertion-Sort on the array A = [31, 41, 59, 26, 41, 58]

Well you can do it by yourself.

2.1.2 Rewrite the Insertion-Sort procedure to sort into nonincreasing instead of nondecreasing order.

This is straightforward.  All needed to be done is to reverse the condition at the starting of the while loop.

for j = 2 to A.length
	key = A[j]
	i = j - 1
	while i > 0 and A[i] < key    //note here we replaced A[i] > key with A[i] < key
		A[i + 1] = A[i]
		i = i - 1
A[i + 1] = key

 

2.1.3 Consider the searching problem:

Input: A sequence of n numbers A = [a1, a2, a3……an] and a value v .

Output: And index i such that v = A[i] or a special value NIL if v is not found in A.

Write the pseudocode for linear search, which scans through the sequence, looking for v. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.

Its a simple linear search the pseudocode is simple too:

SEARCH(A, v):
  for i = 1 to A.length
      if A[i] == v
          return i
  return NIL

Now comes the part of defining the loop invariant. This I defined to be like “At the start of each iteration of the for loop, the subarray A[1…..i-1] consists of elements that are different than v“.

Now comes the part where we verify the correctness with 3 conditions.

Initialization: At the beginning, i.e. before the firs iteration the subarray is simply empty, this becomes the trivial.

Maintenance: For every step we check A[i] against v. We have already assumed that A[1…..i-1] does not contain v. So if we find v at A[i] we return it and the loops terminates with the procedure itself.

Termination: Loop terminates if i > A.lenghth which signifies the checking of the complete array. In this case we simple return NIL. The other condition in which loop ends is by the ending of the procedure itself when it returns the value of i in case we get A[i] = v.

 

2.1.4 Consider the problem of adding two n-bit binary integers, stored in two n-element arrays A and B. The sum of the two integers should be stored in binary form in an (n+1) bit element array C. State the problem formally and write pseudocode for adding the two integers.

I am not going to state the problem formally as we already understand it properly. Here is the psuedocode:

AddNbitArrays(A, B)
	C =  newArray integer(A.length)

	carry = 0
	for i = 1 to A.length
		C[i] = (A[i] + B[i] + carry) % 2
		carry = (A[i] + B[i] + carry) / 2
	C[i] = carry
	return C
Advertisements

CLRS Chapter 1 Solutions

So here we begin the solutions for CLRS. Problem sets of chapter 1 are particularly “not so technical”. So we are going to cover these here in a single entry. Most of the questions of these problem sets are kind of an open discussion geared towards developing an understanding of the subject matter. So here we go!

1.1.1 Give a real-world example that requires sorting or a real-world example that requires computing a convex hull.

Sorting, well this is trivial. The contact book in your phone needs sorting and so does any listable information collection viz. list of flights or trains on the time table, price sorting on e-commerce websites etc. etc.

Convex hull in its simples of sense can be defined as the the set of point, a line drawn connecting them in a convex polygonic way, contains all of the given points inside it. Here is what it looks like:

258px-ConvexHull.svg

Now talking of applications of this thing, image processing (in determination of boundary of objects in image).

 

 

1.1.2 Other than speed, what other measures of efficiency might one use in a real-world setting?

Memory, network usage (GIT uses less network bits than Filezilla), database accesses etc.

 

1.1.3 Select a data structure that you have seen previously, and discuss its strengths and limitations.

(figure out for yourself. Its too open)

 

1.1.4 How are the shortest-path and traveling-salesman problems given above similar? How are they different?

Similar: Each of them walks a path in a graph and tries to find the shortest possible route.

Different: Shortest path tens to find the shortest path between exactly 2 points, whereas TSP finding a closed loop involving many points.

 

1.1.5 Come up with a real-world problem in which only the best solution will do. Then come up with one in which a solution that is “approximately” the best is good enough.

Sorting of a list (only the best solution will do, nearly sorted is not acceptable)

Finding a shortest path in a city map ( approximately will do, a couple of meters don’t matter here)

 

1.2.1 Give an example of an application that requires algorithmic content at the application level, and discuss the function of the algorithms involved.

Hail Google! The search results and also the google Maps. In search pagerank algorithm dictates the order of search results. Maps do work with the routing needs of the user.

 

1.2.2 Suppose we are comparing implementations of insetion sort and merge sort on the same machine. For inputs of size, insertion sort runs in 8n2 steps, while merge sort runs in 64n.lg(n) steps. For which values of n does insertion sort beat merge sort?

Solving the simple equation :

64n.lg(n) = 8n2

for n yields n = 43 as the result. Where 64n.lg(n) = 14933.0806049 and 8n2 = 14792

1.2.3 What is the smallest value of n  such that an algorithm whose running time is 100n2 runs faster than an algorithm whose running time is 2on the same machine?

At n > 15 first algo is faster. (Just solve the equation like in previous problem)

1.1 For each function f(n) and time t in the following table, determine the largest size n of a problem that can be solved in time t, assuming that the algorithm to solve the problem takes f(n) microseconds.

Solve f(n) = Time * (appropriate conversion units) for n, in each cell of the table you would need a calculator and you would arrive at more or less at following result (click to enlarge).

Capture

So this is for the Chapter 1. Chapter 2 solutions are being cooked. Discussions are welcome!