What is The Sequence of Learning Data Structures and Algorithms

In this post i will tell you one of the important thing how data structures and algorithms is learning process. Many students or Beginner will confuse where to start to learn Data Structure and algorithms. Here is the right place to know it. The following sequences of learning Data Structures and Algorithms for all.

1. Arrays(Sorting, searching, adding , deleting, traversing)
2. singly linked-list using Arrays
3. doubly linked-list using Arrays
4. circular linked-list using Arrays
5. doubly circular linked-list using Arrays
6. queue using arrays
7. circular queue using arrays
8. stack using arrays
9. double stack using arrays
10. Repeat all of the above using ‘struct’ in both ‘recursive’ and ‘non-recursive’ implementations.
11. trees using structs
12. Binary search tree
13. AVL Trees
14. RB Trees
15. Graphs

Algorithms:

• Searching algorithms
• Sorting algorithms
• Maximum and minimum element in a data structure
• Sum and average of all elements in the data structures
• Inorder, preorder and post-order tree traversals
• BFS and DFS
• Graph algorithms- Shortest path
• Greedy algorithms
• Divide and conquer
• Backtracking
• Dynamic programming  

What algorithms you must learn for Programming Competition?

In this post you will know what algorithms you must learn for an undergraduate level programming competition. So the following algorithms you should get knowledge.

Mathematics:

(a)Number Theory

Prime Number Generation (Sieve, Segmented Sieve)
Euler Totient Theorem
Fermat’s Theorem
HCF & LCM (Euclid)
Linear Diophantine Equations (Extended Euclid)
Modulus Arithmetic (addition,multiplication,subtraction,modular Inverse)
Cycle Finding (Floyd Algo and Brent Algo)
Integer Factorization (Trial Division , Pollard Rho method)
Lucas Theorem (Simple & Advance)
Chinese Remainder Theorem
Wilson Theorem
Miller - Rabin Primality Testing
Perfect Numbers
Goldbach Conjecture

(b)Probability

Basic Probability and Conditional Probability
Random Variables
Probability Generating Functions
Expectation
Probability Distribution [Binomial, Poisson, Normal,Bernoulli]

(c)Counting

Pigeonhole principle
Inclusion Exclusion
Special Numbers [Stirling,Fibonacci,Catalan, Eulerian, Harmonic, Bernoulli]
Polya Counting
Burnside lemma

(d)Permutation Cycles

(e)Linear Algebra

Addition And Subtraction Of Matrices
Multiplication ( Strassen's algorithm ), Logarithmic exponentiation
Matrix Transformations [ Transpose, Rotation Of Matrix, Representing Linear Transformations Using Matrix ]
Determinant , Rank and Inverse Of Matrix [ Gaussian Elimination , Gauss Jordan Elimination]
Solving System Of Linear Equations
Matrix Exponentiation To Solve Recurrences
Eigenvalues And Eigen vector
Roots of a polynomial [ Prime factorization of a polynomial, Integer roots of a polynomial]
Lagrange Interpolation

(e)Game Theory

Basic Concepts & Nim Game [Grundy Theorem , Grundy Number]
Hackenbush

(f)Group Theory

Burnside Lemma
Polya's Theorem

Graphs:

(a)Graph Representation

Adjacency Matrix
Adjacency List
Incidence Matrix
Edge List

(b)Graph Types

Directed
Undirected
Weighted
Unweighted
Planar
Hamilton
Euler
Special Graphs

(c)DFS & It’s Application

Cycle Detection
Articulation Points
Bridges
Strongly Connected Component
Connected Component
Path Finding
Solving Maze
Biconnectivity in Graph
Topological Sorting
Bipartite Checking
Planarity Testing
Flood-fill algorithm

(d)BFS & It’s Application

Shortest Path (No. Of Edges)
Bipartite Checking
Connected Components
(d)Minimum Spanning Tree

Prim’s Algorithm
Kruskal Algorithm
(d)Single Source Shortest-Path

Dijkstra
Bellman Ford

(e)All pair Shortest Path

Floyd Warshall’s Algorithm

(f)Euler Tour

(g)Flow

Ford-Fulkerson [PFS,DFS,BFS]
Dinic's Algorithm
Min Cost - Max Flow [Successive Shortest Path Algo,Cycle Cancelling Algorithm]
Max Weighted BPM [Kuhn Munkres algorithm/Hungarian Method]
Stoer Wagner Min-Cut Algo
Hop-Kraft BPM
Edmond Blossom Shrinking Algorithm

(h)Other Important Topics On Graphs

2-SAT,
LCA
Maximum Cardinality Matching
Application Flow
Min Path Cover Over Dag
Independent Edge Disjoint Path
Minimum Vertex Cover
Maximum Independent Set

Data Structures:

Arrays
Linked List
Trees (Binary Tree And Binary Search Tree)
Stacks
Queues
Heap
Hash Tables
Disjoint-Set Data Structures
Trie
Segment Tree
Binary Index Tree
Treap

Searching And Sorting:

Linear Search
BInary Search
Ternary Search
Selection Sort
Bubble Sort
Insertion Sort
Merge Sort
Quick Sort
Quick Select
Heap Sort
Radix Sort
Counting Sort
Greedy:
Classical Problems of Greedy & Concept
example : Fractional Knapsack

Dynamic Programming Classical Problems

Edit Distance
Egg Dropping Puzzle
Integer Knapsack
Largest Independent Set
Longest Biotonic Subsequence
Longest Common Subsequence
Longest Common Substring
Longest Increasing Subsequence
Longest Palindromic Subsequence
Longest Palindromic Substring
Longest Substring Without Repeating Character
Matrix Chain Multiplication
Max Size Square Submatrix With One
Maximum Length Chain Pairs
Maximum Sum Increasing Subsequence
Optimal Binary Search Tree
Palindrome Partition Problem
Set Partition Problem
Subset Sum
Word Wrap Problem

Dynamic Programming Advanced Techniques

DP + Tree
DP + Bit Masking
DP + Binary Search
DP + Graph
DP + Matrix Exponentiation
DP + Probability Space
DP + Crack Recurrence
Divide & Conquer

Classical Problems & Concepts

Merge Sort
Closest Pair Points

Other Algorithm Design Techniques :

BackTracking
Man In Middle
Newton-Raphson to reach the fixed point
Brute Force
Constructive Algo
Sliding Window
Pancake Sorting

Difference Between QuickSort and MergeSort

In this post you will learn the main difference between quicksort and mergesort. Both are sorting algorithms based on the divide and conquer strategy.

Mergesort

The real work of mergesort is done by the merge operation. Given two sorted sub-arrays, together having a total of n elements,  the merge operation uses an auxiliary array of size n to merge them together into a single sorted array in linear time i.e. O(n) in Big Oh notation.

Having this merge operation, mergesort works as follows. Given an array of elements A, it sorts the left and right sub-arrays using mergesort itself, and then merges them together into one single sorted array. The base case is a sub-array of size 1, which is implicitly sorted by definition.

If we analyze the time complexity of mergesort, we will see it is O(n log n) in all cases. That is, the time taken to sort n elements grows proportionally to n log n. Merge sort also needs an extra array of size n for the merge operation. So its space complexity is O(n).

Quicksort

Quicksort is another divide and conquer sorting algorithm, proposed by C. A. R. Hoare. Here, the workhorse is the partition operation. Given an array of n elements, partition takes one element (known as the pivot) and places it in the correct position. That is, the array will not be sorted, but all the elements less than the pivot will be to the left of the pivot, and all the elements greater than the pivot will be to the right. The partition operation can be performed in linear time.

Quicksort then works as follows. First, it performs the partition operation on the input array. Assume the pivot is placed in position p. Now, quicksort sorts the sub-arrays A[0 : p - 1] and A[p + 1 : n - 1], using quicksort itself. Here again, the base case is an array of size 1.

There are various ways of selecting the pivot. The simplest is to just take the left-most element every time as the pivot. But, this leads to a fatal weakness. In this case, if the array is already sorted, the pivot will get placed in the left most position always, and quicksort will be sorting sub-lists of size 0 and n - 1. This leads to a time complexity of O(n2)O(n2), which is no better than bubble sort.

This can be mitigated by choosing a random element as the pivot, or using the median of three elements. In this case, the worst case time of O(n2)O(n2) is extremely unlikely (borderline impossible).

In the best case, when the pivot is always placed in the middle, the time complexity will be O(n log n). Also, if the pivot always gets placed somewhere in the middle 50% (25% - 75%) part of the array, quick sort will take time proportional to O(n log n), even as in the best case.

The biggest advantage of quick sort is that, even though the asymptotic complexities are O(n log n), the constant muliplier (hidden by the Big Oh notation) is much smaller for quicksort, which subsequently is appreciably faster than mergesort in almost all cases.

Regarding space complexity, the space complexity of quicksort is O(log n), taking into account the stack space used for recursion.

Also, quicksort cannot be implemented iteratively, unlike mergesort, where an iterative implementation, sometimes called bottom-up mergesort, is possible.

What are Machine Learning Algorithms?

In this post you will know some the mostly used Machine Learning Algorithms. If I had to choose one, I'd say my favorite algorithm is the Ensemble, which I consider my own “Master Algorithm”. Whatever algorithm you start from, you can always use an ensemble to improve it. Ensembles won the Netflix Prize and routinely show their great performance, but they are also relatively easy to understand, optimize, and inspect.  My Second Algorithm is  Logistic Regression(LR )is a very simple but efficient and flexible algorithm that can be used for many applications, notably classification, but also ranking.

The following are some of the commonly used ML Algorithms:

1. Back-propagation algorithm - a relatively simple idea that made neural networks useful.
2. Dropout - if we can consider it an algorithm (I like to think about it as a useful idea to use on neural networks). It makes you create ensemble classifiers without making many models.
3. PCA - mathematics at its best (or thereabouts). Very useful a lot of times, although probably a bit overused.
4. Perceptrons - just to study the convergence theorem, a thing of beauty.
5. Linear regression - the mathematics behind how the cost function comes is so nice.
6. Logistic regression - well, we want a simple but powerful model to do classification.
7. KNN - why not? Dumb, but very useful.
8. K-means - one of the most famous algorithms ever. There are so many much more sophisticated clustering algorithms, and k-means is still as useful as it ever was.
9. Replicator dynamics - because game theory is interesting and fun. And because it can be used as a building tool in doing a lot of completely different things, like graph matching or clustering (dominant sets).
10. Szemeredi’s regularity lemma - not a machine learning algorithms, but something that can be used on machine learning (and in any graph problems when we want to reduce them). And more importantly, because I worked on it in my master thesis, and did my first ever paper on it.
11. Support Vector Machines - because the maths there is stunning. And because all those hours of learning function analysis, are finally put to work.
12. Regularization - because nothing works without it.

Most elegant: The Perceptron algorithm. Developed back in the 50s by Rosenblatt and colleagues, this extremely simple algorithm can be viewed as the foundation for some of the most successful classifiers today, including suport vector machines and logistic regression, solved using stochastic gradient descent. The convergence proof for the Perceptron algorithm is one of the most elegant pieces of math I’ve seen in ML.  

Most useful: Boosting, especially boosted decision trees. This intuitive approach allows you to build highly accurate ML models, by combining many simple ones. Boosting is one of the most practical methods in ML, it’s widely used in industry, can handle a wide variety of data types, and can be implemented at scale. I recommend checking out XGBoost for really scalable implementation of boosted trees. Boosting also lends itselft to very elegant proofs.

Biggest comeback: Convolutional neural network deep learning This type of neural network has been around since the early 80s. Although there was a decline in interest in them from the late nineties to late 2000s, they have seen an amazing comeback in the last 5 years. In particular, convolutional neural networks form the core of the deep learning models that have been having a huge impact, especially in computer vision and speech recognition. 

Most beautiful algorithm: Dynamic programming (e.g., Viterbi, forward-backward, variable elimination & belief propagation algorithms). Dynamic programming is one of the most elegant algorithmic techniques in computer science, since it allows you to search through an exponentially-large space to find the optional solution. This idea has been applied in various ways in ML, especially for graphical models, such as hidden Markov models, Bayesian networks and Markov networks. 

Unbeatable baseline: Nearest-neighbor algorithm. Often, when you are trying to write a paper, you want to show that “your cuve is better than my curve”. :) One way to do that is to introduce a baseline approach, and show that your method is more accurate. Well… nearest-neighbor is the simplest baseline to implement, so often folks will try first, thinking they’ll easily beat it and show their method is awesome. To their surprise, nearest-neighbor can be extremely hard to beat! In fact, if you have enough data, nearest neighbor is extremely powerful! And, this method is really useful in practice.

Best place to learn Data Structure and Algorithms Online

In this post you will know the best place to learn data structures and algorithms through online. Before learning algorithms/ds, learn a programming language first.  The following are the 3 best places to learn ds and algorithms. They are

1. https://www.udemy.com/introduction-to-algorithms-and-data-structures-in-c/

2. Abdul Bari:

3. CS Dojo:

How do I use Algorithms in real life?

In this post you will know how do we use algorithms and data structures in real life. they are
We do it all the time!

• On the way to your college canteen? A* search
• Waiting in line in the canteen? Queue
• Notice that girl standing in front? Linear search
• Searching for her dad in the phone book? Binary search
• Stupid! Google it! Trie
• Search for her on Facebook! Depth-first search
• Found her! Friend request? Accepted! Send a Hi! Graph
• Writing her a secret love letter? Caesar cipher
• Uploading your first date pic on fb? Image compression algorithms
• Looking through her Whatsapp messages? KMP algorithm
• She found out and had your first fight? Start over with some gifts! Backtracking
• Got her list of items to buy? Array
• Too many items! Low on cash, maybe? Priority queue
• Making her play treasure hunt for her gifts? Linked list
• Wait! Go back! Is that a ring? Stack
• Girl’s family not agreeing to your proposal? Divide and conquer
• Got married? Congrats! Going for your honeymoon? Travelling salesman problem
• Your mom packing luggage for you? 0/1 Knapsack problem
• She packed your favorite pickles? Hash table
• Driving to the airport? Breadth-first search