Scribd
Upload
38 views3 pages

DSA Assignment

The assignment for the DSA course at the University of Management and Technology requires handwritten submissions only, covering various data structures including Binary Search Trees, AVL Trees, Min-Max Heaps, and Binary Trees. Students must perform specific tasks related to their university ID, phone number, and CNIC, including coding, diagramming, and explanations. Plagiarism is strictly prohibited, and neatness and clarity are emphasized in the submissions.

Uploaded by

shehzaibmirza428
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
38 views3 pages

DSA Assignment

The assignment for the DSA course at the University of Management and Technology requires handwritten submissions only, covering various data structures including Binary Search Trees, AVL Trees, Min-Max Heaps, and Binary Trees. Students must perform specific tasks related to their university ID, phone number, and CNIC, including coding, diagramming, and explanations. Plagiarism is strictly prohibited, and neatness and clarity are emphasized in the submissions.

Uploaded by

shehzaibmirza428
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

University of Management and Technology,

Lahore Campus

Assignment – Spring 2025


Deadline:
Course Name: DSA Course Code: CS458 June 26, 2025
Course
Dr. Sadaf Program Name BSAI
Instructor/s:
Jabeen

Instructions:

 Handwritten Submission Only:


All code, diagrams, dry runs, and explanations must be written by hand. Typed or printed
submissions will not be accepted.
 Every code snippet must be followed by a brief explanation and a dry run on sample input.
 Tree/Heap structures must be represented clearly with diagrams at each major step (insertions,
deletions, rotations, etc.).
 Ensure neat handwriting, proper indentation in code, and labeled diagrams. Use headings and
subheadings for clarity
 Submissions must reflect your own understanding. Plagiarism or copied work will receive zero
marks.

Question 1: BST from Your University ID

(Use your university ID e.g., f20211223456)

Tasks:

1. Extract digits from your ID and insert into a Binary Search Tree
2. Implement code for:

 Insert function
 Inorder, Preorder, Postorder Traversals
 Count leaf nodes and print them

3. Show tree diagram after full insertion

Bonus: Identify if your BST is left-skewed, right-skewed, or balanced

1|Page
Question 2: AVL Tree from Phone Number

(Use your full 11-digit phone number e.g., 03124567890)

Tasks:

1. Insert digits into an AVL Tree, maintaining balance


2. Perform:

 Necessary rotations (LL, RR, LR, RL) with diagrams


 Function to find height of any given node
 Count total rotations performed

3. Search any 3 digits and print their depth

Bonus: Highlight rotations in tree diagrams using color pens

Question 3: Min-Max Heap from CNIC Number

(Use your full CNIC e.g., 35201-1234567-8)

Tasks:

1. Extract digits → [3,5,2,0,1,1,2,3,4,5,6,7,8]


2. Build:

1. Min Heap
2. Max Heap (using reverse of above)

3. Code for:

1. Heapify function
2. Delete root
3. Insert 2 extra values (last 2 digits of CNIC)

4. Show diagrams after each operation

Explain why Min Heap is useful in priority scheduling

Question 4: File System using Binary Tree

(Use first 6 digits of your CNIC as folder names)

2|Page
Tasks:

1. Each digit becomes a folder (e.g., 352011 → Folder_3 → Folder_5 → Folder_2...)


2. Create a binary tree structure using these folders
3. Implement:

1. Recursive DFS to search a folder by name


2. BFS to print all folders
3. Path trace function (root → folder)

Diagram coloring:

 Root: Blue
 Leaf: Red
 Internal Nodes: Green

Write down memory calculation: Assume each node uses 4 bytes

3|Page

You might also like