Learntofish's Blog

A blog about math, physics and computer science

Data Structures and Algorithms – Books and Videos

Posted by Ed on February 18, 2010

This post is about data structures and algorithms. I will give some book recommendations and links to video lectures.

Recently, I’ve become interested in data structures and algorithms. Given a problem it is fun to think about how to solve it with the computer. You need an algorithm but you also need to know how to implement it, i.e. you have to teach the computer what you actually intend to do.
For example, there are these GPS navigation systems that calculate a shortest route between two cities. You can model this using graphs and Dijkstra’s algorithm. But how do you save a graph on a computer. What kind of data structure do you use? Another example is getting out of a maze. Naturally, you would try something like Depth First Search. Again, how do you tell the computer to search for a way out of a maze?
Below is a list of books and video lectures that get you started. For me, the field of data structures and algorithms is fascinating. I also want to learn more about it to solve complex problems on projecteuler and to compete in topcoder.

Books

1) Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein
Hands down, this book also known as CLRS (the initial letter of the authors’s names) is the bible for algorithms. My first encounter with it was when I tried to understand Dijkstra’s algorithm. After this I just fell in love with the book. The pseudo codes are clear and tell you what data structures are involved. If you had to buy a book then it would be this one.

2) Introduction to the Design and Analysis of Algorithms by Anany V. Levitin
For a total beginner, this book might be better suited. I liked the section on combinatorics, e.g. how to generate permutations and combinations. The solution of the knapsack problem with dynamic programming is very well described.

3) Algorithm Design by Kleinberg, Tardos
This book is rather wordy. But I liked the section on NP completeness, a topic every computer scientist has to know.

4) The Algorithm Design Manual by Skiena
This book sheds some light on the practical side of algorithms, containing code in C++. It is not a standalone book, though. But what I really like are the “war stories”. These are stories illustrating the application of the right data structures. For example, the author tells about a problem on DNA sequences and how he worked together with his student to solve the problem. The author also describes his work on Combinatorica, a package included in Mathematica for discrete mathematics and graph theory. Moreover, you’ll find an extensive list of references at the end of each chapter.

5) Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani
You can view a draft of the entire book if you click on the link above. The section on dynamic programming is nice.

Video Lectures

1) Data Structures and Algorithms (UNSW)
Prof. Buckland is a great teacher. Look at this funny presentation of Bubble Sort during his lecture.

2) Introduction to Computer Science and Programming
This MIT course illustrates algorithms using Python.

3) Introduction to Algorithms (MIT OpenCourseWare)
This course is based on the book by CLRS I mentioned in the beginning.

4) Data Structures and Advanced Programming (UC Berkeley)
These lectures by Prof. Shewchuk illustrate algorithms using Java. Very good lectures.

5) Introduction to Data Structures and Algorithms (IIT Delhi)
A series of 36 lectures, each one lasting for almost an hour!

6) Skiena’s Algorithm Lectures
Lectures by Prof. Skiena, the author of the fourth book from above.

7) Data Structures, Algorithms, and Applications in Java
Lectures by Sartaj Sahni

8) Algorithms
Excellent lectures by Shai Simonson

At last, a step by step explanation on how quicksort works. This video helped me alot to understand this wonderful sorting algorithm.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: