Data Structures and Algorithms (CS F211) Lab Sheet 1 solved




5/5 - (1 vote)

1. Given any n x n matrix, write a C program to find the saddle point of the matrix. A saddle point is an
element of the matrix such that it is the minimum element in its row and maximum in its column. The size
and the elements of the matrix are given as user inputs. In case the matrix does not contain a saddle point,
your code should be able to determine that as well.
2. Write a C program to create a number spiral of the form depicted below arranged as an n x n matrix. n is
given as user input.
3. Modify the above program to put only prime numbers in the number spiral.
59 53 47 43 41
61 11 7 5 37
67 13 2 3 31
71 17 19 23 29
73 79 83 89 97
4. Write a C program to find the Kth node from the end in the singly, doubly and circular linked list?
5. Write a C program with three functions: (i) Function Search(x) that search for a node containing a given
data (as search keyword), (ii) Function Delete(x) that keeps the node (that has first occurrence of the given
data x) and deletes the other nodes (that has rest of the occurrences of x) and then (ii) Function Swap that
swaps the node (that has first occurrence of the given data) with the next node. E.g. if the list 2->9->3->8-
>3->5->2->3, using search(3), the program shall find the three occurrences, using Delete(3), the output is 2-
>9->3->8->5->2 and using swap(), the output of the program is 2->9->8->3->5->2.
6. Given two numbers ‘a’ and ‘b’, write a C program to find prime numbers between ‘a’ and ‘b’ (both ‘a’ and
‘b’ are included).
7. Write a C program to encode a given message. The encoding algorithm first transforms every alternate
character (excluding spaces) into its third successor in the series and then performs reverse operation on
each word. For an example, the message “have a good day” will be first transformed as “kaye d grog ddy”
and then reversed as “eyak d gorg ydd”. Your program should also be able to decode a given coded message
into its original form i.e. if I give an encoded message it should decode the original message. Ignore the white
spaces while looking for the alternate characters.
Clarifications for Lab Sheet 1:
Q1: If there are multiple saddle points in a matrix, your program should be able to find all of
Q2: n is less than or equal to 1000.
Q3: Same as Q2.
Q4: Your code should find out the Kth node from the rear end of the singly, doubly and circular
linked list. The type of the linked list and the values to be stored in the linked lists are given
as user input. Your program should not take the number of nodes as user input. However, if
the given value of K is greater than the total number of nodes present in the linked list, your
program should display a message saying that “Value of K has exceeded the limit”.
Q5: Consider a singly linked list. The elements of the linked list are given as user input. In case,
the first occurrence of the number is in the tail of the list, then there is no swapping possible.
Q6: ‘a’ and ‘b’ are given as user input and lie in the range between 1 and 1000.
General: For the linked list programs, include a function to print the entire list.