E Lesson 3

IDOL Institute of Distance and Online Learning ENHANCE YOUR QUALIFICATION, ADVANCE YOUR CAREER.

MCA 2 All right are reserved with CU-IDOL DESIGN AND ANALYSIS OF ALGORITHMS Course Code: MCA 632 Semester: Third e-Lesson: 3 Unit: 4 www.cuidol.in Unit-4(MCA 632)

Design and Analysis of Algorithms 33 OBJECTIVES INTRODUCTION  Student will be able to define concept of data  In this unit we are going to learn about data structure like array , stack, queue and graph, tree structures.  Student will be able to calculate time complexity Under this you will learn and understand the concept of stack, queue, tree and graph and space complexity of various data structures.   Student will be able to do analyze of stack and queue Student will be able to learn about sets and  Different sets and dictionaries..  dictionaries. www.cuidol.in Unit-4(MCAQ-613021)) INSTITUTE OF DAIlSlTAriNgChEt aArNeDreOsNeLrvINeEd LwEiAthRNCIUN-GIDOL

TOPICS TO BE COVERED 4 Important Problem Types: Stacks Queues Graphs Trees Sets and Dictionaries www.cuidol.in Unit-4(MCA 632) All right are reserved with CU-IDOL

Stack 5 www.cuidol.in Unit-4(MCA 632) All right are reserved with CU-IDOL

Stack 6 A stack is used for the following two primary operations − push() − Pushing (storing) an element on the stack. pop() − Removing (accessing) an element from the stack. When data is PUSHed onto stack. To use a stack efficiently, we need to check the status of stack as well. For the same purpose, the following functionality is added to stacks − peek() − get the top data element of the stack, without removing it. isFull() − check if stack is full. isEmpty() − check if stack is empty. www.cuidol.in Unit-4(MCA 632) All right are reserved with CU-IDOL

Queue 7 www.cuidol.in Unit-4(MCA 632) All right are reserved with CU-IDOL

Queue 8 The basic operations associated with queues − enqueue() − add (store) an item to the queue. dequeue() − remove (access) an item from the queue. Few more functions are required to make the above-mentioned queue operation efficient. These are − peek() − Gets the element at the front of the queue without removing it. isfull() − Checks if the queue is full. isempty() − Checks if the queue is empty. www.cuidol.in Unit-4(MCA 632) All right are reserved with CU-IDOL

Graph 9 Graphs are mathematical structures that represent pairwise relationships between objects. A graph is a flow structure that represents the relationship between various objects. It can be visualized by using the following two basic components: Nodes: These are the most important components in any graph. Nodes are entities whose relationships are expressed using edges. If a graph comprises 2 nodes A and B and an undirected edge between them, then it expresses a bi-directional relationship between the nodes and edge. Edges: Edges are the components that are used to represent the relationships between various nodes in a graph. An edge between two nodes expresses a one-way or two-way relationship between the nodes. www.cuidol.in Unit-4(MCA 632) All right are reserved with CU-IDOL

Graph Representation 10 The adjacency matrix representation of the following graph is: i/j : 1 2 3 4 1:0101 2:1010 3:0101 4:1010 The adjacency list representation A1 → 2 → 4 A2 → 1 → 3 A3 → 2 → 4 A4 → 1 → 3 www.cuidol.in Unit-4(MCA 632) All right are reserved with CU-IDOL

Graph Traversing 11 Two methods of Graph Traversing are BFS and DFS. Breadth First Search is based on queue and Time Complexity: O(V+E) where V is number of vertices in the graph and E is number of edges in the graph. Depth First Search is based on stack and Time Complexity: O(V+E) where V is number of vertices in the graph and E is number of edges in the graph. www.cuidol.in Unit-4(MCA 632) All right are reserved with CU-IDOL

Tree 12 Binary Tree is a special data structure used for data storage purposes. A binary tree has a special condition that each node can have a maximum of two children. www.cuidol.in Unit-4(MCA 632) All right are reserved with CU-IDOL

Tree 13 Binary Search tree exhibits a special behavior. A node's left child must have a value less than its parent's value and the node's right child must have a value greater than its parent value. www.cuidol.in Unit-4(MCA 632) All right are reserved with CU-IDOL

Tree 14 BST Basic Operations The basic operations that can be performed on a binary search tree data structure, are the following : Insert − Inserts an element in a tree/create a tree. Search − Searches an element in a tree. Preorder Traversal − Traverses a tree in a pre-order manner. Inorder Traversal − Traverses a tree in an in-order manner. Postorder Traversal − Traverses a tree in a post-order manner. www.cuidol.in Unit-4(MCA 632) All right are reserved with CU-IDOL

Tree 15 All right are reserved with CU-IDOL Depth First Traversals: (a) Inorder (Left, Root, Right) : 4 2 5 1 3 (b) Preorder (Root, Left, Right) : 1 2 4 5 3 (c) Postorder (Left, Right, Root) : 4 5 2 3 1 Breadth First or Level Order Traversal : 1 2 3 4 5 www.cuidol.in Unit-4(MCA 632)

Set 16 A set is a collection of objects (called members or elements) that is regarded as being a single object. To indicate that an object x is a member of a set A one writes x ∊ A, while x ∉ A indicates that x is not a member of A. The empty (or void, or null) set, symbolized by {} or Ø, contains no elements at all. Nonetheless, it has the status of being a set. A set A is called a subset of a set B (symbolized by A ⊆ B) if all the members of A are also members of B. For example, any set is a subset of itself, and Ø is a subset of any set. If both A ⊆ B and B ⊆ A, then A and Bhave exactly the same members. Part of the set concept is that in this case A = B; that is, A and B are the same set. www.cuidol.in Unit-4(MCA 632) All right are reserved with CU-IDOL

Set 17 Operations on sets The symbol ∪ is employed to denote the union of two sets. Thus, the set A ∪ B—read “A union B” or “the union of A and B”—is defined as the set that consists of all elements belonging to either set A or set B (or both). The intersection operation is denoted by the symbol ∩. The set A ∩ B—read “A intersection B” or “the intersection of A and B”—is defined as the set composed of all elements that belong to both A and B. The Cartesian product of two sets A and B, denoted by A × B, is defined as the set consisting of all ordered pairs (a, b) for which a ∊ A and b ∊ B. For example, if A = {x, y} and B = {3, 6, 9}, then A × B = {(x, 3), (x, 6), (x, 9), (y, 3), (y, 6), (y, 9)}. www.cuidol.in Unit-4(MCA 632) All right are reserved with CU-IDOL

Dictionaries 18 A dictionary is a general-purpose data structure for storing a group of objects. A dictionary has a set of keys and each key has a single associated value. When presented with a key, the dictionary will return the associated value. For example, the results of a classroom test could be represented as a dictionary with pupil's names as keys and their scores as the values: results = {'Detra' : 17, 'Nova' : 84, 'Charley' : 22, 'Hwa' : 75, 'Roxann' : 92, 'Elsa' : 29} Instead of using the numerical index of the data, we can use the dictionary names to return values: >>> results['Nova'] 84 >>> results['Elsa'] 29 A dictionary is also called a hash, a map, a hashmap in different programming languages www.cuidol.in Unit-4(MCA 632) All right are reserved with CU-IDOL

Dictionaries 19 Main operations on dictionaries Dictionaries typically support several operations: retrieve a value (depending on language, attempting to retrieve a missing key may give a default value or throw an exception) insert or update a value (typically, if the key does not exist in the dictionary, the key-value pair is inserted; if the key already exists, its corresponding value is overwritten with the new one) remove a key-value pair test for existence of a key www.cuidol.in Unit-4(MCA 632) All right are reserved with CU-IDOL

MULTIPLE CHOICE QUESTIONES 1. When does top value of the stack changes? 20 A) Before deletion C) At the time of deletion B) While checking underflow D) After deletion 2. In the ----------traversal we process first root node. A) depth first B) breadth first C) Preorder D) Postorder 3. -------Is a pile in which items are added at one end and removed from the other. A) Stack B) Queue C) List D) Array 4. A queue data-structure can be used for; B) recursion A )expression parsing D) all of the above C) Resource allocation 5. Which data structure is used in breadth first search of a graph to hold nodes? A).Stack B) Queue C) Array D) List Answers: 1.c) 2.c) 3.b) 4.d) 5.b) www.cuidol.in Unit-4(MCA 632) All right are reserved with CU-IDOL

SUMMARY 21 This presentation includes unit 4 for Design and Analysis of Algorithms. Unit 4 has stack, queue, graph, sets and dictionaries. Stack and queue are two basic data structures of DAA. One is used as LIFO and another one is FIFO. Further graph and tree are used for non linear data structures. Sets and dictionaries are some types of structures which are used for data organisation in key value pair and comma separated values. www.cuidol.in Unit-4(MCA 632) All right are reserved with CU-IDOL

FREQUENTLY ASKED QUESTION 22 Q1. Differentiate between stack and queue. Ans. Stack is LIFO based and Queue is FIFO based. (For Further details please refer to the SLM) Q2. Define set. Ans. Set is a collection of elements in comma separated values format. (For Further details please refer to the SLM) Q3. Discuss about linear graph and trees. Ans. Graphs and trees are examples of non linear data structures. They are having nodes, edges and branches. (For Further details please refer to the SLM) www.cuidol.in Unit-4(MCA 632) All right are reserved with CU-IDOL

REFRENCES 23 1) Data Structures and Algorithms made easy By Narasimha Karumanchi. 2) The Algorithm Design Manual, 2nd Edition by Steven S Skiena 3) Fundamentals of Computer Algorithms - Horowitz and Sahani www.cuidol.in Unit-4(MCA 632) All right are reserved with CU-IDOL

24 THANK YOU www.cuidol.in Unit-4(MCA 632) All right are reserved with CU-IDOL