Data Structures and Algorithms/Design and Analysis of algorithms
Practical Assignment 1 Due date: 03 October 2025
Instruction:
Print code and output
Use C++ or C# compiler
Question 1.
Implement the following algorithm (10)
Euclid’s algorithm for computing gcd(m, n)
Step 1 If n = 0, return the value of m as the answer and stop; otherwise,
proceed to Step 2.
Step 2 Divide m by n and assign the value of the remainder to r.
Step 3 Assign the value of n to m and the value of r to n. Go to Step 1.
Question 2.
Design an algorithm and write the program to find all the common elements in two
sorted lists of numbers. For example, for the lists 2, 5, 5, 5 and 2, 2, 3, 5, 5, 7, the
output should be 2, 5, [Link] is the maximum number of comparisons your
algorithm makes if the lengths of the two given lists are m and n, respectively? (10)
Question 3.
Describe the algorithm used by your favorite ATM machine in dispensing cash. (You
may give your description in either English or pseudocode, whichever you find more
convenient.) (10)
Question 4.
Implement the following sequential search algorithm (10)
ALGORITHM SequentialSearch(A[0..n − 1], K)
//Searches for a given value in a given array by sequential search
//Input: An array A[0..n − 1] and a search key K
//Output: The index of the first element in A that matches K
// or −1 if there are no matching elements
i ←0
while i < n and A[i] != K do
i ←i + 1
if i < n return i
else return −1 Discuss its best-case, average-case, and worst-case
efficiency.
Question 5.
Fill in the description of the following basic asymptotic efficiency classes
Class Name Description
1 constant (2)
Log n logarithmic (2)
n linear (2)
n log n Linearithmic (2)
n2 Quadratic (2)
n3 cubic (2)
2n exponential (2)
n! factorial (2)
Question 6.
Implement the following algorithm for the sorting problem that sorts an array by
comparison-counting, for each of its elements, the number of smaller elements and
then uses this information to put the element in its appropriate position in the
sorted array:
ALGORITHM ComparisonCountingSort(A[0..n − 1])
//Sorts an array by comparison counting
//Input: Array A[0..n − 1] of orderable values
//Output: Array S[0..n − 1] of A’s elements sorted
// in nondecreasing order
for i ←0 to n − 1 do
Count[i]←0
for i ←0 to n − 2 do
for j ←i + 1 to n − 1 do
if A[i]<A[j ]
Count[j ]←Count[j ]+ 1
else Count[i]←Count[i]+ 1
for i ←0 to n − 1 do
S[Count[i]]←A[i]
return S
a. Apply this algorithm to sorting the list 60, 35, 81, 98, 14, 47. (6)
b. Is this algorithm stable? (2)
c. Is it in-place? (2)
Question 7.
Compute the factorial function F(n) = n! for an arbitrary nonnegative integer n. Use
the following recursive algorithm. (10)
ALGORITHM F(n)
//Computes n! recursively
//Input: A nonnegative integer n
//Output: The value of n!
else return F(n − 1) ∗ n
if n = 0 return 1
Question 8.
Consider the Fibonacci numbers, a famous sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21,
34, . . . that can be defined by the simple recurrence F(n) = F(n − 1) + F(n − 2) for
n > 1 and two initial conditions F(0) = 0, F(1) = 1.
a) Implement following algorithm to display the first 20 numbers of the
Fibonacci series. (10)
b) Implement the same algorithm this time using loops.
(10)
ALGORITHM F(n)
//Computes the nth Fibonacci number recursively by using its definition
//Input: A nonnegative integer n
//Output: The nth Fibonacci number
if n ≤ 1 return n
else return F(n − 1) + F(n − 2)
Question 9.
Implement the following algorithm for selection sort. (10)
ALGORITHM SelectionSort(A[0..n − 1])
//Sorts a given array by selection sort
//Input: An array A[0..n − 1] of orderable elements
//Output: Array A[0..n − 1] sorted in nondecreasing order
for i ←0 to n − 2 do
min←i
for j ←i + 1 to n − 1 do
if A[j ]<A[min] min←j
swap A[i] and A[min]
Question 10.
Bubble Sort: A brute-force algorithm to the sorting problem is to compare adjacent
elements of the list and exchange them if they are out of order. By doing it
repeatedly, we end up “bubbling up” the largest element to the last position on the
list. The next pass bubbles up the second largest element, and so on, until after n −
1 passes the list is sorted. Implement this algorithm. (10)
ALGORITHM BubbleSort(A[0..n − 1])
//Sorts a given array by bubble sort
//Input: An array A[0..n − 1] of orderable elements
//Output: Array A[0..n − 1] sorted in nondecreasing order
for i ←0 to n − 2 do
for j ←0 to n − 2 − i do
if A[j + 1]<A[j ] swap A[j ] and A[j + 1]
Question 11.
Implement the following insertion sort algorithm. (10)
ALGORITHM InsertionSort(A[0..n − 1])
//Sorts a given array by insertion sort
//Input: An array A[0..n − 1] of n orderable elements
//Output: Array A[0..n − 1] sorted in nondecreasing order
for i ←1 to n − 1 do
v ←A[i]
j ←i − 1
while j ≥ 0 and A[j ]> v do
A[j + 1]←A[j ]
j ←j − 1
A[j + 1]←v
Question 12.
Binary search is a remarkably efficient algorithm for searching in a sorted array. It
works by comparing a search key K with the array’s middle element A[m]. If they
match, the algorithm stops; otherwise, the same operation is repeated recursively
for the first half of the array ifK <A[m], and for the second half ifK >A[m].
ALGORITHM BinarySearch(A[0..n − 1], K)
//Implements nonrecursive binary search
//Input: An array A[0..n − 1] sorted in ascending order and
// a search key K
//Output: An index of the array’s element that is equal to K
// or −1 if there is no such element
l←0; r ←n − 1
while l ≤ r do
m←(l + r)/2
if K = A[m] return m
else if K <A[m] r ←m − 1
else l←m + 1
return −1
Question 13.
Mergesort is a perfect example of a successful application of the divide-and-conquer
technique. It sorts a given array A[0..n − 1] by dividing it into two halves A[0..(n/2)
− 1] and A[(n/2)..n − 1], sorting each of them recursively, and then merging the two
smaller sorted arrays into a single sorted one. Implement this algorithm.
ALGORITHM Merge(B[0..p − 1], C[0..q − 1], A[0..p + q − 1])
//Merges two sorted arrays into one sorted array
//Input: Arrays B[0..p − 1] and C[0..q − 1] both sorted
//Output: Sorted array A[0..p + q − 1] of the elements of B and C
i ←0; j ←0; k←0
while i <p and j <q do
if B[i]≤ C[j ]
A[k]←B[i]; i ←i + 1
else A[k]←C[j ]; j ←j + 1
k←k + 1
if i = p
copy C[j..q − 1] to A[k..p + q − 1]
else copy B[i..p − 1] to A[k..p + q − 1]
Apply mergesort to sort the list E, X, A, M, P, L, E in alphabetical order.
(10)