Assignment-1

Data Structures and Algorithms

Sorting, Pointers, and Linked Lists
Due Date: 28 Jan, 2025 11:59 PM

Important Notes
• You are only allowed to use C for this assignment.
• For questions 3 and 4, all functions mentioned must be defined with exact function name and function
parameters and return type (we would run scripts to check this, so match the case of alphabets also)
• OPERATION names are case sensitive
• Doubt Document
• Plagiarism Policy. Please read this before you start the assignment.
TOTAL: [100 PTS]

1 Find the Closest Pair to a Target Sum [15 PTS]

1.1 Problem Statement
You are given an array of distinct integers and a target number. You must find two distinct numbers n1 and
n2 in the array such that:
1. The absolute difference |target − (n1 + n2 )| is minimized.
2. If there are multiple such pairs with the same minimum difference, choose the pair where n1 is the larger
value.

1.2 Input Format

• First line: An integer n [ 2 ≤ n ≤ 104 ] (size of the array).
• Second line: n space-separated integers (the elements of the array).
• Third line: A single integer (the target).

1.3 Output Format

Print two space-separated integers n1 and n2 (with the condition n1 < n2 ) that represent the chosen pair with
the minimum distance to the target according to the tiebreak rule.

1.4 Example Testcase

Sample Input Sample Output

6
5 2 3 10 6 9 6 9
15

1.5 Explanation
Among all pairs whose sums are closest to 15, (6, 9) achieves a sum of 15, which is at distance 0. Although the
pair (5, 10) also sums to 15, we choose (6, 9) because n1 = 6 is larger than 5 in the other pair.

1
2 Doctor A’s Appointment Adventures [20 PTS]
2.1 Problem Statement
Dr.A runs a clinic where all appointments must be exactly L minutes long. Patients request time slots (start
time and end time in hhmm format), but many requests overlap. Your task is to select the maximum possible
number of non-overlapping appointments, all of which must be exactly L minutes long.

2.2 Input Format

• First line: Two integers n and L, where n is the number of patients and L is the fixed duration (in
minutes) for each appointment.
• Next n lines: Each line has two integers (in hhmm format) indicating the requested start time and end
time for an appointment.

Constraints:
2 ≤ n ≤ 104 , 1 ≤ L ≤ 100

2.3 Output Format

Print a single integer indicating the maximum number of appointments that can be scheduled without overlap,
with the constraint that each appointment is exactly L minutes long.

2.4 Example Testcase

Sample Input Sample Output

6 30
0900 0930
0915 0945
0930 1000 4
0945 1015
1000 1030
1035 1105

2.5 Explanation
A possible selection is as follows:
1. 0900–0930: Selected first since it is the earliest.
2. 0915–0945: Overlaps with 0900–0930, so skip.

3. 0930–1000: Does not overlap, so select it.

4. 0945–1015: Overlaps with 0930–1000, skip.
5. 1000–1030: Does not overlap with 0930–1000, select.
6. 1035–1105: Does not overlap with 1000–1030, select.

Hence, 4 appointments fit without overlap.

2
3 Pointer Warmup [15 PTS]
Pointers is a very important concept in C programming. Let us begin with a few warm-up questions.

3.1 File Structure

• functions.h - Which has the function prototypes.
• functions.c - Which implements the functions defined in 3.2.
• main.c - Which must use the functions and perform various operations on input and produce output as
specified later.

3.2 Functions
• void reverseString(char* str, int length): takes in a pointer to a string and its length and reverses
the string in place.
• char* compressString(char* str, int length): takes in a pointer to a string and its length, and
returns a pointer to a string that is a compressed version of the original, where each character is followed
by the number of times it appears consecutively in the original string. For example, ”aaabbc” would be
compressed to ”a3b2c1”.
NOTE: No of times a character occurs continuously can be any number. (need not be single digit)
• int* uniqueElements(int* arr, int length): takes in a pointer to an array of integers and its length,
and returns a pointer to an array of integers that contains only the unique elements of the original array,
without using any library functions except malloc.
NOTE: The size of the array you are returning must be exactly equal to the number of unique elements.
• int** transpose(int** matrix, int NumRow, int NumCol): takes in a pointer to a matrix of integers
and its dimensions and returns a pointer to a matrix that represents the transpose of the original matrix.
NOTE: The dimensions of the matrix you are returning must be exactly equal to the dimensions of the
mathematical transpose.

3.3 Input and Output

The first line contains T , the number of OPERATION’s that need to be done. 1 ≤ T ≤ 100.

The first line of an OPERATION consists of a string indicating the OPERATION name.

The next few lines contain the required input data according to the table i.e.

Operation name Corresponding function

OPER1 reverseString
OPER2 compressString
OPER3 uniqueElements
OPER4 transpose

3
OPERATION INPUT FORMAT CONSTRAINTS OUTPUT FORMAT
First line contains an integer
OPER1 n indicating the length of the 1 ≤ n ≤ 104 [ 2.5 PTS ] String (Reversed)
string.
Second line contains the string
First line contains one integer
OPER2 n indicating the length of the 1 ≤ n ≤ 104 [ 2.5 PTS ] String (Compressed)
string.
str[i] contains only lower-
Second line contains the string
case alphabet
All unique elements in a
First line contains an integer
line, space separated and
OPER3 n indicating the length of the 1 ≤ n ≤ 104 [ 5 PTS ]
should be in the order
array.
they appear first
Second line contains n space
1 ≤ arr[i] ≤ 104
separated integers.
First line contains 2 integers
The transposed matrix.
R and C indicating the num-
OPER4 1 ≤ R, C ≤ 102 [ 5 PTS ] Each row should be
ber of rows and the number of
printed on a new line.
columns, respectively.
Following R lines contains C
1 ≤ M at[i][j] ≤ 106
space-separated elements

3.4 Example Test Cases

Input Output
4
OPER1
10
abcdefghij jihgfedcba
OPER2
12
aacceeggiiaa a2c2e2g2i2a2
OPER3
10
1124599168 1245968
OPER4
34 1 2 3
1234 2 3 4
2345 3 4 5
3456 4 5 6

4
4 Circular Linked List [25 PTS]
In this question, the aim is to create a self-adjusting circular linked list. A self-adjusting list is like a regular
list, except that all insertions are performed at the front. When an element is accessed by a Find function, it
is moved to the front of the list without changing the relative order of the rest of the elements.

4.1 File Structure

• functions.h - Which has the function prototypes.
• functions.c - Which implements the functions defined in 3.3.
• main.c - Which must use the functions and perform various operations on input and produce output as
specified later.

4.2 Structs
Each node in the circular linked list needs to have the following attributes:
• int Element
• PtrNode NextNode
Note: You can add other attributes if it helps with the code.

4.3 Functions
• void Insert(PtrNode Head, int num): creates a new node containing the integer num and inserts (adds
it to the front) it into the circular linked list (identified by Head).
• PtrNode Find( PtrNode Head, int num ): searches the circular linked list (identified by Head) for the
node with the integer num and then moves the node containing num to the front of the circular linked list.
The function returns the pointer to the node that contains num.(If num doesn’t exist in the circular linked
list, then return a NULL pointer).
• void Print( PtrNode Head): prints the elements of the circular linked list in order.
Note: After completion of each operation the linked list must necessarily be circular

4.4 Input and Output

The first line contains T , the number of operations that need to be performed. 1 ≤ T ≤ 1000.

The next line consists of a string indicating the OPERATION to be executed.

The next few lines give the data needed for the operation i.e.

Operation
Corresponding function
name
OPER1 Insert
OPER2 Find
OPER3 Print

OPERATION INPUT FORMAT CONSTRAINTS OUTPUT FORMAT

First line contains an integer
OPER1 n that must be inserted into 1 ≤ n ≤ 106 [ 10 PTS ]
the circular linked list.
First line contains an integer n
OPER2 that must be searched in the 1 ≤ n ≤ 106 [ 10 PTS ]
circular linked list.
Print all the elements in
OPER3 [ 5 PTS ] the circular linked list in
order.

5
4.5 Example Test Cases
Input Output
10
OPER1
1
OPER1
2
OPER1
3
OPER2
2
OPER2
3
OPER1
5
OPER2
1
OPER1
9
OPER1
7
OPER3 791532

4.6 Explanation
We have:
1. Insert 1 : Inserts 1. The current state of the circular linked list will be:
1

2. Insert 2 : Inserts 2. The current state of the circular linked list will be:
2−1

3. Insert 3 : Inserts 3. The current state of the circular linked list will be:
3−2−1

4. Find 2 : Finds 2 and re-adjusts it. The current state of the circular linked list will be:
2−3−1

5. Find 3 : Finds 3 and re-adjusts it. The current state of the circular linked list will be:
3−2−1

6. Insert 5 : Inserts 5. The current state of the circular linked list will be:
5−3−2−1

7. Find 1 : Finds 1 and re-adjusts it. The current state of the circular linked list will be:
1−5−3−2

8. Insert 9 : Inserts 9. The current state of the circular linked list will be:
9−1−5−3−2

9. Insert 7 : Inserts 7. The current state of the circular linked list will be:
7−9−1−5−3−2

10. Print : Prints the circular linked list.

6
5 Sparse Matrices as Linked Lists [25 PTS]
Linked lists are commonly used in the representation of sparse matrices because they can efficiently store and
retrieve data without using too much memory. In a sparse matrix, most elements are zero, so storing all of
these zeros in memory is inefficient. Instead, only the non-zero elements and their row and column indices are
stored.

One way to use linked lists to represent a sparse matrix is to use a linked list for each non-zero row of the
matrix. Each node in the lists corresponds to a non-zero element in the row and holds the column index and
the value of the element.
Another linked list that stores pointers to the heads of the row lists connect these row lists together.

Example:
 
0 0 1 0
0 0 0 0
M =
2

0 8 0
0 0 1 1

Can be represented as

5.1 File Structure

• functions.h - Which has the required function prototypes.
• functions.c - Which implements the required functions.
• main.c - Which must use the functions and perform various operations on input and produce output as
specified later.

5.2 Problems:
1. Represent a sparse matrix using linked lists.
2. Find Transpose of a matrix

3. Add two matrices.

4. Multiply 2 Matrices. (This question is only for practice and will not be graded, but we strongly suggest
you to practice this part, as it will give you more exposure to pointers and linked lists).

5.3 Input and Output

The first line contains a string named OPERATION (ADD, M U L, or T RA) denoting the type of operation to
be performed on the matrix/matrices.

Only one OPERATION would be asked per run.

7
OPR INPUT FORMAT CONSTRAINTS
The second line contains the dimensions of the matrix
T RA N and M , followed by K denoting the number of non- 1 ≤ N, M ≤ 109
zero elements the matrix.
(i.e. N M K for matrix of size N × M ) 1 ≤ K ≤ min(N ∗ M, 103 ) [ 5 PTS ]
1 ≤ K ≤ min(N ∗ M, 106 ) [ 5 PTS ]
The next K lines contain three integers i, j, val repre-
senting the row index, column index, and value of the 0≤i<n,0≤j<m
non-zero elements in the first matrix.
−109 ≤ val ≤ 109 ,val ̸= 0
The second line contains the dimensions of the matri-
ADD ces N and M , followed by K1 , K2 denoting the number 1 ≤ N, M ≤ 109
of non-zero elements in each of the matrices.
(i.e. N M K1 K2 for matrices of size N × M ) 1 ≤ K1 , K2 ≤ min(N ∗ M, 103 ) [ 10 PTS ]
(i.e. N M K1 K2 for matrices of size N × M ) 1 ≤ K1 , K2 ≤ min(N ∗ M, 106 ) [ 5 PTS ]
The next K1 lines contain three integers i, j, val rep-
resenting the row index, column index, and value of 0≤i<n,0≤j<m
the non-zero elements in the first matrix.
Followed by K2 lines representing the non-zero ele-
−109 ≤ val ≤ 109 , val ̸= 0
ments of the second matrix in the same format
The second line contains the dimensions of the matri-
MUL ces N, M, L, followed by K1 , K2 , denoting the number 1 ≤ N, M, L ≤ 109
of non-zero elements in each of the matrices.
First matrix dimensions N ×M , Second matrix dimen-
1 ≤ K1 ≤ min(N ∗ M, 106 )
sions M × L
(i.e. N M L K1 K2 for matrices of size N × M ) 1 ≤ K2 ≤ min(M ∗ L, 106 )
The next K1 lines contain three integers i, j, val rep-
resenting the row index, column index, and value of 0≤i<n,0≤j<m
the non-zero elements in the first matrix.
Followed by K2 lines having the non-zero elements in
−100 ≤ val ≤ 100,val ̸= 0
the second matrix in the same format
max(no of non zero rows of mat1, no of
non zero columns of mat2) × max(K1 , K2 ),
≤ 103 [ Extra ]
max(no of non zero rows of mat1, no of
non zero columns of mat2) × max(K1 , K2 ),
≤ 106 [ Extra ]
Example:

ADD
4354
021
201
228
311
321
111
20 −1
22 −8
324

8
Corresponds to:

   
0 0 1 0 0 0
0 0 0 0 1 0
 + 
1 0 8 −1 0 −8
0 1 1 0 0 4

Output:
The first line of the output should contain the number of non-zero elements (W ) in the resultant matrix after
the operation.
The next W lines should contain three spaced integers denoting i, j, val, denoting the row number(0 indexed),
column number (0 indexed), and value of non-zero elements in the resultant matrix.

The expected output for the input shown above is:

4
021
111
311
325

Sample Test Cases:

Input Output
TRA 4
434 021
021 201
201 228
228 231
321
ADD 4
4354 0 2 1
021 1 1 1
201 3 1 1
228 3 2 5
311
321
111
2 0 -1
2 2 -8
324
MUL 3
32232 1 0 18
101 117
119 208
214
017
102
NOTE:
• For matrix transpose, though it is easier to produce the output by simply swapping i and j from the
input, we recommend you build a linked list representation of the matrix and perform transpose on it.
(This may be useful in matrix multiplication)
• As shown in the examples above, you can assume that the input is provided in sorted order of (i, j). The
output need not be sorted.

9
6 Submission Details
• For questions 3 and 4 OJ is only used to check the correctness of your code. You are eligible for a full
score(for a given function) if and only if the required functions are implemented as instructed. You will
be graded on your moodle submission.
• Question 1, 2, 5 will be graded directly as your OJ score, but you still have to submit it in moodle.

• All solutions submitted in OJ will be considered for plagiarism

• Your submission to moodle will also be checked for plagiarism
• Moodle submission should be of the given format. A roll number.zip, which contains a folder named your
roll number.

Figure 1: File format

All the best and happy coding!

10