Course: Data Structures and Algorithms (for ECE students)

Code: 15B11CI578

Weekly Assignments
Assignment - 1 (3rd Jan to 11th Jan)

(Practice Assignment) (C371.1)

1. Write a program to create a single link list (SLL1) having elements as 24, 6, 7, 8, 1, 2, 8, 10, 4, 27, 16,
26. Later, write a program to sort SLL1 (retain all the duplicate elements). Call this list as SLL2. Finally
merge SLL2 with SLL1 such that elements of merged linked list will be in sorted order (retaining all the
duplicate elements). 2. Write a RemoveDuplicates() function which takes a list sorted in increasing order
and deletes any duplicate nodes from the list.

3. Write a program in C to perform following operations on singly linked list (SLL). For every operation
create a separate function. a. Create a linked list containing 10 elements. Display the contents of SLL b.
Search an element entered by the user and return its position. For example, if the elements of the list are:
23, 12, 8, 78, 5, 45, 8, 15, 18, 20, 2, 19, 9, 8, 25, 17, then the position of 23 is 1 and of 8 is 3. c. Display
the contents of SLL in reverse order. d. Display identify second largest number in SLL (Do not sort the
link list). 4. Write a program to design a library management application using linked list which will
maintain a record of all the books available in the library including (Book name, author, ISBN,
publication year, no of copies available etc.). There is another list containing the name of the issued books
and the name of student, to whom the book is issued. Provide menu which will contain options to add,
delete, display and update the entry in the records.

Assignment – 02(13th Jan 13 – 18th Jan)

(C371.1)

1. Write a function which takes a list and deletes any duplicate nodes from the list.

2. Write a program in C to perform following operations on doubly linked list. For every operation create
a separate function. a. Create a linked list containing 10 elements. Display its contents.

b. Search an element entered by the user and return its position. For example, if the elements of the list
are: 23, 12, 8, 78, 5, 45, 8, 15, 18, 20, 2, 19, 9, 8, 25, 17, then the position of 23 is 1 and of 8 is 3.

c. Display the contents of the list in reverse order.

d. Display the second smallest number in List (Do not sort the link list).

Assignment -03(20th Jan- 25th Jan)

Use Doubly Linked List for solving the following questions (C371.1):

Q1. Take 'n' number of strings from the user.

a. Sort them in alphabetical order. Use recursion function.

b. Reverse the sorting order and display.

Q2. a. Create a Linked list such that it can be used to represent a polynomial function. The data
in the node represents the coefficient of the polynomial function. The position represents the power value.

Example: Input: 1 → -3 → 6 → 2

Output: x0 -3x1+6x2+2x3

b. Reverse the representation such that the first value of the original linked list is associated
with the highest power value:

Example: Input: 1 → -3 → 6 → 2

Output: x3 -3x2+6x1+2x0

Topic:Circular Linked List (C371.1)

Q3. Create a circular integer linked list. If the linked-list contains values less than 7 nodes, concate 0's
at the second last positions. If the linked list has more number of elements, truncate it such that
apart from the first and the last values, the first 6 values are displayed.

Topic: Algorithm Complexity (C371.2)

Q4. Develop a non-recursive function for reversing a single linked list and analyze the time complexity
of the developed code.

Q 5. What will be time complexity of the C code given below,

while (ptr->next!=NULL){

tmp = ptr->next;

while(tmp->next!=NULL){
>next!=NULL){

if(ptr->data > tmp->data){

>data){

//Swapping of data in node ptr and tmp }

Assignment -04(27th Jan- 1st Feb)

Topic : MultiList (C371.1)

Q1. The standard use of multi--linked
linked lists is to organize a collection of elements in two different
ways. For example, suppose the elements in node include the name of a person and his/her age.
e.g. (FRED,19) (MARY,16) (JACK,21) (JILL,18)
There is need to order these elements alphabetically and also to order them by age. There will be
need for two pointers - NEXT
NEXT-alphabetically, NEXT-age - and the list header would have two
pointers, one based on name, the other on age [as shown in figure bbelow].

Implement thehe following operations:

a) Insertion of new nodes in the multilinked list such that the list is sorted after insertion
b) Deletion of a node from the multilinked list based on the user inputted age/name
c) Display the multilinked li
list
Q2. Given a linked list where in addition to the next pointer, each node has a child pointer, which may
or may not point to a separate list. These child lists may have one or more children of their own,
and so on, to produce a multilevel data struct structure,
ure, as shown in below figure. You are given the
head of the first level of the list. Flatten the list so that all the nodes appear in a single-level
single linked
list. Write the program to flatten the list in way that all nodes at first level should come first, then
nodes of second level, and so on. Each node is a C struct with the following definition.
struct list
{
int data;
struct list *next;
struct list *child; };

The above list should be converted to

10→5→12→7→11→4→20→13
13→17→6→2→16→9→8→3→19→15

Q3. Write a program to read a list of students from a file and create a linked list. Each entry in the
linked list should have the student’s name, a pointer to the next pointer, and a pointer to a linked
list of scores. There may be up to 4 scores for each st student.
udent. The program should initialize the
student list by reading the students’ names from the file and creating null score lists.

It should then loop through the list, prompting the user to enter the scores for each student. The
scores’ prompt should include
clude the name of the student. After all scores have been entered, the
program should print the scores for each student along with the scoretotal and avg. The average
should include only those scores present.

Topic: Stack and Stack Applications (C371.1)

Q4. Write a program that reads integers from a file and pushes them into stack until it reads a negative
no. Then it pops five items from the stack and prints them. If there are fewer than five items in the
 stack, print the error message. After printing the data, the program resumes reading data and
placing them in the stack. When the end of file is detected, print a message and print items
remaining in the stack.

Topic: Queue and Queue Applications (C371.1)

Q5. For a given queue, Q, write a recursive function to shuffle the values stored in first half of queue
with the second half of it in an alternate manner. The first and the last values of the queue are not
affected by the shuffle. For example, (LHS is front of queue and RHS as rear of queue)

Example 1: Input Q: 123456

Output Q: 153426

Example 2: Input Q: 74621

Output Q: 7264 1

Q6. Given a queue, shuffle values of the queue, such that the smallest element is shifted to the end of
the queue without changing the basic ordering of the elements in the queue. Further, write a
modified stack for the same function such that the smallest element is shifted to the top of the
stack without changing the ordering of the other elements.

Week 5 (3rd Feb – 8th Feb): Evaluation-1 (15 Marks)

Evaluation Topics: Single Linked List/Circular Linked List, Stacks, Queues,
Algorithm Complexity
(C371.1, C371.2 )