Sunday, November 21, 2010

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,
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.
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.
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.
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.
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.
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.
Another nice book on algorithms. Good collection of problems, and problem solving techniques.

    Sunday, November 7, 2010

    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,
    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?