ADVANCED DATA STRUCTURES LAB - WordPress

Faculty of Engineering1819202122232425262728293031Savitribai Phule Pune University, PuneGiven sequence k k1 k2 kn of n sorted keys, with a search probability pi for eachkey ki . Build the Binary search tree that has the least search cost given the access probabilityfor each key.A Dictionary stores keywords & its meanings. Provide facility for adding new keywords,deleting keywords, updating values of any entry. Provide facility to display whole data sortedin ascending/ Descending order. Also find how many maximum comparisons may require forfinding any keyword. Use Height balance tree and find the complexity for finding a keywordGroup ETo create ADT that implements the SET concept.a. Add (newElement) -Place a value into the set b. Remove (element) Remove the valuec. Contains (element) Return true if element is in collectiond. Size () Return number of values in collection Iterator () Return an iterator used to loop overcollectione. Intersection of two sets, f. Union of two sets, g. Difference between two sets, h. SubsetRead the marks obtained by students of second year in an online examination of particularsubject. Find out maximum and minimum marks obtained in that subject. Use heap datastructure. Analyze the algorithm.Group FAssume we have two input and two output tapes to perform the sorting. The internal memorycan hold and sort m records at a time. Write a program in java for external sorting. Find outtime complexity.Department maintains a student information. The file contains roll number, name, divisionand address. Allow user to add, delete information of student. Display information ofparticular employee. If record of student does not exist an appropriate message is displayed.If it is, then the system displays the student details. Use sequential file to main the data.Company maintains employee information as employee ID, name, designation and salary.Allow user to add, delete information of employee. Display information of particularemployee. If employee does not exist an appropriate message is displayed. If it is, then thesystem displays the employee details. Use index sequential file to maintain the data.Group GImplement the Heap/Shell sort algorithm implemented in Java demonstrating heap/shell datastructure with modularity of programming language.Any application defining scope of Formal parameter, Global parameter, Local parameteraccessing mechanism and also relevance to private, public and protected access. Write a Javaprogram which demonstrates the scope rules of the programming mechanism.Write a Java program which will demonstrate a concept of Interfaces and packages: In thisassignment design and use of customized interfaces and packages for a specific applicationare expected.Write a Java program which will demonstrate a concept of cohesion and coupling of thevarious modules in the program.Write a program on template and exception handling in Java: in this assignment multipletemplates are to be designed as a pattern and these patterns to be used to take decisions.Write a Java program for the implementation of different data structures using JAVAcollection libraries (Standard toolkit library): at least 5 data structures are used to design asuitable application.Design a mini project using JAVA which will use the different data structure with or withoutJava collection library and show the use of specific data structure on the efficiency(performance) of the code.Syllabus for Second Year of Computer Engineering#57/65

Experiment No 1Title:A book consists of chapters, chapters consist of sections and sections consist of subsections.Construct a tree and print the nodes. Find the time and space requirements of your method.Objectives:1. To understand concept of tree data structure2. To understand concept & features of object oriented programming.Learning Objectives: To understand concept of class To understand concept & features of object oriented programming. To understand concept of tree data structure.Learning Outcome: Define class for structures using Object Oriented features. Analyze tree data structure.Theory:Introduction to Tree:Definition:A tree T is a set of nodes storing elements such that the nodes have a parent-child relationshipthat satisfies the following if T is not empty, T has a special tree called the root that has no parent each node v of T different than the root has a unique parent node w; each node with parent w isa child of wRecursive definition T is either empty or consists of a node r (the root) and a possibly empty set of trees whose roots are the childrenof rTree is a widely-used data structure that emulates a tree structure with a set of linkednodes. The tree graphicaly is represented most commonly as on Picture 1. The circles are thenodes and the edges are the links between them.

Trees are usualy used to store and represent data in some hierarhical order. The data arestored in the nodes, from which the tree is consisted of.A node may contain a value or a condition or represent a separate data structure or a treeof its own. Each node in a tree has zero or more child nodes, which are one level lower in thetree hierarchy (by convention, trees grow down, not up as they do in nature). A node that has achild is called the child's parent node (or ancestor node, or superior). A node has at most oneparent. A node that has no childs is called a leaf, and that node is of course at the bottommostlevel of the tree. The height of a node is the length of the longest path to a leaf from that node.The height of the root is the height of the tree. In other words, the "height" of tree is the "numberof levels" in the tree. Or more formaly, the height of a tree is defined as follows:1. The height of a tree with no elements is 02. The height of a tree with 1 element is 13. The height of a tree with 1 element is equal to 1 the height of its tallest subtree.The depth of a node is the length of the path to its root (i.e., its root path). Every childnode is always one level lower than his parent.The topmost node in a tree is called the root node. Being the topmost node, the root nodewill not have parents. It is the node at which operations on the tree commonly begin (althoughsome algorithms begin with the leaf nodes and work up ending at the root). All other nodes canbe reached from it by following edges or links. (In the formal definition, a path from a root to anode, for each different node is always unique). In diagrams, it is typically drawn at the top.In some trees, such as heaps, the root node has special properties.A subtree is a portion of a tree data structure that can be viewed as a complete tree initself. Any node in a tree T, together with all the nodes below his height, that are reachable fromthe node, comprise a subtree of T. The subtree corresponding to the root node is the entire tree;the subtree corresponding to any other node is called a proper subtree (in analogy to the termproper subset).Every node in a tree can be seen as the root node of the subtree rooted at that node.

Fig1. An example of a treeAn internal node or inner node is any node of a tree that has child nodes and is thus not aleaf node.There are two basic types of trees. In an unordered tree, a tree is a tree in a purelystructural sense — that is to say, given a node, there is no order for the children of that node. Atree on which an order is imposed — for example, by assigning different natural numbers to eachchild of each node — is called an ordered tree, and data structures built on them are calledordered tree data structures. Ordered trees are by far the most common form of tree datastructure. Binary search trees are one kind of ordered tree.Important TermsFollowing are the important terms with respect to tree. Path Path refers to the sequence of nodes along the edges of a tree.Root The node at the top of the tree is called root. There is only one root per tree andone path from the root node to any node.Parent Any node except the root node has one edge upward to a node called parent.Child The node below a given node connected by its edge downward is called its childnode.Leaf The node which does not have any child node is called the leaf node.Subtree Subtree represents the descendants of a node.Visiting Visiting refers to checking the value of a node when control is on the node.Traversing Traversing means passing through nodes in a specific order.Levels Level of a node represents the generation of a node. If the root node is at level0, then its next child node is at level 1, its grandchild is at level 2, and so on.

keys Key represents a value of a node based on which a search operation is to becarried out for a node.Advantages of treesTrees are so useful and frequently used, because they have some very serious advantages: Trees reflect structural relationships in the dataTrees are used to represent hierarchiesTrees provide an efficient insertion and searchingTrees are very flexible data, allowing to move subtrees around with minumum effortFor this assignment we are considering the tree as follows.Software Required: g / gcc compiler- / 64 bit Fedora, eclipse IDEInput: Book name & its number of sections and subsections along with name.Output: Formation of tree structure for book and its sections.Conclusion: This program gives us the knowledge tree data structure.

OUTCOMEUpon completion Students will be able to:ELO1: Learn object oriented Programming features.ELO2: Understand & implement tree data structure.Questions asked in university exam.1. What is class, object and data structure?2. What is tree data structure?3. Explain different types of tree?

Experiment No: 2Aim: To illustrate the various Binary Tree functions.Problem Statement : For given expression eg. a-b*c-d/e f construct inorder sequence and traverse itusing postorder traversal(non recursive).Learning Objectives:To understand concept of Tree & Binary Tree.To analyze the working of various Tree operations.Learning Outcome: Students will be able to use various set of operations on Binarysearch.Theory:TreeTree represents the nodes connected by edges also a class of graphs that is acyclic is termed astrees. Let us now discuss an important class of graphs called trees and its associated terminology.Trees are useful in describing any structure that involves hierarchy. Familiar examples of suchstructures are family trees, the hierarchy of positions in an organization, and so on.Binary TreeA binary tree is made of nodes, where each node contains a "left" reference, a"right" reference, and a data element. The topmost node in the tree is called the root.Every node (excluding a root) in a tree is connected by a directed edge from exactly one othernode. This node is called a parent. On the other hand, each node can be connected to arbitrary numberof nodes, called children. Nodes with no children are called leaves, or external nodes. Nodes which arenot leaves are called internal nodes. Nodes with the same parent are called siblings.

Insert OperationThe very first insertion creates the tree. Afterwards, whenever an element is to be inserted, firstlocate its proper location. Start searching from the root node, then if the data is less than the key value,search for the empty location in the left subtree and insert the data. Otherwise, search for the emptylocation in the right subtree and insert the data.TraversalsA traversal is a process that visits all the nodes in the tree. Since a tree is a nonlinear datastructure, there is no unique traversal. We will consider several traversal algorithms with we groupin the following two kinds depth-first traversal breadth-first traversal There are three different types of depth-first traversals, : PreOrder traversal - visit the parent first and then left and right children; InOrder traversal - visit the left child, then the parent and the right child; PostOrder traversal - visit left child, then the right child and then the parent; There is only one kind of breadth-first traversal--the level order traversal. This traversal visits nodesby levels from top to bottom and from left to right. As an example consider the following tree and itsfour traversals:PreOrder - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3InOrder - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11PostOrder - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8LevelOrder - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2

Algorithm: Algorithm to insert a node :Step 1 - Search for the node whose child node is to be inserted. This is a node at some level i,and a node is to be inserted at the level i 1 as either its left child or right child. This is thenode after which the insertion is to be made.Step 2 - Link a new node to the node that becomes its parent node, that is, either the Lchild orthe Rchild.Algorithm to traverse a tree : Inorder traversalUntil all nodes are traversed Step 1 Recursively traverse left subtree.Step 2 Visit root node.Step 3 Recursively traverse right subtree. PreordertraversalUntil all nodes are traversed Step 1 Visit root node.Step 2 Recursively traverse left subtree.Step 3 Recursively traverse right subtree. PostordertraversalUntil all nodes are traversed Step 1 Recursively traverse left subtree.Step 2 Recursively traverse right subtree.Step 3 Visit root node.Algorithm to copy one tree into another tree :Step 1 – if (Root Null)Then return NullStep 2 Tmp new TreeNodeStep 3 – Tmp- Lchild TreeCopy(Root Lchild);Step4–Tmp- Rchild TreeCopy(Root- Rchild); Step 5 – Tmp-Data Root- Data;Then returnTmp;

Software required: g / gcc compiler- / 64 bit fedora.OutcomeLearn object oriented programming features.Understand & implement different operations on tree & binary tree.Conclusion : Thus we have studied the implementation of various Binary tree operations

Experiment No. 02Aim: To illustrate the concept of graph.Problem Statement :Write a function to get the number of vertices in an undirected graph and its edges. You mayassume that no edge is input twice.i. Use adjacency list representation of the graph and find runtime of the functionii. Use adjacency matrix representation of the graph and find runtime of the functionLearning Objectives:To understand directed and undirected graph.To implement program to represent graph using adjacency matrix and list.Learning Outcome:Student able to implement program for graph representation.Theory:Graph is a data structure that consists of following two components:1. A finite set of vertices also called as nodes.2. A finite set of ordered pair of the form (u, v) called as edge. The pair is ordered because (u, v)is not same as (v, u) in case of directed graph(di-graph). The pair of form (u, v) indicates thatthere is an edge from vertex u to vertex v. The edges may contain weight/value/cost.Graphs are used to represent many real life applications: Graphs are used to represent networks.The networks may include paths in a city or telephone network or circuit network. Graphs are

also used in social networks like linkedIn, facebook. For example, in facebook, each person isrepresented with a vertex(or node). Each node is a structure and contains information like personid, name, gender and locale. See this for more applications of graph.Following is an example undirected graph with 5 vertices.Following two are the most commonly used representations of graph.1. Adjacency Matrix2. Adjacency ListThere are other representations also like, Incidence Matrix and Incidence List. The choice of thegraph representation is situation specific. It totally depends on the type of operations to beperformed and ease of use.Adjacency Matrix:Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Letthe 2D array be adj[][], a slot adj[i][j] 1 indicates that there is an edge from vertex i to vertex j.Adjacency matrix for undirected graph is always symmetric. Adjacency Matrix is also used torepresent weighted graphs. If adj[i][j] w, then there is an edge from vertex i to vertex j withweight w.The adjacency matrix for the above example graph is:Adjacency Matrix Representation

Pros: Representation is easier to implement and follow. Removing an edge takes O(1) time.Queries like whether there is an edge from vertex ‘u’ to vertex ‘v’ are efficient and can be doneO(1).Cons: Consumes more space O(V 2). Even if the graph is sparse(contains less number of edges),it consumes the same space. Adding a vertex is O(V 2) time.Adjacency List:An array of linked lists is used. Size of the array is equal to number of vertices. Let the array bearray[]. An entry array[i] represents the linked list of vertices adjacent to the ith vertex. Thisrepresentation can also be used to represent a weighted graph. The weights of edges can bestored in nodes of linked lists. Following is adjacency list representation of the above graph.Pros: Saves space O( V E ) . In the worst case, there can be C(V, 2) number of edges in a graphthus consuming O(V 2) space. Adding a vertex is easier.Cons: Queries like whether there is an edge from vertex u to vertex v are not efficient and can bedone O(V).

Conclusion:Student implemented program for graph presentation in adjacency matrix and list.Questions1. An undirected graph having n edges, then find out no. Of vertices that graph have?2. Define data structure to represent graph.3. What are the methods to display graph.4. Where you apply directed and undirected grap?5. What is complexity of your graph to represent it in adjacency matrix and list?

Experiment No 4Title:There are flight paths between cities. If there is a flight between city A and city B thenthere is an edge between the cities. The cost of the edge can be the time that flight take to reachcity B from A, or the amount of fuel used for the journey. Represent this as a graph. The nodecan be represented by airport name or name of the city. Use adjacency list representation of thegraph or use adjacency matrix representation of the graph. Justify the storage representationused.Objectives:1. To understand concept of Graph data structure2. To understand concept of representation of graph.Learning Objectives: To understand concept of Graph data structure To understand concept of representation of graph.Learning Outcome: Define class for graph using Object Oriented features. Analyze working of functions.Theory:Graphs are the most general data structure. They are also commonly used data structures.Graph definitions: A non-linear data structure consisting of nodes and links between nodes.

Undirected graph definition: An undirected graph is a set of nodes and a set of links between the nodes.Each node is called a vertex, each link is called an edge, and each edge connects twovertices.The order of the two connected vertices is unimportant.An undirected graph is a finite set of vertices together with a finite set of edges. Both setsmight be empty, which is called the empty graph.Graph Implementation:Different kinds of graphs require different kinds of implementations, but the fundamentalconcepts of all graph implementations are similar. We'll look at several representations for oneparticular kind of graph: directed graphs in which loops are allowed.Representing Graphs with an Adjacency MatrixFig: Graph and adjacency matrixDefinition: An adjacency matrix is a square grid of true/false values that represent the edges of agraph.

If the graph contains n vertices, then the grid contains n rows and n columns.For two vertex numbers i and j, the component at row i and column j is true if there is anedge from vertex i to vertex j; otherwise, the component is false.We can use a two-dimensional array to store an adjacency matrix:boolean[][] adjacent new boolean[4][4];Once the adjacency matrix has been set, an application can examine locations of the matrix todetermine which edges are present and which are missing.Representing Graphs with Edge ListsFig: Graph and adjacency list for each nodeDefinition: A directed graph with n vertices can be represented by n different linked lists.List number i provides the connections for vertex i.For each entry j in list number i, there is an edge from i to j.Loops and multiple edges could be allowed.Representing Graphs with Edge SetsTo represent a graph with n vertices, we can declare an array of n sets of integers. For example:IntSet[] connections new IntSet[10]; // 10 verticesA set such as connections[i] contains the vertex numbers of a

a short route from S to F or a route having one distance unit longer than the minimal distance. Two routes from S to F are considered different if there is at least one road from a city A to a city B which is part of one route, but not of the other route. 13 Consider the scheduling problem