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!

Backing Up MySQL Databases on Ubuntu Server

Having your own server comes with a lot of maintenance considerations. It can be your worst nightmare to experience a disastrous server crash and damaging (or loosing!!!) your database. Prevention is better than cure. An easy prevention of such an unfortunate problem is to backup your databases regularly, on a rotational basis.

I have some ubuntu servers running on Amazon AWS. I am well aware of the high quality of the services provided by amazon. But I am just pretty obsessed with fault prevention and recovery. Backing up databases daily on rotational basis seems to be a rather good idea.

There are many ways to do that. You can employ a shell script or cronjob or some third party tool/utility. I preferred to use cronjob and mysqldump utility which ships with MySQL itself.

Cron is a software utility in Unix like (that means ALL Linuxes) operating Systems. Its a job scheduler, speaking crudely. Much like windows Task Scheduler. Now there is a lot to learn about cron. For the purpose of this article I will provide the steps I took to backup my databases.

First of all in the terminal lets open up “/etc/crontab” file with an editor of your choice (my choice is nano) with root privileges (this essentially means using “sudo” and all).

Now at the bottom of the file add following line:

0 13 * * * root mysqldump -u root -p database_name | gzip > /home/backup/database_`date +\%m-\%d-\%Y`.sql.gz

Here 0 13 * * * specifies the time when you want to take the backup. There are 5 terms , MINUTE HOUR DAY_OF_MONTH MONTH DAY_OF_WEEK. So our backup is created at 1 PM everyday, because we have not provided the values for other parameters.

root mysqldump -u root -p database_name is the command executed with root privileges. It invokes mysqldump utility and creates a SQL dump of the database whose name is provided.

Then using |gzip we pipe this sql file to gzip utility which compresses this file to gzip format.

Finally we are providing a location’s path to save this file by /home/backup/database_`date +\%m-\%d-\%Y`.sql.gz

After adding this line its required to restart the cron daemon. Following command will do this.

sudo /etc/init.d/cron restart

Although this process is applied and tested on my ubuntu server. Any linux distro will be having almost the same setup.

Connecting to Remote MySQL Hosts with HeidiSQL

Spending quite of hours after struggling with this. I finally found the correct method to connect to remote mysql hosts using an excellent GUI for mysql. I use HeidiSQL all the time for my local development and also the database maintenance on remote servers.

Lately  have been working with Amazon AWS. Their EC2 instances are totally awesome. Apart from little configuration problems I am lovin it.

So here are the quick steps to be followed.

  1. Use puttygen to convert your .pem file which you get from amazon server. It will provide you with a .ppk file. This ppk file is used by HeidiSQL for connecting to remote servers using SSH Tunnel.
  2. Now from Session Manager in HeidiSQL select MySQL (SSH Tunnel) for the network type.
  3. Always use Hostname/IP localhost or 127.0.0.1 irrespective of the name/IP of the remote host. We will come to this in the next step.
  4. Fill in your MySQL username and passwords.

Now in the SSH Tunnel Tab

  1. Browse for the location of the plink.
  2. Hostname/IP of your remote host this time.
  3. Port 22 will work in almost all cases, of course, if you have not tweaked (or messed?) the configuration in your remote host.
  4. Here in the username field fill in your SSH username. Mostly in case of EC2 ubuntu instances its “ubuntu” itself by default.
  5. You can safely leave the password field blank as in next step we will be using the ppk file (remember we generated it a while ago!) for authentication.
  6. TaDa! Done.

There might be some errors regarding connectivity and/or your configuration of the MySQL Server.

Most of the connectivity issues can be easily resolved by extending the plink.exe timeout. You can increse it easily from HeidiSQL Sesison Manager Settings right there on the SSH Tunnel Tab. Default value is 4 seconds. I found 10 seconds to be a fair deal as my connection gets crazy sometimes.

Another problem which may occur is the nasty error

reading initial communication packet, system error: 0

This error occurs mostly when MySQL drops the communication packet silently. There is a simple workaround for this.

You would need to login to your server via SSH and edit following file:

/etc/mysql/my.cnf”

Add following line:

bind_address = 0.0.0.0

This ensures that mysql responds to all the IPs.

 

Ciao!!