Name: Tirthraj Mahajan
Class: SE-02
Roll No: 21242
College: PICT, Pune

Assignments Index

1. Binary Tree
2. Binary Search Tree
3. Threaded Binary Search Tree
4. Hash Table Implementation
5. Dictionary ADT Implementation using Open Hashing
6. Graph using Adjacency List
7. Minimum Spanning Tree
8. Optimal Binary Search Tree
9. AVL Tree
10. Heap Data Structure and Heap Sort
11. Sequential File
12. Direct Access File

---

Assignment 1 - Binary Tree

Problem Statement

Beginning with an empty binary tree, Construct binary tree by inserting
the values in the order given. After constructing a binary tree perform
following operations on it-
1 Perform in order / pre order and post order traversal
2 Change a tree so that the roles of the left and right pointers are
swapped at every node
3 Find the height of tree
4 Copy this tree to another [operator=]
5 Count number of leaves, number of internal nodes.
6 Erase all nodes in a binary tree.
(implement both recursive and non-recursive methods)

---

Assignment 2 - Binary Search Tree

Problem Statement

Beginning with an empty binary search tree. Construct the binary
search tree by inserting the values in given order. After constructing
binary search tree perform following operations 1) Insert a new node 2)
Find numbers of node in longest path 3) Minimum and maximum data
value found in tree 4) Change a tree so that the roles of the left and
right pointers are swapped at every node 5)Search an element

---

Assignment 3 - Threaded Binary Search Tree

Problem Statement

Create an inordered threaded binary search tree. Perform inorder,
preorder traversals without recursion and deletion of a node. Analyze
time and space complexity of the algorithm.

---

Assignment 4 - Hash Table Implementation

Problem Statement

Consider telephone book database of N clients. Make use of a hash
table implementation to quickly look up client’s telephone number.
Make use of two collision handling techniques and compare them using
number of comparisons required to find a set of telephone numbers
(Note: Use linear probing with replacement and without replacement)

---

Assignment 5 - Dictionary ADT Implementation using Open Hashing

Problem Statement

Implement all the functions of a dictionary (ADT) using open
hashing technique: separate chaining using linked list Data: Set of
(key, value) pairs, Keys are mapped to values, Keys must be
comparable, and Keys must be unique. Standard Operations: Insert
(key, value), Find(key), Delete(key)

---

Assignment 6 - Graph using Adjacency List

Problem Statement

Represent a given graph using adjacency list to perform DFS and BFS.
Use the map of the area around the college as the graph. Identify the
prominent landmarks as nodes and perform DFS and BFS on that.

---

Assignment 7 - Minimum Spanning Tree

Problem Statement

To write a program for Graph creation and find its minimum cost using
Prim’s or Kruskal’s algorithm.

You have a business with several offices; you want to lease phone lines
to connect them up with each other and the phone company charges
different amounts of money to connect different pairs of cities. 
You want a set of lines that connects all your offices with a minimum total
cost. Solve the problem by suggesting appropriate data structures.

---

Assignment 8 - Optimal Binary Search Tree

Problem Statement

Given sequence k = k1 <k2 < … <kn of n sorted keys, with a successful and unsuccessful 
search probability pi and qi for each key ki. Build the Binary search tree that has the least 
search cost given the access probability for each key

---

Assignment 9 - AVL Tree

Problem Statement

A Dictionary stores keywords and its meanings. Provide facility for adding new keywords. 
Provide facility to display whole data sorted in ascending/ Descending order. Also find 
how many maximum comparisons may require for finding any keyword. 

Use Height balanced (AVL) tree.

---

Assignment 10 - Heap Data Structure and Heap Sort

Problem Statement

Read the marks obtained by students of second year in an online examination of particular 
subject. Find out minimum/maximum marks obtained in that subject. Use heap data structure. 
Analyze the algorithm.

OR

Implement the Heap sort algorithm for demonstrating heap data structure with modularity 
of programming language (consider integer data)

---

Assignment 11 - Sequential File

Problem Statement

Department maintains a student information. The file contains roll
number, name, division and address. Allow user to add, delete
information of student. Display information of particular student. 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 maintain the data.

---

Assignment 12 - Direct Access File

Problem Statement

Implementation of a direct access file -Insertion and deletion of a
record from a Direct Access File.

---

All the assignments in this repository are implemented by me. If there are any mistakes/suggestions do let me know.
Thanks!