Learning 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.

I was in the same situation 1 and a half year ago. I will explain how I learnt data structure and algorithms.

In the following text Algorithms and Data structure which are marked in bold are very important. Learn every algorithm/data structure with it’s time & space complexity, stable, in place, and where it is useful.

What to study?

Step 0 :

• Understand about pointers in C++, structures or classes
• Learn how to calculate worst case, best case , average case time complexities

Step 1 :

• Learn few basic sorting algorithms along with their use case and time complexity.
  • Bubble sort
  • Insertion sort
  • Selection sort
• Learn searching algorithms along with time complexity.
  • Linear Search
  • Binary Search

Step 2 :

• Stack
• Queue
• Single Linked List (Insert at front,back,middle; Delete at front back middle)
• Double Linked List
• Circular Linked List

Step 3 :

• Learn the following approaches in algorithms
  • Divide and Conquer (Merger Sort, Quick Sort, Binary Search are some examples)
  • Greedy method (Knapsack, Prim’s algorithm, Kruskal’s algorithm, Dijkstra, Bellmanford)
  • Dynamic programming (0/1 Knapsack, Travelling Salesman Problem, Coin change)
• Backtracking (N Queens problem)

Step 4 :

• Binary Tree
• Binary Search Tree
  • Height of a Tree
  • Tree Traversal
    • BFS
    • DFS
  • Searching an element
• AVL Tree
• Hashing

Where to study from?

GeeksforGeeks | A computer science portal for geeks

Data Structures and Algorithms | Coursera

Video Lectures | Introduction to Algorithms (SMA 5503) | Electrical Engineering and Computer Science | MIT OpenCourseWare

Note: If detailed answer or specific approach is needed, feel free to massage me on quora.

First thing you should know is how pointer works,how dynamic memory gets allocated and also basic concepts like stack unwinding etc.

Now assuming that your basics are clear, you should start with famous Thomas Cormen book; start implementing the algorithms on your own. At first, you’ll struggle but remember hard work is the key to success.

If you are not best at programming, then look for geeksforgeeks.org website. This website is the best to crack any coding interview.

Some more:

1. Data structure course – Unlimited Online Developer, IT and Creative Training
2. Udemy data structure course
3. mycodeschool
4. thenewboston – Youtube channel

Happy coding…!!!