How do I learn data structures and algorithms from scratch?

  1. Learn Big-Oh notation, omega and theta notations denoting complexity of algorithms and data structures.
  2. If you don’t know, learn some discrete mathematics and probability. Learn basic combinatorics, graph theory, matrices, probability theory, especially the concept of expected values. Do this on the fly.
  3. Learn basic data structures
    1. Implement singly and doubly linked lists on your own.
    2. Learn stack and queue. Implement them using linked lists. For more fun - try implementing stacks and queues using arrays.
    3. Implement vector data structure in C++ on your own. It is simple - when you run out of space, allocate twice the memory you had allocated previously and copy all the data to newly allocated array.
    4. Implement binary heap data structure and use it as priority queue.
  4. Learn sorting algorithms
    1. Learn somewhat inefficient sorting algorithms - Selection sort, Bubble sort and Insertion sort (the last one works fine on small inputs)
    2. Learn merge sort. Recursive functions can be somewhat hard to understand in the beginning. This teaches you that skill. Trace it very well.
    3. Learn quick sort. This is one of the most important algorithms ever discovered. Learn the importance of randomized quick-sort and pivot selection.
    4. Learn counting sort and why it works in linear sort.
    5. If you are interested, you can go further and learn about “stability” of sorting algorithms. For instance, merge sort and insertion sort are stable.
  5. Some more data structures now. Let’s go to the next level.
    1. Binary Search Tree - Implement the basic binary search tree and set operations using it - insert, delete, find elements in it.
    2. You might come across performance issues for certain inputs. Why? Now learn about “Balanced” binary search trees like AVL Tree and Red-Black Trees and try implementing them - This is hard, tedious and scary to implement and debug. Expect lot of Segmentation faults.
    3. Learn the concept of hashing and hash-table. Implement a hash-table. (there are two schemes).
    4. Figure out what else can be done with binary search trees. Augmenting data structures with more information? How about adding a feature where kth order statistic can be found? How about binary search on keys?
  6. You might have encountered terms like Divide and Conquer while studying merge sort. They are called “Algorithm design techniques”. You will also come across terms like Brute Force, Dynamic programming, Greedy algorithms. Now let’s dive into it.
    1. You already know Divide and Conquer. Learn Dynamic programming technique. You might find it a bit difficult in the beginning and all of us had been there. Study the solution of some standard problems like Rod Cutting, 0/1 Knapsack, Edit Distance, Matrix Chain Multiplication, Longest Increasing Subsequence etc.
    2. Now it is time to look at another technique - Greedy algorithms. Study standard problems which use greedy technique like selecting largest number of intervals among given ones so that there is no conflict. You’ll see more later.
    3. Learn the difference between all these techniques. DP and D&C differ in sub-problem overlap and Greedy, DP differ in the way decisions are made and revisited.
    4. Study the proofs of these algorithms, especially the greedy ones. Don’t worry about abstract concepts like Matroids for now.
  7. Let’s jump to Graph algorithms now.
    1. Let’s build a maze solver - Learn and implement Depth First Search (DFS) and Breadth First Search (BFS). They are basic searching techniques.
    2. Study Prim’s and Kruskal’s Minimum Spanning Tree algorithms and implement them.
    3. Let’s implement our version of Google Maps - Finding the shortest path between two given places given a roadmap. Learn and implement the algorithms of Dijkstra, Bellman-Ford and Floyd-Warshall.
Bingo, now you are pretty good at data structures and algorithms. But remember that this is just the tip of the iceberg. Once you learn it, implement on your own. Only then you get a feel of it. If you want to learn them in a fun way, try competitive programming.
Here are some resources
  1. Introduction to Algorithms - CLRS (Chapters are in the order I have written. I have skipped some chapters in it). I suggest this one along with the DSA course from Stanford on Coursera.
  2. Coursera - data structures and algorithms courses
    1. Algorithms, Part I - Princeton University | Coursera
    2. Algorithms, Part II - Princeton University | Coursera
    3. Algorithms | Coursera - from Stanford University
  3. MIT Open courseware
    1. Introduction to Algorithms (SMA 5503)
    2. Advanced Data Structures - As the course says, this is VERY advanced. If you are ready to go deeper, then go here.
  4. GeeksforGeeks - It is very helpful, especially if you are preparing for an interview.

Popular Posts

Top 10 Web Sites Every Programmer Should Visit Daily

How do I improve my logical thinking and problem solving skills?

C++: STL Iterators