COLLEGE OF ENGINEERING & TECHNOLOGY
UNIVERSITY OF SARGODHA
CE 416: Data Structure and Algorithms (Lab)
Lab 9 Manual
Divide and Conquer Algorithms
Instructor & Demonstrator: Engr. Nauman Ahmad Tariq
Student Name OBAID UR REHMAN
Roll No. ELEN51F20R010
Date Performed
Marks obtained
Instructor Signature
CLO-1 Illustrate understanding of key concepts of Data structures
and Algorithms using Python PyCharm Platform
CLO-2 Design a programming application by applying concepts of
Data Structures and algorithms leading to the solution of a moderate
scale-programming problem.
CLO-3 Write lab notes, effective communication and the analysis of
the given problem to perform in the laboratory environment.
CLO-4 Demonstrate involvement in the Project as a team or
individually with respect to the contribution.
OBJECTIVE:
Objective of this experiment is to design, develop and implement divide and conquer
algorithms. The algorithms implemented in this lab session will be quicksort and tower of
Hanoi.
ABOUT THE EXPERIMENT:
QUICKSORT:
QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array
around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.
Always pick first element as pivot.
Always pick last element as pivot (implemented below)
Pick a random element as pivot.
Pick median as pivot.
The key process in quickSort is partition(). Target of partitions is, given an array and an element x of array
as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x,
and put all greater elements (greater than x) after x. All this should be done in linear time.
ALGORITHM
Algorithm for choosing pivot
Step 1 − Choose the highest index value has pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − left points to the low index
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is new pivot
Recursive quicksort algorithm:
Step 1 − Make the right-most index value pivot
Step 2 − partition the array using pivot value
Step 3 − quicksort left partition recursively
Step 4 − quicksort right partition recursively
TOWER OF HANOI
Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of the puzzle
is to move the entire stack to another rod, obeying the following simple rules:
1) Only one disk can be moved at a time.
2) Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack
i.e. a disk can only be moved if it is the uppermost disk on a stack.
3) No disk may be placed on top of a smaller disk.
ALGORITHM
Step 1 − Move n-1 disks from source to aux
Step 2 − Move nth disk from source to dest
Step 3 − Move n-1 disks from aux to dest
START
Procedure Hanoi(disk, source, dest, aux)
IF disk == 1, THEN
move disk from source to dest
ELSE
Hanoi(disk - 1, source, aux, dest) // Step 1
move disk from source to dest // Step 2
Hanoi(disk - 1, aux, dest, source) // Step 3
END IF
END Procedure
STOP
Python Program Code:
import time
# Function to find the maximum value in a given array using Divide and Conquer
def dac_max(arr, index, l):
if l - 1 == 0:
return arr[index]
if index >= l - 2:
if arr[index] > arr[index + 1]:
return arr[index]
else:
return arr[index + 1]
max_val = dac_max(arr, index + 1, l)
if arr[index] > max_val:
return arr[index]
else:
return max_val
# Function to find the minimum value in a given array using Divide and Conquer
def dac_min(arr, index, l):
if l - 1 == 0:
return arr[index]
if index >= l - 2:
if arr[index] < arr[index + 1]:
return arr[index]
else:
return arr[index + 1]
min_val = dac_min(arr, index + 1, l)
if arr[index] < min_val:
return arr[index]
else:
return min_val
# Driver code
def main():
arr = [51, 20, 89, 65, 42, 10, 99]
n = len(arr)
# Measure start time
start_time = time.time()
max_val = dac_max(arr, 0, n)
min_val = dac_min(arr, 0, n)
# Measure end time
end_time = time.time()
print("Maximum:", max_val)
print("Minimum:", min_val)
# Calculate and print the elapsed time
elapsed_time = end_time - start_time
print("Execution Time:", elapsed_time, "seconds")
if __name__ == "__main__":
main()
OUTPUT:
Maximum: 99
Minimum: 10
Execution Time: 0.0 seconds
Process finished with exit code 0
Python Program Code (for 200,000 numbers):
import time
# Function to find the maximum value in a given array
def dac_max(arr):
if len(arr) == 0:
print("Array is empty!")
return -1 # Return a default value or handle this case accordingly
start_time = time.time()
max_val = arr[0]
for i in range(1, len(arr)):
if arr[i] > max_val:
max_val = arr[i]
end_time = time.time()
execution_time = end_time - start_time
print("Maximum:", max_val)
print(f"Execution Time (dac_max): {execution_time} seconds")
return max_val
# Function to find the minimum value in a given array
def dac_min(arr):
if len(arr) == 0:
print("Array is empty!")
return -1 # Return a default value or handle this case accordingly
start_time = time.time()
min_val = arr[0]
for i in range(1, len(arr)):
if arr[i] < min_val:
min_val = arr[i]
end_time = time.time()
execution_time = end_time - start_time
print("Minimum:", min_val)
print(f"Execution Time (dac_min): {execution_time} seconds")
return min_val
# Driver code
def main():
size = 200000
arr = list(range(1, size + 1)) # Populate the list with numbers from 1 to 200,000
max_val = dac_max(arr)
min_val = dac_min(arr)
if __name__ == "__main__":
main()
OUTPUT:
Maximum: 200000
Execution Time (dac_max): 0.01886725425720215 seconds
Minimum: 1
Execution Time (dac_min): 0.013058662414550781 seconds
Process finished with exit code 0
Assessment Rubric for Lab 9
Method of Evaluation: Lab report.
Outcomes Assessed:
CLO-1 Illustrate understanding of key concepts of Data structures and Algorithms using Dev
C++ Platform.
CLO-2 Design a programming application by applying concepts of Data Structures and
algorithms leading to the solution of a moderate scale-programming problem.
CLO-3 Write lab notes, effective communication and analysis of the given problem to perform
in the laboratory environment.
CLO-4 Demonstrate involvement in the Project as a team or individually with respect to the
contribution.
Performance 5 Excellent 4 Good 3 Satisfactory 2-1 Needs Marks
Improvement
Realization of Fully understand & Close to fully Partially Unable to
Experiment able to illustrate understand & able understands & able understand & able
CLO-1 quicksort and to illustrate to illustrate to illustrate
tower of Hanoi quicksort and quicksort and quicksort and
algorithms tower of Hanoi tower of Hanoi tower of Hanoi
algorithms algorithms algorithms
Conducting Completely able to Close to Partially able to Unable to
Experiment successfully completely able to successfully successfully
CLO-2 design and compile successfully design and compile design and compile
Python programs design and compile Python programs Python programs
for quicksort and Python programs for quicksort and for quicksort and
tower of Hanoi for quicksort and tower of Hanoi tower of Hanoi
algorithms tower of Hanoi algorithms algorithms
algorithms
Data Collection Completely Close to Partially Unable to
and Data Analysis understand & able completely understand & able understand & able
CLO-3 to demonstrate understand & able to demonstrate to demonstrate
syntax of quicksort to demonstrate syntax of quicksort syntax of quicksort
and tower of Hanoi syntax of quicksort and tower of Hanoi and tower of Hanoi
algorithms and tower of Hanoi algorithms algorithms
algorithms
Individual/Team Completely able to Close to Partially able to Unable to execute
Work execute different completely able to execute different different programs
CLO-4 programs for execute different programs for for quicksort and
quicksort and programs for quicksort and tower of Hanoi
tower of Hanoi quicksort and tower of Hanoi algorithms
algorithms tower of Hanoi algorithms
algorithms
Total
