EX NO:1

Write a program to implement the List ADT using arrays and linked lists.

AIM:

To create a python program and to implement the list ADT using arrays and linked list.

ALGORITHM:

Step 1: Creating a new list.

Step 2: Retrieving an object in the list at a particular index.

Step 3: Adding an object to the list at a particular index.

Step 4: Removing an object from the list at a particular index.

Step 5: Clearing the list.

Step 6: Print the contents of the list.

1
EX NO: 2

Write a programs to implement the following using a singly linked list.

AIM:

To create a python program STACK and QUEUE using singly linked list.

ALGORITHM:

Push Operation:

Step 1: Initialize a node

Step 2: Update the value of that node by data i.e. node->data = data

Step 3: Now link this node to the top of the linked list

Step 4: And update top pointer to the current node

Pop Operation:

Step 1: First Check whether there is any node present in the linked list or not, if not then return

Step 2: Otherwise make pointer let say temp to the top node and move forward the top node by 1 step

Step 3: Now free this temp node

2
EX NO: 3

Write a program that reads an infix expression, converts the expression to postfix form and
then evaluates the postfix expression (use stack ADT).

AIM:
To create a Python Program Code for Infix to Postfix Conversion.

ALGORITHM:
Step 1: Scanning the expression from left to right

Step 2: If the operand is encountered, push it into the stack

Step 3: If the operator is encountered, then pop the corresponding operand from the stack and perform
computation

Step 4: Continue the same process and retain the final value in the stack

3
EX NO:4

Write a Program to implement priority queue ADT.

AIM:

To create a Python Program to implement priority queue ADT.

ALGORITHM:

Step 1: Start the program.

Step 2: To start, items A, B, C, and D arrive in the presented order. All four items are added to the queue
in the order they arrive.

Step 3: At this point, an item is chosen for processing. Item A is selected and removed from the queue. It
is chosen because it arrived first and is at the front of the queue.

Step 4: Next, item E arrives. It is added to the back of the queue.

Step 5: Two more items are selected and removed. Items B and C are retrieved because they occupy the
first two positions of the queue.

Step 6: There are now two items in the queue. Item D is at the front and would be the next scheduled
item, followed by E. The next item to arrive would be added to the end of the queue, following E.

Step 7: Stop the program.

4
EN NO: 5

Write a Program to perform the Insert, Delete, Search element into a binary search tree.

AIM:

To create a Python Program to perform the Insert, Delete, Search element into a binary search
tree.

ALGORITHM:

Step 1: Start from the root node.

Step 2: When inserting, deleting and search an element, compare it to the root; if it is smaller than the
root, call the left subtree recursively; otherwise, call the right subtree recursively.

Step 3: Simply insert the node at the left (if less than current) or the right (if not) after reaching the end.

5
EX NO: 6

Write a Program to perform the following operations

A. Insertion into an AVL-Tree.

AIM:

To create a python program and to insert into an AVL-Tree.

ALGORITHM:

Step 1: Let the newly inserted node be w

Step 2: Perform standard BST insert for w.

Step 3: Starting from w, travel up and find the first unbalanced node. Let z be the first unbalanced
node, y be the child of z that comes on the path from w to z and x be the grandchild of z that comes on
the path from w to z.

Step 4: Re-balance the tree by performing appropriate rotations on the subtree rooted with z. There can
be 4 possible cases that need to be handled as x, y and z can be arranged in 4 ways.

Step 5: Following are the possible 4 arrangements:

y is the left child of z and x is the left child of y (Left Left Case)
y is the left child of z and x is the right child of y (Left Right Case)
y is the right child of z and x is the right child of y (Right Right Case)
y is the right child of z and x is the left child of y (Right Left Case)

6
B. Deletion from an AVL-Tree.

AIM:

To Create a Python Program to Deletion from an AVL-Tree.

ALGORITHM:

Step 1: Let w be the node to be deleted

Step 2: Perform standard BST delete for w.

Step 3: Starting from w, travel up and find the first unbalanced node. Let z be the first unbalanced node,
y be the larger height child of z, and x be the larger height child of y. Note that the definitions of x and y
are different from insertion here.

Step 4: Re-balance the tree by performing appropriate rotations on the subtree rooted with z. There can
be 4 possible cases that needs to be handled as x, y and z can be arranged in 4 ways. Following are the
possible 4 arrangements:

y is left child of z and x is left child of y (Left Left Case)

7
EX NO: 7

Write a Programs for the implementation of BFS DFS for a given Graph.

AIM:

To Create a Python Program for the implementation of DFS for a given Graph.

(A) DEPTH -FIRST-SEARCH

ALGORITHM:

Step 1: We will start by putting any one of the graph's vertex on top of the stack.

Step 2: After that take the top item of the stack and add it to the visited list of the vertex.

Step 3: Next, create a list of that adjacent node of the vertex. Add the ones which aren't in the visited
list of vertexes to the top of the stack.

Step 4: Lastly, keep repeating steps 2 and 3 until the stack is empty.

8
 (B) BREADTH FIRST SEARCH

AIM:
To Create a Python Program for the implementation of DFS for a given Graph.

ALGORITHM:

Step 1: Start by putting any one of the graph’s vertices at the back of the queue.

Step 2: Now take the front item of the queue and add it to the visited list.

Step 3: Create a list of that vertex's adjacent nodes. Add those which are not within the visited list to
the rear of the queue.

Step 4: Keep continuing steps two and three till the queue is empty.

9
EX NO:8

Write a Programs for implementing the following searching methods.

A. Linear Search.

AIM:

To Create a Python Program for implementing the Linear Search Method.

ALGORITHM:

Step 1: Start from the first element (index 0) and compare key with each element (arr[i]).

Step 2: Now when comparing arr[2] with key, the value matches.

Step 3: The Linear Search Algorithm will yield a successful message and return the index of the element
when key is found (here 2).

10
B. Binary Search.

AIM:

To Create a Python Program for implementing the Binary Search Method.

ALGORITHM:

Step 1: Let x = 4 be the element to be searched.

Step 2: Set two pointers low and high at the lowest and the highest positions respectively.

Step 3: Find the middle element mid of the array ie. arr[(low + high)/2] = 6

Step 4: If x == mid, then return [Link], compare the element to be searched with m.

Step 5: If x > mid, compare x with the middle element of the elements on the right side of mid. This
is done by setting low to low = mid + 1.

Step 6: Else, compare x with the middle element of the elements on the left side of mid. This is done by
setting high to high = mid - 1.

Step 7: Repeat steps 3 to 6 until low meets high

Step 8: x = 4 is found.

11
EX NO: 9

Write a Programs for implementing the following Sorting Methods.

A. Bubble Sort.

AIM:

To Create a Python Program for implementing the Bubble Sort Methods.

ALGORITHM:

Step 1: The algorithm iterates through the array multiple times.

Step 2: Each pass pushing the largest unsorted element to its correct position at the end.

Step 3: initializes an array, applies the bubbleSort function to sort it, and prints the sorted array.

Step 4: After sorting, the output is: [11, 12, 22, 25, 34, 64, 90], indicating ascending order.

12
B. Selection Sort.

AIM:

To Create a Python Program for implementing the Selection Sort Methods.

ALGORITHM:

Step 1: Set the first element as minimum

Step 2: Compare minimum with the second element. If the second element is smaller than minimum ,
assign the second element as minimum .

Step 3: After each iteration, minimum is placed in the front of the unsorted list.

Step 4: For each iteration, indexing starts from the first unsorted element. Step 1 to 3 are repeated until
all the elements are placed at their correct positions.

13
C. Insertion Sort.

AIM:

To Create a Python Program for implementing the Selection Sort Methods.

ALGORITHM:

Step 1: The first element in the array is assumed to be sorted. Take the second element and store it
separately in key.

Step 2: Now, the first two elements are sorted.

Step 3: Similarly, place every unsorted element at its correct position

14
D. Radix Sort.

AIM:

To Create a Python Program for implementing the Selection Sort Methods.

ALGORITHM:

Step 1: Find the largest element in the array, i.e. max. Let X be the number of digits in max. X is
calculated because we have to go through all the significant places of all elements.
In this array [121, 432, 564, 23, 1, 45, 788], we have the largest number 788. It has 3 digits.
Therefore, the loop should go up to hundreds place (3 times).

Step 2: Now, go through each significant place one by one.

15