Data Structures and Algorithms - The Complete Masterclass

Data structures and Algorithms : When we talk about best algorithms, best practice, or performance of the program is everything based on execution time for the program. An ultimate aim for every programmer is reduce the execution time of the program. Am I right? So when we will say that, this is the best algorithms for this process. So answer I simple. The algorithm which is gives the result in a short time in all the cases. That is a suitable algorithm for that process

Data Structures and Algorithms : There will often be trade-offs that we will need to identify and decide upon. As computer scientists, in addition to our ability to solve problems, we will also need to know and understand solution evaluation techniques. In the end, there are often many ways to solve a problem. Finding a solution and then deciding whether it is a good one are tasks that we will do over and over again 

Data Structures and Algorithms : In real time we might have lots of option while choosing an algorithm. Which mean for the single problem we will have lots of algorithms to solve the problem. Analysis the algorithm is help you to choose the right one. We will analysis the algorithm based on complexity of the program. So it’s very important to know how to calculate the complexity of the program.

Data Structures and Algorithms : Asymptotic Analysis is the great idea that handles these kind issues while analyzing algorithms. In Asymptotic Analysis, we evaluate the performance of an algorithm in terms of input size (which means we don’t measure the actual running time). We calculate, how does the time (or space) taken by an algorithm increases with the input size   

Data Structures and Algorithms : Whatever the number I am searching for and its is present in the last element of this array. Then it will be a worst case for this case.

 If an element is there in 1 st position of this list of values it will be the best case scenario. If its present in the middle, than it will be average case.

Data Structures and Algorithms : In this Video, you’ll be presented with the common rules of logarithms, also known as the “log rules”. 

Data Structures and Algorithms : In this video we are going to discuss about different levels of complexity in terms of Big O

When we talk about the code complexity, we will have different levels of complexity for the algorithms.

Data Structures and Algorithms : This video is quick wrap-up which you learnt in this unit.

So far, you have learnt every single details about basics of data structures and algorithms. Now It's time to evaluate your skill. Lets get start!

Data Structures and Algorithms : This course is purely designed to focus on data structures and algorithms. I am strongly believing that, data structures and algorithm are not a technology. using correct data structures and writing efficient algorithm is a skill, So I am going to focus on to teach you how the apply this skill in Real time application which means how to apply this knowledge while choosing data structure in real application.

As an instructor, I should make you comfortable to understand the concept which is we are going to discuss in this course. So I need some programming language to explain the concepts     

Data Structures and Algorithms : Whenever we want to work with large number of data values, we need to use much number of different variables. As the number of variables are increasing, complexity of the program also increases and programmers get confused with the variable names. There may be situations in which we need to work with large number of similar data values. To make this work more easy, programming languages provides a concept called "Array" Data Structures. That’s what we are going to discuss in this lecturer in Data Structures and Algorithms course.

Data Structures and Algorithms : Its Implementation approach for 1D Array Implementation

Data Structures and Algorithms : All popular languages, like C/C++, Java or Perl start indexing an array from 0 while the last index is the array length minus 1. While this is usual to most developers, it is not a same fact for all programming languages. For example in Fortran, when you declare an array with 'integer a(10)', an int array having 10 elements, the index starts from 1 and ends at 10 (however you can override this behavior using a statement like, integer a(0:9), by declaring an array with indices from 0 to 9).   

Data Structures and Algorithms : In this video we are going to discuss about 2 DIMENSIONAL ARRAY

When we talk about 2D array, all the features from the 1D array applicable for 2 D array as well. The difference is, this array having 2 dimensional. To understand this, it’s better to think of the two-dimensional array as a matrix. A matrix can be thought of as a grid of numbers, arranged in rows and columns, kind of like a bingo board.

Data Structures and Algorithms :

Like array, Linked list is the another way to sore the data. So before we move to linked list in detail we first understand why linked list and what is the problem with array data structure.

Data Structures and Algorithms : Whatever we have discussed in last video. Its singly linked list. Which means in every node holding value and another node which means reference of next node.

Data Structures and Algorithms :

A Single linked list contains two parts within it right. One part is holding actual data and another part contains reference of next node. But, A Doubly Linked List (DLL) contains an extra pointer, typically we can call it as previous pointer

Data Structures and Algorithms : In ordinary Doubly Linked List requires space for two address fields to store the addresses of previous and next nodes. A memory efficient version of Doubly Linked List can be created using only one space for address field with every node. This memory efficient Doubly Linked List is called XOR Linked List. or Memory Efficient as the list uses bit-wise XOR operation to save space for one address. In the XOR linked list, instead of storing actual memory addresses, every node stores the XOR of addresses of previous and next nodes.

Data Structures and Algorithms : If you see the  Singly linked list and doubly liked list, Last node reference will point to null right. But in circular linked list, Last node reference will point to first node so that it will form a circle. Here you can start your iteration from anywhere you want. But in singly and doubly linked list you can start the iteration from Head node only. Which means 1st node

Data Structures and Algorithms : Its Implementation approach for  Linked List

Data Structures and Algorithms : Home work

Data Structures and Algorithms : Till now we have discussed about Array and Linked list and various form of array and linked list.

But when we should prefer linked list over array and when we should prefer array over linked list. Lets discuss this in this video.

Data Structures and Algorithms : Hash table is a data structure used to store a key-value pair. In a hash table, data is stored in an array format, where each data value has its own unique index value. Access of data becomes very fast if we know the index of the data that is the idea of hash table

Data Structures and Algorithms : Hashing is a technique used in Hash table to convert a range of key values into a range of indexes of an array. Hashing is a technique that is used to uniquely identify a specific object from a group of similar objects. We're going to use modulo operator to get a range of key values.

Data Structures and Algorithms : Some times if you apply a hash function to two different keys its generate the same index number for both the keys. But both the element can’t go to the same place. This is known as collisions. And we have seen 2 different ways to handle collisions one is separate chaining and another one is open addressing.

Data Structures and Algorithms : This video is quick wrap-up which you learnt in this unit.

Data Structures and Algorithms : Stack is a simple data structure and its another option to storing data and stack is some what similar to Linked Lists. In a stack, the order in which the data arrives is important.   

Data Structures and Algorithms : When we use stack data structure to store the element, we can do basic operation like inserting element into the stack and remove the element from the stack. It’s basically PUSH and POP.     

Data Structures and Algorithms : Now we are going to see some real-world application for Stack data structure.

Data Structures and Algorithms : Its Implementation approach for Stack using Linked List

Data Structures and Algorithms : Its Implementation approach for Stack using Array

Data Structures and Algorithms : Queue is another data structure used to storing data and it is similar to Linked Lists and stack. In a queue, the order in which the data arrives is important. Let’s say for example, a queue is a line of people or things waiting to be served in sequential order starting at the beginning of the line or sequence. A Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO)

Data Structures and Algorithms : When we use queue data structure to store the element, we can do basic operation like inserting element into the queue and remove the element from the queue. It’s basically ENQUEUE and DEQUEUE. These or the main operation in queue.

Data Structures and Algorithms : Here we are going to see some real-world application for Queue data structure.

Data Structures and Algorithms : Its Implementation approach for Queue Using Linked List

Data Structures and Algorithms : Its Implementation approach for Queue Using Array

Data Structures and Algorithms : In this video we are going to talk about priority queue. Priority queue is similar to queue and only difference is, while adding the element in to the priority queue data will add in sorted order. That’s it. That the only different between normal queue and priority queue. Other than this, everything is similar like enqueue, dequeue operations and basic feature of queue like the element which is inserted first the one will come out first. So everything will be similar to normal queue.

Data Structures and Algorithms : This is quick wrap-up for whatever we have covered in this Unit.

Data Structures and Algorithms : Tree is another type of data structure like linked list, Stack and Queue. But Tree is somewhat different from these data structure. Means Tree is the nonlinear data structure while linked list, Stack and Queue are linear data structure. Which means, In Linked list, Stack and queue node are simply pointing to next node means one node will point to another node. But in tree nodes are pointing no many number of nodes. these nodes are leaf of the tree   

Data Structures and Algorithms : Further we will discuss about binary tree which is derived from Tree. We can say like if tree met certain condition which is applicable for Binary tree that’s called Binary tree.

 So The things we were discussed about root node, children, height and depth are applicable for binary tree also.

Data Structures and Algorithms : Binary Search Tree is another variant of Binary Tree. In the binary tree we haven’t any restriction for node data. So, if you want to search any node data from binary tree, you have to search both left sub tree and right sub tree. Means we have to visit each and every node of the tree. So, complexity will be O(n) in worst case. That’s why we came for Binary search tree. The main use of binary search tree is Search. It has the restriction for node data’s while storing it into the binary search tree. So, it will simplify the complexity of search operation in Tree. As a result, it reduces the worst case complexity to O(logn).

Data Structures and Algorithms : Its Implementation approach for BST

Its Implementation approach for BST Insert

Its Implementation approach for BST Delete 

Data Structures and Algorithms : Here we will start with Breadth First Search. In the name itself saying that, we have to visit the nodes based on Breadth of the tree. Or simply we can say like search horizontally. And In Breadth first search we have to prioritize the node by visiting all node on the same level before we move down to child node.     

Data Structures and Algorithms : Its Implementation approach for Breadth First Search

Data Structures and Algorithms : In Breadth first search approach for any node, we visit all its children before visiting any of its grand children.     But in Depth first approach, if we would like to go child of any node. We have to complete full left subtree of that node before we move to right child node.           

Data Structures and Algorithms : If we go over pre order traversal, we have to visit root node first and than left node and than right node.

Data Structures and Algorithms : If we go over In order traversal, we have to visit left node first and then root node and than right node. Ok now we will travel through this tree.

Data Structures and Algorithms : If we go over post order traversal, we have to visit left node first and then right node and than root node. Ok now we will travel through this tree.

Data Structures and Algorithms : Its Implementation approach for Depth First Search

Data Structures and Algorithms : This is quick wrap-up for whatever we have covered in this Unit.

Data Structures and Algorithms : Graph is pair of node and connections. I will just draw some circles. I will call it as A, B and C. These circles are nodes. And these nodes are connected with line and we can call this as connection. Its just a connection between the nodes. We will refer this nodes are vertices and we will refer this connection as edges. This is the graph. So Basically A Graph consists of a finite set of vertices and set of Edges which connect a pair of nodes. And A Graph is a non-linear data structure like tree.

Data Structures and Algorithms : So coming to type of graph, there are two kind of graph, i.e

• Direct/Undirected Graph

• Weighted/Un Weighted Graph

Till now what we have discussed and what the example we have used to discuss about the graph is Un directed and un weighted graph. Means we haven’t use any direction when we represent edges and we haven’t given any number to the edges to associate with. I mean weight.

Data Structures and Algorithms : If we search this in internet, mostly people are talking about the two ways to represent the graph data structure.

• Adjacency Matrix

• Adjacency List

Its hard to represent the graph data structure other than these two ways why because, we can expect one node may connected with more number nodes.  

Data Structures and Algorithms : Matrix the one way to represent Graph data structure in another hand List is another way to do the same Job. So which one is better. Here will compare both the things based on certain factor like accessing node and accessing child node and memory.

Data Structures and Algorithms : Its Implementation approach for Graph

Data Structures and Algorithms : Based on the order on which node is visited, graph traversal algorithms are classified into two category.  

• Breadth First Search (B F S)

• Depth First Search   (D F S)

Data Structures and Algorithms : Its Implementation approach for Graph Traversal

Data Structures and Algorithms : This is quick wrap-up for whatever we have covered in this Unit.

Data Structures and Algorithms : Dijkstra’s algorithm can be used to determine the shortest path from one node in a graph to every other node within the same graph

Data Structures and Algorithms : A Start Search algorithm is one of the best and popular technique used in path-finding in Graph. it is really a smart algorithm which separates it from the other conventional algorithms or we can say like The A* search algorithm is an extension of Dijkstra's algorithm to finding the shortest path between two nodes. And A* algorithm requires a heuristic, it is defined using heuristic values for distances.      

Data Structures and Algorithms : Linear search sequentially checks each element of the list until it finds an element that matches the target value. If the algorithm reaches the end of the list, the search terminates unsuccessfully.

Data Structures and Algorithms : Its Implementation approach for Linear Search

Data Structures and Algorithms : Binary search works on sorted arrays. Binary search begins by comparing the middle element of the array with the target value. If the target value matches the middle element, its position in the array is returned. If the target value is less than the middle element, the search continues in the lower half of the array. If the target value is greater than the middle element, the search continues in the upper half of the array. By doing this, the algorithm eliminates the half in which the target value cannot lie in each iteration

Data Structures and Algorithms : Its Implementation approach for Binary Search

Data Structures and Algorithms : Sorting is the process of rearrange the data with in collection. Sorting is the common task and its very interesting one to understand in data structure world. We can apply the sorting algorithm on top of all most all the data structures like array, linked list like that. There are millions of ways to sort the collection. Similarly, lots of sorting algorithms are available and each one work and give the best result based on data available in the data structure.     

Data Structures and Algorithms : In this video we will start with bubble sort algorithm. It’s a famous algorithm for sorting   

Data Structures and Algorithms : Its Implementation approach for Bubble Sort

Data Structures and Algorithms : In this video are going to talk about selection sort. The selection sort algorithm sorts an array by repeatedly finding the minimum element from unsorted part and putting it at the beginning. Means this algorithm finds the minimum element from the array and it will be placed in the 1st position. And its done for 1st position and in the next iteration, it will take and process the rest of the element which is unsorted now in the array.     

Data Structures and Algorithms : Its Implementation approach for Selection Sort

Data Structures and Algorithms : In this video we are going to discuss about insertion sorting algorithm.

Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands.

Data Structures and Algorithms : Its Implementation approach for Insertion Sort

Data Structures and Algorithms : So next algorithm is merge sorting algorithm. Merge sorting technique based on divide and conquer technique. So algorithms which is we have discussed earlier i.e. Bubble sort, Selection sort and insertion sort are taking time complicity will be n2  in worst case. But for the merge sort time complexity will be Ο(n log n). It’s somewhat less complexity than other sorting algorithm.

 I hope you remember that, Divide and conquer means dived the bigger problems to small problems and conquer means analyze the problem and finally combine the results.

Data Structures and Algorithms : Its Implementation approach for Merge Sort

Data Structures and Algorithms : In this video we are going to discuss about quick sorting algorithm. This algorithm applies divide and conquer approach to solve the sorting problem. As we have already discussed, Divide and conquer means dive the bigger problems to small problems and conquer means analyze the problem and finally combine the result. The overall idea of the quick search algorithm is, choosing one element as a pivot element and partitioning the array around it. means the element which is smaller than pivot, has to be moved to left hand side of the pivot and the element which is greater the pivot, has to be moved to right hand side of the pivot.     

Data Structures and Algorithms : Its Implementation approach for Quick Sort

Data Structures and Algorithms : In this video we are going to discuss about the one of the most interesting algorithm for storing Its Heap sort. In this Unit we have seen lots of algorithm for sorting the elements in the collection. Compared with all other algorithm, heap sort algorithm will be more efficient than other algorithms. Why because, if you take Merge sort its time complexity will be nLogn but While we think about space its taking more space to execute the algorithm right I hope you remember that its O(n). Lets think about Quick sort its space complexity will be O(1) but what about its time complexity  in worst case. Its O(n2).

But if we use heap sort to sort the element in an array time complexity will be O(nLogn) and space complexity will be O(1). Its better deal right.

Data Structures and Algorithms : Its Implementation approach for Heap  Sort

Data Structures and Algorithms : I recommend you to spent your valuable time in https://www.geeksforgeeks.org/

And another great resource to increase problem solving skill is https://www.hackerrank.com/dashboard