Learn Algorithm


Data Structures and Algorithms (DSA for short) is an implementation based course. Many companies stress heavily on concepts from this course in their interviews. In order to master this course, you need to be strong with both the theory and implementation of various Data Structures and Algorithms.

  1. Read. You should start reading Introduction to Algorithms by Cormen et. all. This book is said to be the best for DSA but it can become a bit difficult to read it while working with your course load. You can instead use this as a reference book supplementing your recommended course book.
  2. Implement the Data Structures you read about. While reading about them might give you a fair idea of they work, it is different from actual implementation where you will need to take care of boundary cases. There will be cases where you forget null checks and mess up your entire code.
  3. Understand complexity. You need to be able to calculate the space complexity of various data structures, the time complexity of their operations and the time and space complexities of various algorithms. You should be able to judge which algorithm works better under various conditions.
  4. Practice. Solve problems from various online judges like codechef, hackerrank, topcoder and spoj. This will help you choose the optimal data structure or algo for a particular problem. You can even search for problems specific to the data structure or algo you want but where’s the fun in that?

Day -∞ to 0

Stick to a programming language like C or C++. Make sure that you are comfortable with pointers/objects.

Day 1

Understand the concept of Algorithmic complexity. Skip the theory for now, but for every piece of code you write, you should be able to derive both time and space complexity.

Day 2 – 10

Let’s start with some simple data structures,
* Arrays
* Linked Lists
* Strings
* Stacks
* Queues
Understand their basic operations (insert, delete, search, traversal) and their complexity – Big-O Algorithm Complexity Cheat Sheet, and code them all.

Day 11 – 25

Let’s now learn some simple algorithms,
* Sorting – Insertion sort, Merge sort, Quick sort, Heap sort, Bucket sort, Counting sort, Radix sort, External sorting
* Search – Linear search, Binary Search (along with its variants).
* Prime Numbers – Sieve of Eratosthenes, Primality test
* Strings – String searching, LCS, Palindrome detection
* Miscellaneous – Euclidean algorithm, Matrix multiplication, Fibonacci Numbers, Pascal’s Triangle, Max Subarray problem

Day 26 – 50

Once you are comfortable with everything above, start doing problems from,
* Cracking the Coding Interview
* Elements of Programming Interviews
* Programming Interviews Exposed: Secrets to Landing Your Next Job
* GeeksforGeeks
* HackerRank
* InterviewBit
Stick to chapters of arrays, linked lists, strings, stacks, queues and complexity.

Day 51 – 60

Let’s learn some non-linear data structures,
* Tree
* Binary Tree, Binary Search Tree – Tree traversals, Lowest common ancestor, Depth, Height & Diameter, Finding k-th smallest element
* Heaps
* Hash table – 4 sum problem, Checking if sudoku solution is valid
* Graph – Breadth-first search, Depth-first search, Topological sorting, Minimum spanning tree, Shortest path problem,

Day 61- 90

Refer to the previous resources and start doing problems from trees, hash tables, heaps and graphs.

Day 91 – 100

Understand Computational complexity theory and NP-completeness, Knapsack problem, Travelling salesman problem, SAT problem and so on.

Day 101 – ∞

You are now better than most of the CS undergrads. Keep revising the above topics and start competitive programming! Good luck!

Thanks for the A2A Meghna Bhasin
P.S. Reference from Quora

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