CS 24102 : DATA STRUCTURE AND ALGORITHMS LABORATORY

Lab Assignment No : 1 Day & Date : Thursday, August 07, 2025

Sections : IIIA & AIML Premises : IIIA [Lab 7] AIML [Lab 1]
Faculty : Sandip Ghosal; Bikas Kanti Sarkar and Supratim Biswas

Read the general information about the Laboratory course and follow the protocols given in the “…….” docu-
ment
Objective : To revise and strengthen programming skills under Linux environment. Get familiar with the
changes required to migrate from C to C++. Compile and execute programs using g++. Find the running time of
generated executable code; compare performance of different algorithms that solve the same problem.

Resources Required : Linux server; g++ software

Skills to be learnt : shell commands for file and directories; how to organize one’s home directory; use of g++;
shell i/o to execute programs redirecting i/o; basic features of C++; make changes to given C++ program to solve
a modified version of the original problem.

Reinforcement of Concepts from Theory : Nil

Problem 1. [ Set up your home directory; copy the material provided to you in your area]
• log into your assigned directory (common directory) and create a new directory for yourself with your
roll number. [pwd, mkdir, ls].
• Change your password [passwd] and make sure that you do not lose it for the semester.
• Change the permissions of your directory to prohibit others from entering your area. [chmod].
• create 4 directories in your roll-number dir, named as “handouts”, “assignment”, “programs” and “sub-
mission”. [mkdir]. Copy the files given by your faculty to the respective directories [cp]
• create a file with a suitable name such as “work-done-lab1” in which you save the results that are asked
in the problems. Move this file to the “submission” directory before closing the session.
Submission : snapshot of your entire roll-no directory with listing of all children in long form [ls -l -R]

Problem 2. [Compile, execute and find the run time of 3 different programs for finding perfect number]
A number is defined to be a perfect number, if the sum of all its factors (except the number itself), yields the
same number. The first 2 perfect numbers are 6 (1+2+3) and 28 (1+2+4+7+14). Three C++ programs, are given
to you, named as, "perfect1.C ", "perfect2.C" and "perfect3.C". All the 3 programs are supposed to find all per-
fect numbers in [1, 55555]. Run the following sequence of commands for each C++ program. One is done for
you.
$ g++ perfect1. C -o perf1 $ ./perf1 $ time ./perf1
Executing "./perf1" displays the output of the program. Examine the output and verify that they are correct. The
execution of "time ./perf1 " displays 3 time values. We will use the value reported as "real"as the time required
by this program.
• Repeat the last command a few times and observe the variations in the data displayed by “time”.
• Repeat the above sequence for the other 2 programs also and note down their performance data.
• Generate a report of all the results produced by each experiment
• Make changes to the C++ programs so that they can find all perfect numbers in the range [1, n], where n
is supplied as input by the user. Repeat the experiments and increase the range to 6 digit numbers. In -
clude the results in your report.
• Draw your conclusions on the performance of the 3 algorithms based on your experimental results.
Examine the source programs and try to explain the difference in performance from their code
Problem 3. Read the program given in the file, "randoms-file-io.C" that generates random numbers using file
i/o features of C++. Note the use of the following features.
#include <fstream> #include <climits> int main(int argc, char*argv[]) ifstream ofstream
Two files are required to be given in the command line as shown below.
Assume that we want to generate 20 random numbers in the range [3, 18], than we create an input file say,
"randinp1.txt", is with the following contents : 20 3 18
$ g++ randoms-file-io.C -o randomfileio
$ ./randomfileio randinp1.txt rand20
Then the input and output files are as shown below.

Input file as argv[1] : randinp1.txt output file as argv[2] : rand20

20 3 18 20 3 18
10 9 12 6 4 18 13 15 12 16
13 14 5 14 6 9 15 5 7 11
Your task is to generate 3 different sets of random numbers, of varying sizes, such as 500, 5000 and 50000 by
creating appropriate input files. Find out some details about the generated output files, such as number of lines,
number of words and number of characters in these files. You may use the wc command to generate such data.
Save all the relevant outputs in the “work-done-lab1-file.txt”.

Problem 4. Find the number of repetitions in the random numbers generated in Problem3. Consider an example
to illustrate the output required for a sample input file. The formula for calculating
Let repeat-count be the total number of repetitions in the input, range denote the number of distinct numbers in
[min, max], and count be the number of values in input file.
range = max + 1 – min Actual number of repetitions % = (repeat-count / count)*100
Expected number of repetitions = (| count – repeat-count| / count) * 100
Your C++ program has to use file i/o features to do its intended task. Assuming that the executable code is
named as "repeatcount" and the input file is named as "rand20" and the output file is named as "rep20", then the
result of executing the following command is shown below.

$ ./repeatcount rand20 rep20

Sample input file, rand20 Desired Output file, rep20

20 5 15 Actual repetitions % : with 9 repetitions is 45%
11 15 11 7 6 9 5 11 8 6 Expected repetitions % : with 9 repetitions is 45%
13 12 10 8 12 9 14 15 7 5
Append the output to the file, “work-done-lab1-file.txt”.

Finally, Before you logout make sure that you have saved the file “work-done-lab1-file.txt” in the submis-
sion directory.
Attachments
1. Handouts – lab-conductprotocol.pdf; handout-C++-basics.pdf; handout-shell-basics.pdf;
handout-g++.pdf; perfect-numbers-handout.pdf
2. Programs : Perfect1.C ; perfect2.C; perfect3.C; randoms-file-io.C
3. Lab-assignment1.pdf
End of Lab Assignment No. 1