DS LAB (II) Assignment 1 Binary Search Tree and Traversals

Binary Search Tree and Traversals

It is a binary tree with the property that the value in a node is greater than any value in a node's left sub-tree and less than any value in the node's right sub-tree.

The Operations on Binary Search Tree are:

init (T)	creates an empty Binary search tree by initializing T to NULL
insert (T, x)	inserts the value x in the proper position in the Binary search tree
search (T, x)	searches if the value x is present in the search tree
inorder (T)	displays the node using inorder traversal of binary search tree
postorder (T)	displays the node using postorder traversal of binary search tree
preorder (T)	displays the node using preorder traversal of binary search tree
delete(T, x)	Deletes node x from binary search tree

Set A

a) Implement a Binary search tree (BST) library (btree.h) with operations – create, search, insert, inorder, preorder and postorder. Write a menu driven program that performs the above operations.

b) Write a program which uses binary search tree library and counts the total nodes and total leaf nodes in the tree.
int count(T) – returns the total number of nodes from BST
int countLeaf(T) – returns the total number of leaf nodes from BST 

Set B

a) Write a C program which uses Binary search tree library and implements following function with recursion:

1. T copy(T) – create another BST which is exact copy of BST which is passed as parameter.

2. int compare(T1, T2) – compares two binary search trees and returns 1 if they are equal and 0 otherwise.

Set C
a) Write a C program which uses Binary search tree library and implements following two functions: 

int sumodd(T) – returnssum of all odd numbers from BST 

int sumeven(T) – returnssum of all even numbers from BST 

mirror(T) – converts given tree into its mirror image

Read More

DS LAB(II) Assignment 2 Binary Tree Applications

Binary Tree Applications

 

Set A

a) Write a C program which uses Binary search tree library and displays nodes at each level, count of node at each level and total levels in the tree.

 

Set B

a) Write a program to sort n randomly generated elements using Heapsort method.

Read More

DS LAB (II) Assignment 3 Graph as Adjacency Matrix

Graph as Adjacency Matrix

Set A
a) Write a C program that accepts the vertices and edges of a graph and stores it as an adjacency matrix. Display the adjacency matrix.
 

b) Write a C program that accepts the vertices and edges of a graph and store it as an adjacency matrix. Implement functions to print indegree, outdegree and total degree of all vertices of graph.
 

Set B
a) Write a C program that accepts the vertices and edges of a graph and store it as an adjacency matrix. Implement function to traverse the graph using Breadth First Search (BFS) traversal.

b) Write a C program that accepts the vertices and edges of a graph and store it as an adjacency matrix. Implement function to traverse the graph using Depth First Search (BFS) traversal.

Read More

DS LAB (II) Assignment 4 Graph as Adjacency List

Graph as Adjacency List

 

Set A
a) Write a C program that accepts the vertices and edges of a graph. Create adjacency list and display the adjacency list.

b) Write a C program that accepts the vertices and edges of a graph. Create adjacency list. Implement functions to print indegree, outdegree and total degree of all vertex of graph.
 

Set B
a) Write a C program that accepts the vertices and edges of a graph and store it as an adjacency list. Implement function to traverse the graph using Breadth First Search (BFS) traversal.

b) Write a C program that accepts the vertices and edges of a graph and store it as an adjacency list. Implement function to traverse the graph using Depth First Search (BFS) traversal.

Read More

DS-(I) Assignment 9: Linear Queue and Circular queue

 

Set A.

a)Implement a linear queue library (st_queue.h) of integers using a static implementation of the queue and implementing the above six operations. Write a program that includes queue library and calls different queue operations.

b)Implement a circular queue library (cir_queue.h) of integers using a dynamic (circular linked list) implementation of the queue and implementing the above five operations. Write a menu driven program that includes queue library and calls different queue operations.

Read More

DS-(I) Assignment 8: Applications of Stack

 

 Set A.

a)Write a program that reverses a string of characters. The function should use a stack library (cststack.h) of stack of characters using a static implementation of the stack.

 

b)Write a program to convert an infix expression of the form (a*(b+c)*((d-a)/b)) into its equivalent postfix notation. Consider usual precedence’s of operators. Use stack library of stack of characters using static implementation.

 

 Set B.

a)A postfix expression of the form ab+cd-*ab/ is to be evaluated after accepting the values of a, b, c and d. The value should be accepted only once and the same value is to be used for repeated occurrence of same symbol in the expression. Formulate the problem and write a C program to solve the problem by using stack.

 

b)Write a program that checks whether a string of characters is palindrome or not. The function should use a stack library (cststack.h) of stack of characters using a static implementation of the stack.

 

Read More

DS-(I) Assignment 7: Stack

 

 

Set A.

a) Implement a stack library (ststack.h) of integers using a static implementation of the stack and implementing the above six operations. Write a driver program that includes stack library and calls different stack operations.

 

b) Implement a stack library (dystack.h) of integers using a dynamic (linked list) implementation of the stack and implementing the above five operations. Write a driver program that includes stack library and calls different stack operations.

 

Set B.

a) Write a program to check whether the contents of two stacks are identical. Use stack library to perform basic stack operations. Neither stack should be changed.

 

b) Write a program that copies the contents of one stack into another. Use stack library to perform basic stack operations. The order of two stacks must be identical.(Hint: Use a temporary stack to preserve the order).

 

Read More

DS-(I) Assignment 6: Linked List Applications

 

Set A.

1)Write a program that merges two ordered linked lists into third new list. When two lists are merged the data in the resulting list are also ordered. The two original lists should be left unchanged. That is merged list should be new one. Use linked implementation.

 

2)Write a program that adds two single variable polynomials. Each polynomial should be represented as a list with linked list implementation.

 

Set B.

1)Write a program that sorts the elements of linked list using any of sorting technique.

 

2)Write a program that multiply two single variable polynomials. Each polynomial should be represented as a list with linked list implementation.

 

Read More

DS-(I) Assignment 5: Doubly Linked List – Dynamic Implementation

 

Set A.

a) Implement a list library (doublylist.h) for a doubly linked list with the above operations. Write a menu driven driver program to call the operations append, insert, delete specific node, delete at position, search, display.

 

b) Implement a list library (doublylist.h) for a doubly linked list. Create a linked list, reverse it and display reversed linked list.

 

Set B.

a) There are lists where insertion should ensure the ordering of data elements. Since the elements are in ascending order the search can terminate once equal or greater element is found. Implement a doubly linked list of ordered integers (ascending / descending) with insert, search and display operations.

 

b) There are lists where new elements are always appended at the end of the list. The list can be implemented as a circular list with the external pointer pointing to the last element of the list. Implement doubly linked circular list of integers with append and display operations. The operation append(L, n), appends to the end of the list, n integers either accepted from user or randomly generated.

 

Read More

DS-(I) Assignment 4: Singly Linked List – Dynamic Implementation

 

Set A.

a) Implement a list library (singlylist.h) for a singly linked list with the above six operations. Write a menu driven driver program to call the operations.

 

b) Implement a list library (singlylist.h) for a singly linked list. Create a linked list, reverse it and display reversed linked list.

 

Set B.

a) There are lists where insertion should ensure the ordering of data elements. Since the elements are in ascending order the search can terminate once equal or greater element is found. Implement a singly linked list of ordered integers (ascending /descending) with insert, search and display operations.

 

b) There are lists where new elements are always appended at the end of the list. The list can be implemented as a circular list with the external pointer pointing to the last element of the list. Implement singly linked circular list of integers with append and display operations. The operation append(L, n), appends to the end of the list, n integers either accepted from user or randomly generated.

 

Read More

DS-(I) Assignment 3: Sorting Algorithms –Counting Sort, Merge Sort, Quick Sort

 

Set A.

a) Sort a random array of n integers (accept the value of n from user) in ascending order by using recursive Counting sort algorithm.

 

b)Sort a random array of n integers (accept the value of n from user) in ascending order by using a recursive Merge sort algorithm.

 

c) Sort a random array of n integers (create a random array of n integers) in ascending order by using recursive Quick sort algorithm.

Read More

DS-(I) Assignment 2: Sorting Algorithms – Bubble Sort, Insertion Sort, Selection Sort

 

Set A.

a) Sort a random array of n integers (accept the value of n from user) in ascending order by using bubble sort algorithm.

 

b) Sort a random array of n integers (create a random array of n integers) in ascending order by using insertion sort algorithm.

 

c) Sort a random array of n integers (accept the value of n from user) in ascending order by using selection sort algorithm.

 

Set B.

a) Read the data from the file “employee.txt” and sort on age using 

• Bubble sort
• Insertion sort 
• Selection sort

b) Read the data from the file “employee.txt” and sort on names in alphabetical order (use strcmp) using 

• Bubble sort
• Insertion sort 
• Selection sort

Read More

DS-(I) Assignment 1: Searching Algorithms

 

Set A.

a) Create a random array of n integers. Accept a value x from user and use linear search algorithm to check whether the number is present in the array or not and output the position if the number is present.

 

b) Accept n values in array from user. Accept a value x from user and use sentinel linear search algorithm to check whether the number is present in the array or not and output the position if the number is present.

 

c) Accept n sorted values in array from user. Accept a value x from user and use binary search algorithm to check whether the number is present in sorted array or not and output the position if the number is present.

Set B.

a) Read the data from file 'cities.txt' containing names of cities and their STD codes. Accept a name of the city from user and use linear search algorithm to check whether the name is present in the file and output the STD code, otherwise output “city not in the list”.

 

b) Read the data from file 'cities.txt' containing names of cities and their STD codes. Accept a name of the city from user and use sentinel linear search algorithm to check whether the name is present in the file and output the STD code, otherwise output “city not in the list”.

 

c) Read the data from file ‘sortedcities.txt’ containing sorted names of cities and their STD codes. Accept a name of the city from user and use binary search algorithm to check whether the name is present in the file and output the STD code, otherwise output “city not in the list”.

Read More