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

Learning Outcome: Learn the data structure Stack and its implementations.Learn application Programs using Stack.

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
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.

Expression evaluation and syntax parsing

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/prefix
10) 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+1
evaluation 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]

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.
11.Implement Following Memory Allocation Strategies
    First Fit
    Best Fit
    Worse Fit

Comments

Post a Comment

Popular posts from this blog

Data Structures Lab PCCSL307 KTU 2024 Scheme - Dr Binu V P

About Me    Learn the theory Data Structures and Algorithms PCCST303 Scheme and Assessments Experiment List and References Lab Assignments Format of the Lab Record Lab Cycle ( Mandatory Programs) 1.Polynomial Addition Using Arrays 2.Sparse Matrix- Transpose and Addition 3.Stack    Implement  stack using array    Infix to Postfix Conversion and Evaluation 4.Queue    Queue using array     Circular Queue using array     Double ended Queue using array 5.Singly Linked List      Singly  Linked list and operations     Stack using linked list     Queue using linked list    Polynomial addition using linked list    Polynomial multiplication using linked list     Priority Queue-Post office customers simulation     Circular Queue using Linked List 6. Doubly Linked List      Doubly Linked List- Operations     Double Ended Queue ...
Read more

Polynomial Addition using Arrays

Polynomial  Addition We can represent a polynomial as a collection of terms and every term is having a coefficient and exponent. So, we can represent this as a list of terms having coefficients and exponents.  Each term of a polynomial (like 3 x 2 3x^2 , 5 x 1 5x^1 , − 7 x 0 -7x^0 ) can be stored in a structure having two parts: coefficient (like 3, 5, -7) exponent (like 2, 1, 0) An array of such structures represents the whole polynomial. Structure Definition (Example in C) struct Term { int coeff; // Coefficient of the term int expo; // Exponent of the term }; And then you can declare: struct Term poly1 [10], poly2 [10], polyResult [20]; to represent polynomials. Algorithm to Add Two Polynomials Assumption : Both polynomials are sorted in decreasing order of exponents . Steps : Initialize three pointers (indexes): i = 0 for first polynomial (poly1), j = 0 for second polynomial (poly2), k = 0 for result polynomial (polyR...
Read more

Sparse Matrix - Transpose and Addition

Image
  A sparse matrix is a special type of matrix in which most of the elements are zero or have some default value. In contrast, a dense matrix is one in which most of the elements are non-zero. Sparse matrices are used in various fields, including computer science, numerical analysis, and scientific computing, when dealing with large datasets or systems where efficiency and memory usage are crucial.   As a rule of thumb, if 2/3 of the total elements in a matrix are zeros, it can be called a sparse matrix . Using a sparse matrix representation — where only the non-zero values are stored — the space used for representing data and the time for scanning the matrix are reduced significantly. In many real-world problems — like graphs, networks, or scientific simulations — the majority of elements in the matrix are zero . Such a matrix is called a Sparse Matrix . Formally: A matrix in which the number of zero elements is significantly greater than the number of non-zero elements. ...
Read more