My favorite books on Algorithms and Data Structures

21, November 2010

We usually study algorithms and data structures during academic course. However, constant improvement on algorithms and data structures skills is required for every developer. It is a day to day activity. A strong foundation on algorithms/data structures can be achieved by reading different algorithm books and solving exercises. My favorite books on Algorithms, Data Structures are given below,

1.           Introduction To Design and Analysis Of Algorithms by Anany Levitin

My first book on learning algorithms. Very nice explanation of many algorithms and dividing chapters based on design strategy is unique feature of the book. Many of the exercises deal with programming puzzles and algorithms. Fun to read such a book, one must attempt all exercise problems. Write the algorithm on peace of paper after you read and visualize each algorithm when read.

2.           Introduction To Algorithms 3e by  Thomas H Cormen

My best reference on algorithms. A standard book used across many universities in the world. It takes atleast an year (few hours per week) to practice complete book along in-sync with the supplementary material on their website. Special for data structures. A nice book, write the algorithm or data structure on black board after you understood. One should attempt all problems.

3.           Algorithms by Dasgupta

A short and precise book on collection of algorithms. First few chapters will help in understanding the basics well. Later chapters are based on graph modeling and their algorithms. The book emphasize on graphs, dynamic programming, greedy strategy, and few more topics very well. Entire book is freely available online. For details click here. Attempt all exercise problems.

4.           The Algorithm Design Manual  by Steven S Skiena

A good collection of algorithmic problems on various categories. Other book by Skiena is Programming Challenges. A must work book for all computer/computing geeks. Contains many pointers to useful resources on the CD as well as on repository site. Selectively read topics, once you have understood various concepts of algorithm design and data structures.

5.           Robert Sedgewick (Algorithms in C++/Java)

Another standard reference and lucid material on many algorithms. Selective reading helped me in getting best results from the book. Their exclusive book on Algorithms (4e) is upcoming.

6.           Algorithms 4e by Sedgewick and Kevin.

Released early 2012. I have read the book, and it left excellent contentment in solving various algorithmic problems. The exercise problems on their website are interesting. Try them.

For above six references, it is strongly recommended to attempt the exercise problems. Just reading will be useless.

7.           Programming Pearls by Bentley

If you feel you understood algorithms usage well, it is the book to read. A must for every programmer and computer science geek.

8.           Data Structures and Algorithms in C++ by Mark Alen Weiss

Another best resource on data structures and algorithms. This book have collection of good problems, data structures, and C++ concepts.

9.           Computer Algorithms by Sara Baase

Another reference on algorithms. Selective reading will be useful, pseudo code in Java.

10.        Donald Knuth books (Volume 1 through Volume 4).

If you have enough time for research these books are for you. If you know well an algorithm, it is time to refer this book for in-depth study.

11.        How To Solve It By Computer by Dromey: A good collection of specific algorithms. Short book, a must read.

12.        Foundations of Algorithms by Richard Neapolitan.

I heard that it is good book. Looking for Indian version of the copy.

13.       Fundamentals Of Algorithmics by Brassard & Bratley

A nice book on fundamentals of algorithms. If you have time, read each chapter individually. The chapters are divided per design techniques. The book is special for few number theoretic algorithms. I am still reading it.

14.        Introduction to Algorithms: A Creative Approach by Udi Manber

A book written by former professor, and present part of a technological revolution company. It emphasizes the mathematical induction as primary approach in designing algorithms. One must read it. Exercises and hits to selected questions, are added bonus to the book. Unfortunately it is costly edition.

15.        Computer Algorithms by Horowitz

Another nice book on algorithms. Good collection of problems, and problem solving techniques.

Linear Diophantine Equation and a puzzle

November 7, 2010

Linear Diophantine Equation, what is it? Meanwhile read the question posted here and try for solution.

During college days I read one regional language novel. The author created one nice question between two characters of novel, it left a good fragrance on my mathematical interest.

[ The annotation from the novel is something like this,

The male character is in need of money for his parent cremation. He hesitates to beg at female character. On the fly, he phrases one puzzle and poses the same at female character. (The question by male character was also based on single LDE equation of two variables). She immediately cracks it. She evaluates the value of puzzle as one rupee and donates 499 bucks for cremation. Unfortunately, that is the kind of value talent has.

I believe right talent should be at right place ]

Given an equation with two variables, how to solve it? Or what are the conditions to solve it? How many solutions does it have? LDE is the answer. LDE deals with equations having integer solutions. Let us solve the puzzle posted in the following link,

http://math-puzzles-computing.blogspot.com/2010/05/workers-and-wages.html

Given that male (M) paid 7/-, female (F) 5/- and children (C) 1/- each. Total number of workers should be limited to 100, considering the capital letters as number of each group, we have

M + F + C = 100 ……… (Equation A)

Total worth of work should be limited to 250/-, i.e.

7M + 5F + C = 250 ……… (Equation B)

We have two equations with 3 unknowns, can we consolidate them to an LDE? Yes, eliminate one variable, we will have

7M + 5F + (100 – M – F) = 250

6M + 4F = 150 ……… (Equation C)

From Equation C, we have common factor, don’t take it out. Now, it is in LDE from. An LDE will have solutions when the GCD of variable’s coefficients is factor of constant on right side.

GCD(4, 6) = 2 which is factor of 150, so we have solutions to Equation C. But, how many?

Rearranging Equation C, will yield the following form

M = (150 – 4F) / 6 = 25 – 4/6F

M = 25 – 4/6F

Replacing F = 6t where t is intermediate variable will yield M value to,

M = 25 – 4t

and C value as,

C = 100 – 25 + 4t – 6t = 75 – 2t,

So finally,

M = 25 – 4t

F = 6t

C = 75 – 2t

We can have 13 different values of t, satisfying the Equations A and B.

We crack the puzzle.

Now crack it, “if two oranges and three apples cost six rupees, how many integral values can be the prices of orange and apple?”

Car Race Puzzle (Google)

20^th, October, 2010

Given 49 cars and 7 tracks of equal length. No two have the same speed. How to find the 25^th fastest car? At least how many races are needed? The puzzle posted here.

I am providing my initial thought on the puzzle. We are given 49 cars and 7 tracks. We can arrange them into 7 groups. Conduct first race among these 7 groups, we will have seven ordered sets.

For easy reference, let us name them from group A through group G. Further, in group A, let us name the best car as A1 and last car as A7. Similarly other groups. Now conduct one more race among the winners of all groups. At this point we needed 8 races to figure out groups order along with order in each group. We can represent them in the following matrix form.

For simplicity, assume that the result of 8^th race is A1 through G1. We can arrange them as shown in the above diagram.

By careful observation, we can avoid those cars in red border, since they can’t fall in the first 25 places. We can also avoid A1, since it occupies first place.

Now we have 24 cars, some preprocessed information and 7 tracks. How best can we group them with the preprocessed information in hand, and having 7 tracks. Obviously, we need to group them in 3 groups, leaving 3 remaining.

[ If we observe, we have a matrix in which all rows sorted and only the first column sorted. Can we think of sorting the 2D matrix both vertically and horizontally? Locating 25^th element in that matrix is our target. ]

From now I have fun, since I am not sure how to proceed.

Either A2 or B1 can occupy 2^nd place. If B1 wins second place, we will end up in more races. Best possible case will arrive when A2 wins for second place.

Yet to fill

Tree equations

19, Oct, 2010

Given an N-ary tree and number of internal nodes (I), find leaf nodes in the tree. Question posted here.

I thought many people get confused while working with tree/graph related mathematics. I am providing two fundamental equations that help in understanding these equations.

In a tree with I internal nodes and L leaf nodes, the total number of nodes is sum of internal nodes and external (leaf) nodes, i.e.

T = I + L -----à 1

Assume, we are given with 3 poles (nodes). We need minimum two ropes (edges/branches in graph terminology) to connect them. Similarly, a tree with T nodes on total will have (T – 1) branches.

An N-ary tree with I internal nodes will have (N x I) branches. It is because, each internal node can have utmost N branches. We have the following relation with total nodes T,

T – 1 = (N x I) ------à 2

From the above two equations, it is clear that leaf nodes can be given by the following relation,

L = (N - 1) x I + 1

In a binary tree, N = 2, hence in a binary tree external nodes are always one more than the internal nodes.

Scala-Lift-Twitter

Scala is a new generation programming language which supports both Function Programming and Object Oriented Programming. It forms an alternative domain specific language due to the provisions such as mixins, methods as opeartor, no macros, no meta programming, etc. The language can be extended with the help of these features without altering the syntax.

Lift is web framework designed in Scala. Twitter is one major application designed in Scala to date.

The programmer needs JVM and Scala compiler. Easy to learn and experiment. Try out your had.

Permuting the words of a string

10th October, 2010

Given a string, how can you permute all words of the string? The question was asked here.

Given below is the working code. Algorithmic steps can be understood from the comments.

// Prints all the words in the string array

void printTheArray(char *array[], int size)

{

    static int count;

    int index;

    printf("%d ", count);

    for(index = 0; index < size; index++)

    {

        printf("%s ", array[index]);

    }

    count++;

    printf("\n");

}

// swpping integers is easy, swapping strings nothing but swapping their base

inline

void swapStringPointers (char *stringsVector[], int i, int j)

{

    char *base;

    base = stringsVector[i];

    stringsVector[i] = stringsVector[j];

    stringsVector[j] = base;

}

// Actual permutation algorithm (recursive)

inline

void permuteWords (char *stringsVector[], int vectorSize, int processedIndex)

{

    int currentIndex;

    if (processedIndex == vectorSize)

    {

        // print the vector

        printTheArray(stringsVector, vectorSize);

    }

    else

    {

        for (currentIndex = processedIndex; currentIndex < vectorSize; currentIndex++)

        {

            // No need to swap the same element

            if(currentIndex != processedIndex)

                swapStringPointers (stringsVector, processedIndex, currentIndex);

            // Recursively permute the smaller instances

            permuteWords (stringsVector, vectorSize, processedIndex + 1);

            // No need to swap the same element

            if(currentIndex != processedIndex)

                swapStringPointers (stringsVector, processedIndex, currentIndex);

        }

    }

}

int main ()

{

    // Just add one more string if you want to test

    char *strings[] = {"SARI", "GAMA", "PADA", "NISA"};

    int size = sizeof(strings)/sizeof(strings[0]);

    // Prints original array

    printTheArray(strings, size);

    printf("\n");

    // Permutes all words in the string

    permuteWords (strings, size, 0);

    return 0;

}

SQLite

Are you using Android phone? Then you are using SQLite software, a light weight structured query language for database. An open source software and implemented in C language. Worth reading the wiki link and if interested explore the design.

Designed by D. Richard Hipp about 10 years ago. The SQLite DLL also embedded as a plugin into Qt framework.

Member alignment of structures

When we declare structures, usually their size will not match to the sum of individual elements size. The structures size will atleast be sum of all elements size or more. Why is it so?

I referred many books for information, but almost all are helpless. Some how, I could able to trace reasons using web search. Thanks to search engines, Art of Assembly Programming book and colleagues.

Processor architectures are advanced and optimized for optimum performance. In olden days memory was byte addressable. To maintain backward compatibility next versions of many architectures were also needed to support byte addressing.

Here is the question...

Byte is 8 bits. Present day processors have 32 bit or 64 bit processing word length. It means they can process 4 or 8 bytes at a time. Usually integer is most prominent processing type on any processor. It occupy the size of processing word length.

If the memory is to be byte addressable due to backward compatibility, processor need to issue 4 read cycle to read one integer which is time consuming. In lieu of, the hardware manufacture arranges memory in banks of one byte each. So, a 32 bit processor needs 4 banks of memory. (Assuming such kind of hardware support, few processors will not have hardware pins representing least two bits).

The fun comes here. How to read data types, like char (one or two bytes), double (8 bytes always), vector types (GCC), etc... To overcome this issue, the processors provides byte read instruction (e.g. LDRB on ARM). These byte read instructions can identity, in which bank the byte is stored and shifts the data to Least Significant Byte position automatically during data fetch mode. This impacts on performance.

To get better performance characteristics, few architectures won't allow misalignments. The processor issues a platform exception which is to be addressed by the system programmer. Otherwise the results will be error prone.

I have published much better article on GeeksforGeeks.

Calculating the value of pi

18, September, 2010


Pi! What is π? How to prove its value is approximately 3.1415?

"Pi" is one of the fascinating numbers in mathematics history. I have seen some poems in Sanskrit whose character sequence gives the value of phi. It was great Indian heritage. Here I am providing my own proof.
There are more than 50 solutions found to prove phi value. They range from simple geometrical based proof to advanced Fourier series based proofs. Given below is one way, which I thought during my engineering (of-course that day the class was boring). Note that phi is irrational number. After our proof we can conclude it.

Note that when we increase the diameter of circle its Area and Perimeter will also increase. It is obvious by means of visual observation. What interests to a mathematician is, how much is the increase ratio? Is it constant?

How can we devise an algorithm or method that can be understood by school kid (may be 5^th standard)?

We trace phi value in two parts. PART 1 deals with calculating area of circle with infinitesimal pieces of radii. PART 2 deals with calculating area of circle using Pythagoras Theorem.

PART - I

The base for our proof is Pythagoras Theorem. The sum of areas of squares formed by adjacent sides to the right angle is equal to the square formed by opposite side.

Most of us know that Area of circle is A = πr², and Perimeter P = 2πr. Or we can write them in the following way.

Π = 2πr/2r = 2πr/D = P/D where D is diameter of circle. [Note it as equation 1]

It means, the ratio of perimeter of circle to its diameter is constant and it is π. I know it is poor derivation, after all we are trying for value of π. How much is its value? Can we make use of area of circle to find π value? Yes.

How can we calculate area of circle? Have a look at the following diagram.

You might have guessed. Just divide the circle into 4 parts as in Figure 1, and join them. We will not get perfect rectangle share. Try cutting the circle into further smaller pieces, and join them.

Now, cut the circle into multiple pieces of infinitesimal width and length will obviously be its radius. If we join all these pieces, we will get the rectangle as shown in the picture.

From the diagram we can calculate the circle area as A = Pr/2. [Note this as equation 2]

PART - II

We need bit patience. Consider upper right part of the circle in the Figure 1. We can find area of this piece using Pythagoras Theorem.

1. The area of rectangle triangle OAB can be easily found which is ½ r * r.
2. We left with area of the half convex formed by chord AB and perimeter of the circle. How can we calculate it? As usual, recurs.
3. Draw a perpendicular OC on to AB from the origin O. Join the lines AC and BC (those in red color). By symmetry, area of the part ADC and BDC are same.
4. In-order to find area of ADC and BDC, we need length of DC. We can easily calculate the lengths OD and DC. Also note that OD + OC = radius, and AD = DB = AB/2 by symmetry. We know AB from Pythagoras which is r² + r². From the figure we know that OD² + BD² = r² (Using trigonometry also we can find OD, try it).
5. After this step we can calculate OD and hence DC which is r * (SQRT(2)-1)/SQRT(2). AD and DB also known [r/SQRT(2)]. We need to repeat the above approach for pieces, ADC over the arc of circle and BDC over the arc of circle. After this step we will left with DC = r * (SQRT(2)-1)/SQRT(2), AD = r/SQRT(2), which gives us area of ∆ADC = ∆BDC = r²*(SQRT(2) - 1)/4.
6. Again draw perpendiculars on to AC and CB.
7. At this stage the process repeats from step 3.

We will stop after sufficient accuracy. By now, we can understand why phi is irrational, never ending and non repeating fraction (it includes lots of irrational numbers in calculation).

The area of the upper right part AOB of circle can be integrated over these small areas found by brute force method.

There will be one triangle ∆AOB that forms first term in the series is T1 = ½ r * r.

There will be two triangles (∆ADC and ∆BDC) that will form the second term (T2 = r²/sqrt(8)) in the series.

There will be four triangles that will form the third term (T3) in the series.

There will be eight triangles that will form the third term (T4) in the series.

So, area of the upper right part of circle is given by

Area of Upper Right = T1 + 2 x T2 + 4 x T3 + 8 * T4 + …

The above series leaves only ¼ of the area of actual circle. The area of circle can be found by multiplying it with 4.

Area of circle = 4 x [Area of Upper Right]

= 4 x [T1 + 2 x T2 + 4 x T3 + 8 * T4 + …]

= 4 x [½ r² + 2 x r²*(SQRT(2) - 1)/4 + 4 x T3 + 8 * T4 + …]

= 2 x r² + 2 x r²*(SQRT(2) - 1) + 16 x T3 + 32 * T4 + … [Note this as equation 3]

From equations 2 and 3, we can conclude these two areas must be same. Therefore

Pr/2 = 2 x r² + 2 x r²*(SQRT(2) - 1) + 16 x T3 + 32 * T4 + … 

Pr/2r² = 2 x r² + 2 x r²*(SQRT(2) - 1) + 16 x T3 + 32 * T4 + … 

P/2r = 2 x r² + 2 x r²*(SQRT(2) - 1) + 16 x T3 + 32 * T4 + … 

P/D = 2 + 2 x (SQRT(2) - 1) + 16 x T3 + 32 * T4 + … 

Π = 2 + 0.8284 + 16 x T3 + 32 * T4 + … ---> from equation 1

Which leaves a fraction about 3.1415… when we include few more terms. Note that the actual value is never ending and non-repeating number.

Lengthy but interesting.