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:


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).


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