Lab Assignments
Lab Cycle-1 Week-1 July 2025
Learning Outcome: Learn to use arrays and develop application programs.Analyse the performance.
(Show the output after completing all the programs. Evaluation is done based on this)
Write C programs to do the following:
1) Write a function rotate(int a[],int n,char d,int cr) to rotate given array elements.
The function will take the array, number of elements in the array, direction of rotation(l-left r-right) and count of rotation( how many times to rotate)
Eg:
input array a[]=2 3 4 5 6 7
rotate(a,6,l,2)
output:4 5 6 7 2 3
rotate(a,6,r,2)
output:6 7 2 3 4 5
2) Find the mean, median and mode of list of elements. Use array to implement the same.(assume Unimode ). Write separate functions.
l=[1,2,3,5,4,5,6,3,1,1]
Mean-3.1
Median-3.0
Mode-1
3) Find the frequency of occurrence of each character in the string ( histogram)
Eg: input: This is a test string
Output:t-3, h-1,i-3,s-4,’ ‘-4…….etc
4)Consider two sets S1={1,2,3,4}, and S2={3,4,5}. Find the intersection of S1 and S2={3,4}.Implement the set operation intersection using arrays.
5)Mark of the students in an exam are stored in an integer array marks.Sort the marks in descending order using bubble sort. Implement a function insert(int m) that inserts the given mark m into the marks array. The inserted value should maintain a sorted order in the collection.
( understand the complexities involved)6.Find all local maximums of an array of unique elements. An element is considered to be local max if it is greater than the nearby elements
Eg; [ 3 2 5 7 8 1 6 9]
Here 8 and 9 are local maximums
7.Write a Menu driven program to do the following
a) Print Fibonacci Series < 100
b)Print Prime Numbers Less than 100
8.Implement Bubble Sort ( Consider best case and worst case inputs).Compute the time taken in each case. Print the performance analysis chart for Different n ( 5,10,15,20,25)
9.Implement Linear Search on an array( consider the best and worst case input). Print the time taken for each case as a chart for various n .( 5,10,15,20,25).
10.Modify the Program developed in 7 and print all prime numbers from the Fibonacci series. Count the prime numbers less than 100,1000,10000,20000.Can you observe some relation. (Learn Prime Number Theorem)
11.Implement binary search on a sorted array.Compare the best, worst and average case performance on various input distributions.
Lab Cycle-2 Week-2 July 2025
Stack
Stack is a data structure having LIFO structure. PC uses stacks at the architecture level, which are used in the basic design of an operating system for interrupt handling and operating system function calls. Recursive programs uses stack extensively. The design of compilers, language recognizers, expression evaluation etc uses stack. Many languages has a class called "Stack", which can be used by the programmer.
1) Implement stack
a) using an array
b) using singly linked list.
2) Implement multiple stacks(2 stacks) using an array. Consider memory efficient implementation
2) Implement multiple stacks(2 stacks) using an array. Consider memory efficient implementation
3)Convert a decimal number into binary using stack.
4)Check whether a string is palindrome or not using stack.
5)Find the minimum element in a stack in O(1) time using an auxiliary stack which keeps track of the minimum element.
6)Search for an element in a stack.Use only push() and pop() operation.An auxiliary stack can be used.Calculators employing reverse Polish notation use a stack data structure to hold values. Expressions can be represented in prefix, postfix or infix notations. Conversion from one form of the expression to another form needs a stack. Many compilers use a stack for parsing the syntax of expressions, program blocks etc. before translating into low level code. Most of the programming languages are context-free languages allowing them to be parsed with stack based machines.
7) Check whether the parenthesis are balanced in an expression.
Check if
(),{},[]are balanced in a given expression like:
"{[a + (b * c)] + d}"→ ✅ Balanced
8)A pushdown automaton (PDA) for strings with an equal number of 0s and 1s can be designed to accept strings where the number of 0s is the same as the number of 1s. The PDA essentially pushes 0s onto the stack when it encounters them and pops them off when it reads 1s. If the stack is empty at the end of the input, the string is accepted.( implement the same)
9) Convert a given infix expression to postfix/prefix10) Evaluate a postfix/prefix expression.
Lab Cycle-3 Week-3 July 2025
Learning Outcome: Learn Polynomial Representation and Sparse Matrix Representations
1.Represent a polynomial P(x) using arrays.Evaluate the polynomial for a given value
Eg:P(x)= 3x^2+2x+1evaluation P(2)=12+4+1=17
2.Represent the polynomial using a linked list and evaluate the polynomial.
3.Write a program to read two polynomials and store them in an array. Calculate the sum of the two polynomials and display the first polynomial, second polynomial and the resultant polynomial.
4.Do the Polynomial addition using Linked List.5. Implement the polynomial multiplication using linked list.
6.Given a sparse matrix . Represent and store it using an efficient method(tuple representation). Also find the sparsity (The sparsity of a matrix can be quantified with a score, which is the number of zero values in the matrix divided by the total number of elements in the matrix.)
7.Find the sum of two sparse matrices using the tuple representation.
8.Input the representation of a sparse matrix. Find the representation of its transpose.
9.Check whether the given matrix is sparse symmetric using the representation given.
Lab Cycle-4 Week-4 July 2025
Learning Outcome: Learn the Data Structure Queue and its implementations.Learn application programs using Queue.
1.Implement a Queue
a) using array
b) using singly linked list
2.Implement a circular queue(ring buffer).
a) using array
b) using singly linked list
3. Implement a double ended queue using
a)using array
b) using singly linked list
4.Implement Priority Queue using linked list
6.Reverse a Queue ( use an auxiliary stack).
optional ( can you modify the program)Reversing First K Elements of a Queue
Problem:
Given a queue and an integer k, reverse the first k elements of the queue.
Input: [1, 2, 3, 4, 5], k = 3
Output: [3, 2, 1, 4, 5]
Hint: Use stack + queue combination.
7.Can you implement a stack using queue
8.Sliding Window Maximum ( use a queue to store the max)
Problem:
Given an array of integers and a window size k, print the maximum element in every sliding window of size k.
Input: [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output: [3, 3, 5, 5, 6, 7]
Problem:
Given an array of integers and a window size k, print the maximum element in every sliding window of size k.
Input: [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output: [3, 3, 5, 5, 6, 7]
Lab Cycle-5 Week-1 Week 2 Aug 2025
Learning Outcome: Learn the Data Structure Singly Linked List and its Implementation and Applications
Write programs to implement the following using singly linked list:
1.Create a linked list with n elements by adding elements at the end and display it.
2. Given a node data, insert a new node after it.
3.Given a node data, insert a new node before it.
4.Insert a new node in the given position.(position 1-n)
5.Delete a node, given the key data value.
6.Delete a node given the position.
7. Delete the smallest element from the list.
8. Reverse a list.
9. Search for a given element and print it's position.
10. Create a list in sorted order.elements must be inserted in sorted order.
11. Create two sorted list using program in 10. Merge the two list and create a new sorted list.
12.Linked lists are used to represent sets eg: S1={1,2,3,4}, S2={2,3,5,6}. Write program to find the
a) union b)intersection
13.Design a program to remove duplicate elements from an unsorted linked list. The order of elements should be preserved.14.You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order, and each of their nodes contains a single digit. Write a program to add the two numbers and return the sum as a linked list.(e.g., 123 is represented as 3->2->1).
15.Sort a singly linked list .
16.rollno,name and mark of n students are stored using a linked list.Write programs to do insertion,deletion,modification and search operations(use rollno as key).
Lab Cycle-6 Week-3 Aug 2025
Learning Outcome: Learn the Data Structure Doubly Linked List and its Implementation and Applications
Write programs to implement the following using doubly linked list:
1.Create a doubly linked list with n elements by adding elements at the end and display.
2.Insert a new node at the front and create the list. Display the list in both directions.
3.Given a node data, insert a new node after it.
4.Given a node data, insert a new node before it.
5.Insert a new node in the given position.(position 1-n).
6.Delete a node, given the key data value.
7.Delete a node given the position.
8.Delete the smallest element from the list.
9.Implement a deque using doubly linked list.
10.Simulate browser navigation.
10.Simulate browser navigation.
11.Implement Following Memory Allocation Strategies
13.Find and replace words- implement this feature using linked list
Lab Cycle-7 Week-4 Sep 2025
Build a Binary Search Tree and Implement all the operationsLearning Outcome: Learn the Non Linear Data Structure - Binary Search Tree
1.Create a binary search tree ( use the sample tree above)(Do the array and linked list implementation)
and do the traversals
- Inorder -output is {5 , 15 , 18 , 20 , 25 , 30 , 35 , 40 , 45 , 50 , 60}
- Preorder-output is {30 , 20 , 15 , 5 , 18 , 25 , 40 , 35 , 50 , 45 , 60}
- Post Order-output is {5 , 18 , 15 , 25 , 20 , 35 , 45 , 60 , 50 , 40 , 30}
2.Use the tree created in Q1 and do the level order traversal
- Level Order-output is {30 , 20 , 40 , 15 , 25 , 35 , 50 , 5 , 18 , 45 , 60}
4.Sort a list of elements ( create a BST and do the inorder traversal)
5.Find the maximum and minimum key element
6.Find the height(depth) of a BST
7.Count the total number of nodes,leaf nodes and internal nodes.
5.Find the maximum and minimum key element
6.Find the height(depth) of a BST
7.Count the total number of nodes,leaf nodes and internal nodes.
8.Delete a specified node.
9.Create a binary tree for a given simple arithmetic expression and find the prefix /postfix equivalent.(expression tree)10. Implement a dictionary of word-meaning pairs using binary search trees.
11.Given the preorder traversal of a BST .Build the tree.
12.Implement a binary heap(max)
13. Implement priority queue using max heap.
Lab Cycle-8 Week-1 Oct 2025
1.Implement The Graph Representations
Adjacency Matrix
Adjacency List
Incident Matrix
Learning Outcome: Learn the Non Linear Data Structure - Graph
1.Implement The Graph Representations
Adjacency Matrix
Adjacency List
Incident Matrix
2.Given the adjacency matrix of a Graph. Do the following
Find the degree of a vertex.(in degree and out degree if it is a directed graph).
Find the number of edges.
Find the vertices adjacent to a given vertex
Check if the graph is complete.
Check if an edge exist between two vertex.
Check for cycles ( optional)
Find the degree of a vertex.(in degree and out degree if it is a directed graph).
Find the number of edges.
Find the vertices adjacent to a given vertex
Check if the graph is complete.
Check if an edge exist between two vertex.
Check for cycles ( optional)
3.Given the adjacency list of a Graph. Do the following
Find all neighbours of a vertex.
Degree of a vertex.
Check whether two vertices are connected directly.
Find isolated vertex.
Count the number of edges in a graph.
Find all neighbours of a vertex.
Degree of a vertex.
Check whether two vertices are connected directly.
Find isolated vertex.
Count the number of edges in a graph.
4.Implement the Graph Traversal
Breadth First Search - BFSDepth First Search - DFS
5.Implement the following application Programs using BFS
Find the shortest path -single source to all destinations (undirected graph)
Mine in Maze-Multi source BFS
Water Pouring Problem- Graph Modeling
Mine in Maze-Multi source BFS
Water Pouring Problem- Graph Modeling
Lab Cycle9 Week-2 Oct 2025
Learning Outcome: Learn Searching and Sorting techniques
Implement the Search Algorithms
1.Linear Search
2.Binary Search
You have to the find the position of occurrence of the key element in an array and also print the number of comparisons made.
Implement the Sorting Algorithms
3.Bubble Sort
4.Selection Sort
5.Insertion Sort
6.Quick Sort
7.Merge Sort
8.Heap Sort
9.Radix Sort
You have to print the array elements after each round of the algorithm.Use a randomly generated numeric array as input.
Application Programs
12.Sort the names of n students
13. Roll number , Name and Mark(out of 100) of students are stored in array of structure.
Prepare a Rank List.
Lab Cycle 10 Week-3 Oct 2025
The djb2 hash function, also known as Bernstein's hash function, is a non-cryptographic string hashing algorithm developed by Daniel J. Bernstein. It is widely recognized for its simplicity, speed, and effectiveness in generating hash values for strings, particularly for applications like hash tables and data structures where fast retrieval is crucial.
How it works:
The core of the djb2 algorithm involves initializing a hash value and then iteratively updating it based on the characters of the input string.
Initialization: The hash value typically starts with a prime number, commonly 5381.
Iteration: For each character in the input string:The current hash value is multiplied by a constant, usually 33. hash = hash * 33 + c;
The integer value of the current character is added to the result.
Final Hash: The final hash value after processing all characters is returned.
Learning Outcome: Learn Hashing Techniques
Implement the Hash Table
1.Linear Probing
2.Chaining
3.Quadratic Probing
4.Double Hashing
You can use simple hash function with hash table of size 11 h(k)=k mod 11. Collision resolution can be implemented using linear probing, quadratic probing and chaining. Assume integer keys as inputs.
5.Implement a hash table with chaining using dbj2 hash function.Use list of names as input.
How it works:
The core of the djb2 algorithm involves initializing a hash value and then iteratively updating it based on the characters of the input string.
Initialization: The hash value typically starts with a prime number, commonly 5381.
Iteration: For each character in the input string:The current hash value is multiplied by a constant, usually 33. hash = hash * 33 + c;
The integer value of the current character is added to the result.
Final Hash: The final hash value after processing all characters is returned.
6.Implement a spell checker using a hash table to store a dictionary of words for fast lookup
Internal Lab Examination is scheduled on Oct 24.
Comments
Post a Comment