Data Structures and Algorithms Fundamentals

Data Structures and Algorithms are the building blocks of efficient software. By choosing the right data structure and algorithm for the task, programmers can create software that runs quickly and uses memory effectively.

1. Today's Agenda Introduction to data Structures Linear data structures Nonlinear data structures    Applications  Real time applications Algorithms ​  Analysis (Complexities) Summary

2. What is Programming ?   Programming is the process of  creating a set of instructions that tell a  computer how to perform a task.         Programming can be done using  a variety of computer programming   languages, such as  Python, JAVA  C++, etc.   

3. What is Data Structures ?

4. Data Structure is a way of collecting and organising data in such a way that we can perform operations on these data in an effective way.   Data Structures is about rendering data elements in terms of some relationship, for better organization and storage.   

5. EXAMPLE

6. Types of Data Structures

7. Linear Data Structure

8. Linear Data structure Array Stack Queue Linked List

9. Array Array consisting of a collection of elements (values or variables), each identified by at least one array index or key.    They are also used to implement many other data structures, such as lists and strings.

10. Array Structure

11. Basic Operations in Array

12. Types of Arrays

13. One Dimensional Array One dimensional (1-D) arrays or Linear arrays In it each element is represented by a single subscript.  The elements are stored in consecutive memory locations.

14. Multidimensional Array Multidimensional arrays (a) Two dimensional (2-D) arrays or Matrix Arrays   In it each element is represented by two subscripts.

15. Applications  Implement mathematical vectors and matrices.   Implement other data structures, such as lists, hash tables, deques, queues and stacks.

16. Linked list In linked list, the elements are not stored at contiguous memory locations.  The elements in a linked list are linked using pointers 

17. Structure of Linked list List can be represented by Nodes. Each nodes contains Head and Tail.

18. Types of Linked list

19. Double Linked list Contains an extra memory to store the address of the previous node , together with the address of the next node. we are storing the address of the next as well as the previous nodes.

20. Circular Linked list It is either a singly or doubly linked list in which there are no  NULL   values. we can implement the Circular Linked List by making the use of Singly or Doubly Linked List .   In the case of a singly linked list , the next of the last node contains the address of the first node   In case of a doubly-linked list , the next of last node contains the address of the first node and previous of the first node contains the address of the last node.

21. Circular Linked List

22. Operations on list

23. Applications Implementation of stacks and queues Performing arithmetic operations on long integers Manipulation of polynomials by storing constants in the node of linked list

24. Real Time Applications Train  -    here each coach is connected to its previous and next coach (Except first and last). Image viewer  – Previous and next images are linked, hence can be accessed by next and previous button. Previous and next page in web browser   – We can access previous and next URL searched in web browser by pressing back and next button since, they are linked as linked list. Music Player  – Songs in music player are linked to previous and next song. you can play songs either from starting or ending of the list.

25. Stack Stack is a linear data structure which follows a particular order in which the operations are performed.  The order may be LIFO(Last In First Out)

26. Operations on Stack Push   Adds an item in the stack using Push() function. If the stack is full, then it is said to be an   Overflow condition.

27. POP  Removes an item from the stack by using Pop() function.  The items are popped in the reversed order in which they are pushed.  If the stack is empty, then it is said to be an Underflow condition .

28. Applications

29. Real time applications

30. Queue A Queue follows a particular order in which the operations are performed.  The order is First In First Out (FIFO).  The difference between   Stacks   and queues is in removing.   In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.

31. Operations on Queue

32. Enqueue Enqueue is a function in a queue which adds a new element in the queue. 

33. Dequeue Dequeue   is opposite of  enqueue . It returns and removes a node from the front of a queue.

34. Types of Queue

35. Circular Queue Unlike the simple queues, in a circular queue each node is connected to the next node in sequence the last node’s pointer is also connected to the first node’s address.

36. Double Ended Queue The doubly ended queue or dequeue allows the insert and delete Operations from both ends (front and rear) of the queue.

37. Priority Queue Priority queue makes data retrieval possible only through a pre- determined priority number assigned to the data items. While the deletion is performed in accordance to priority number (the data item with highest priority is removed first), insertion is performed only in the order.

38. Applications of Queue

39. Real Time Applications

40. Non Linear Data Structures 

41. Types of Non Linear Data Structures

42. Graphs

43. Example   On face book , everything is a node . That includes User, Photo, Album, Event, Group, Page, Comment, Story, Video, Link, Note ...anything that has data is a node. Every relationship is an edge from one node to another. Whether you post a photo, join a group, like a page etc., a new edge is created for that relationship.

44. Example Contd... All of face book is then, a collection of these nodes and edges . This is because face book uses a graph data structure to store its data.

45. Structure of graph   Graph is a data structure (V,E) that consists of A collection of vertices V A collection of edges E , represented as ordered pairs of vertices ( u,v ) I n this graph,             V= {0, 1, 2, 3}
           E = {(0,1), (0,2), (0,3), (1,2)}
           G = {V, E}

46. Graph Terminology Adjacency : A vertex is said to be adjacent to another vertex if there is an edge connecting them. Vertices 2 and 3 are not adjacent because there is no edge between them. Path : A sequence of edges that allows you to go from vertex A to vertex B is called a path. 0-1, 1-2 and 0-2 are paths from vertex 0 to vertex 2. Directed Graph : A graph in which an edge (U,V) doesn't necessary mean that there is an edge (V,U) as well. The edges in such a graph are represented by arrows to show the direction of the edge.

47. Graph Representation

48. Adjacency Matrix An adjacency matrix is 2D array of V x V vertices. Each row and column represent a vertex. If the value of any element  a[ i ][j]  is 1, it represents that there is an edge connecting vertex i   and vertex j . Since it is an undirected graph, for edge (0,2), we also need to mark edge (2,0); making the adjacency matrix symmetric about the diagonal. E dge lookup(checking if an edge exists between vertex A and vertex B) is extremely fast in adjacency matrix representation but we have to reserve space for every possible link between all vertices(V x V), so it requires more space.

49. Adjacency List An adjacency list represents a graph as an array of linked list. The index of the array represents a vertex and each element in its linked list represents the other vertices that form an angle with the vertex. An adjacency list is efficient in terms of storage because we only need to store the values for the edges. For a graph with millions of vertices, this can mean a lot of saved space. .

50. Operations On graph

51. Types of Graphs There are 15 types of graphs : 1.Finite graph                          8.Pseudo graph                  15. Cyclic graph   2.Infinite graph                      9.Rectangular graph 3.Trivial graph                        10.Bipartite graph 4.Simple graph                      11.Weighted graph 5.Multi graph                          12.Digraph 6.Null graph                            13.Subgraph 7.Complete graph                  14.Connected graph

52. Finite Graph  A graph is said to be finite if it has finite number of vertices and finite number of edges.

53. Infinite graph A graph is said to be infinite if it has infinite number of vertices as well as infinite number of edges.

54. Trivial Graph     A graph is said to be trivial if a finite graph contains only one vertex        and no edge.

55. Simple   Graph A simple graph is a graph which does not contains more than one edge between the pair of vertices. A simple railway tracks connecting different cities is an example of simple graph.

56. Multi Graph Any graph which contain some parallel edges but doesn’t contain any self-loop is called multi graph. For example A Road Map. Parallel Edges:  If two vertices are connected with more than one edge than such edges are called parallel edges that is many roots but one destination. Loop:  An edge of a graph which join a vertex to itself is called loop or a self-loop.

57. Null Graph A graph of order n and size zero that is a graph which contain n number of vertices but do not contain any edge.

58. Complete Graph A simple graph with n vertices is called a complete graph.   if the degree of each vertex is n-1, that is, one vertex is attach with n-1 edges.  A complete graph is also called Full Graph.

59. Pseudo Graph A graph G with a self loop and some multiple edges is called pseudo graph.

60. Rectangular Graph A simple graph is said to be regular if all vertices of a graph G are of equal degree . All complete graphs are regular but vice versa is not possible.

61. Bipartite Graph A graph G = (V, E) is said to be bipartite graph if its vertex set V(G) can be partitioned into two non-empty disjoint subsets.  V1(G) and V2(G) in such a way that each edge e of E(G) has its one end in V1(G) and other end in V2(G). The partition V1 U V2 = V is called Bipartite of G. Here in the figure: V1(G)={V5, V4, V3} V2(G)={V1, V2}

62. Weighted Graph If the vertices and edges of a graph are labelled with name, data or weight then it is called labelled graph. It is also called Weighted Graph.

63. Digraph   A graph G = (V, E) with a mapping f such that every edge maps onto some ordered pair of vertices (Vi, Vj ) is called Digraph.   It is also called  Directed Graph. Ordered pair (Vi, Vj ) means an edge between Vi and Vj with an arrow directed from Vi to Vj . Here in the figure: e1 = (V1, V2) e2 = (V2, V3) e4 = (V2, V4)

64. Subgraph  A graph G = (V1, E1) is called subgraph of a graph G(V, E) if V1(G) is a subset of V(G) and E1(G) is a subset of E(G) such that each edge of G1 has same end vertices as in G.

65. Connected Graph  A graph G is said to be connected if for any pair of vertices (Vi, Vj ) of a graph G are reachable from one another.  Or a graph is said to be connected if there exist at least one path between each and every pair of vertices in graph G, otherwise it is disconnected.   A null graph with n vertices is disconnected graph consisting of n components. Each component consist of one vertex and no edge.

66. Cyclic graph A graph G consisting of n vertices and n> = 3 that is V1, V2, V3- – – – – – – – Vn and edges (V1, V2), (V2, V3), (V3, V4)- – – – – – – – — -( Vn , V1) are called cyclic graph.

67. Applications of Graphs

68. Real Time Applications

69. Trees  A tree is a nonlinear hierarchical data structure that consists of nodes connected by edges.

70. Why Tree Data Structure ?    Other data structures such as arrays, linked list, stack, and queue are linear data structures         that store data sequentially . In order to perform any operation in a linear data structure, the time         complexity increases with the increase in the data size. But, it is not acceptable in today's computational         world. Different tree data structures allow quicker and easier access to the data as it is a non-linear data structure.

71. Tree Terminology Node A node is an entity that contains a key or value and pointers to its child nodes. The last nodes of each path are called  leaf nodes or external nodes  that do not contain a link/pointer to child nodes. The node having at least a child node is called an  internal node . Edge I t is the link between any two nodes.

72. Cond... Root     It is the topmost node of a tree. Height of a Node     The height of a node is the number of edges from the node to the deepest leaf ( ie . the longest            path from the node to a leaf node). Depth of a Node      The depth of a node is the number of edges from the root to the node.

73. Height of a tree The height of a Tree is the height of the root node or the depth of the deepest node.

74. Types of trees 

75. Binary Tree A binary tree is a tree data structure in which each parent node can have at most two children. For example : In the image below, each element has at most two children.

76. Types of Binary Tree Full Binary Tree A full Binary tree is a special type of binary tree in which every parent node / internal node has either two or no children.

77. Perfect Binary Tree A perfect binary tree is a type of binary tree in which every internal node has exactly two child nodes and all the leaf nodes are at the same level.

78. Complete Binary Tree A complete binary tree is just like a full binary tree, but with two major differences Every level must be completely filled All the leaf elements must lean towards the left. The last leaf element might not have a right sibling i.e. a complete binary tree doesn't have to be a full binary tree.

79. Degenerate or Pathological Tree A degenerate or pathological tree is the tree having a single child either left or right

80. Skewed Binary Tree A skewed binary tree is a pathological/degenerate tree in which the tree is either dominated by the left nodes or the right nodes. Thus, there are two types of skewed binary tree: left-skewed binary tree and right-skewed binary tree.

81. Binary Tree Representation  Code :      struct node
   {
    int data;
    struct node * left ;
    struct node * right ;
   }; A node of a binary tree is represented by a structure containing a data part and two pointers to other structures of the same type.

82. Binary tree Representation

83. Binary Tree Applications To easy and quick access to data In router algorithms To implement the Heap data structures

84. Binary Search tree

85. Representation of Binary tree The binary tree on the right isn't a binary search tree because the right subtree of the node "3" contains a value smaller that it.

86. AVL Tree

87. Balance Factor Balance factor of a node in an AVL tree is the difference between the height of the left subtree and that of right subtree of that node. Balance Factor = (Height of Left Subtree - Height of Right Subtree) or (Height of Right Subtree - Height of Left Subtree) The self balancing property of an AVL tree is maintained by the balance factor. The value of balance factor should always be -1, 0 or +1.

88. AVL Tree Applications 

89. B -Tree B-tree is a special type of self-balancing search tree in which each node can contain more than one key and can have more than two children. It is a generalized form of the binary search tree. It is also known as a height-balanced m-way tree.

90. Why B-Tree ?

91. B-Tree Applications

92. Refresh.... Types of data structures      Real time applications      Applications            Data Structures concepts

93. Algorithms

94. What is an Algorithm ? In CS  ,  programming , and math, an  algorithm  is a sequence of instructions where the main goal is to solve a specific problem, perform a certain action, or computation.  In some way, an  algorithm  is a very clear specification for processing data, for doing calculations, among many other tasks.

95. Search Algorithm Searching Algorithms are designed to check for an element or retrieve an element from any data structure where it is stored.

96. Some Basic Search Algorithms   1.  Linear Search 2.  Binary Search 3.  Jump search  4.  Fibonacci search 5.  Interpolation Search

97. 1.Linear Search  Linear search  is used on a collections of items.  It relies on the technique of traversing a list from start to end by exploring properties of all the elements that are found on the way. For example, consider an array of integers of size . You should find the value 10 

98. Binary Search Binary search  is an efficient algorithm for finding an item from a sorted list of items.  It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one.

99. Jump Search Like Binary Search, Jump Search is a searching algorithm for sorted arrays.  The basic idea is to check fewer elements (than linear search) by jumping ahead by fixed steps or skipping some elements in place of searching all elements.

100. Fibonacci Search Fibonacci Search is a comparison-based technique that uses Fibonacci numbers to search an element in a sorted array.

101. Interpolation Search  Interpolation search is an algorithm for searching for a key in an array that has been ordered by numerical values assigned to the keys. 

102. Sorting Algorithms

103. Some Basic Sorting Algorithms 1. Insertion Sort 2. Merge Sort 3. Selection Sort 4. Bubble Sort 5. Quick Sort 6. Heap Sort

104. Insertion Sort Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part.  Values from the unsorted part are picked and placed at the correct position in the sorted part.

105. Merge Sort  Merge sort  repeatedly breaks down a list into several sub lists until each sub list consists of a single element and  merging  those sub lists in a manner that results into a  sorted  list.

106. Selection Sort Selection sort is an algorithm that selects the smallest element from an unsorted list in each iteration and places that element at the beginning of the unsorted list.

107. Bubble Sort Bubble Sort is the simplest  sorting algorithm  that works by repeatedly swapping the adjacent elements if they are in wrong order. 

108. Quick Sort It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether  they are  less than or greater than the pivot. Sub arrays  are  then  sorted recursively.

109. Heap Sort Heap sort is a comparison based sorting technique based on Binary Heap data structure.  It is similar to selection sort where we first find the maximum element and place the maximum element at the end.  We repeat the same process for the remaining elements.

110.  Analysis of  Algorithm Analysis of the algorithm is the process of analyzing the problem-solving capability of the algorithm in terms of the time and size. Time and  performance  are the main concerns  of  analysis   of algorithm.

111. Complexites of an Algorithm The complexity of an algorithm computes the amount of time and spaces required by an algorithm for an input of size (n).   The  time complexity  and the  space complexity are the two complexities.

112. Time Complexity The time complexity is defined as the process of determining a formula for total time required towards the execution of that algorithm.  This calculation is totally independent of implementation and programming language.

113. Space Complexity Space complexity is defining as the process of defining a formula for prediction of how much memory space is required for the successful execution of the algorithm.  The memory space is generally considered as the primary memory.

114. Refresh.... Searching              Sorting    Complexities           What is Algorithms ?