Heaven's light is our guide
Rajshahi University of Engineering &Technology
Department of Computer Science & Engineering
Lab Report
Course Name : Algorithm Analysis and Design Sessional
Course Code : CSE 2202
Experiment Name : Graham Scan, Fractional Knapsack, Coin problem.
Date of Experiment : 23/08/2025
Date of Submission : 13/09/2025
Submitted by Submitted to
Name: Anup Sarker Md. Mazharul Islam
Roll: 2203144 Lecturer
Section: C Department of CSE,
Series: 22 RUET.
1. Graham Scan Algorithm
Logical Solution:
The Graham Scan algorithm is used to find the convex hull of a given set of points in the
plane.
Steps:
1. Find the point with the lowest y-coordinate (and lowest x in case of tie).
2. Sort the remaining points by polar angle with respect to the starting point.
3. Traverse sorted points, and for each point, check the orientation (left turn/right turn).
- If a non-left turn is detected, remove the last point from the hull.
4. Continue until all points are processed. The remaining stack forms the convex hull.
Source Code:
Input/Output Example:
Input:
6
03
11
22
44
00
12
Output:
Convex Hull points in order:
00
44
03
Conclusion:
Graham Scan efficiently computes the convex hull with complexity O(n log n) due to
sorting. It is widely used in computational geometry problems involving boundaries or
enclosures.
2. Fractional Knapsack Problem (Greedy Approach)
Logical Solution:
The fractional knapsack problem maximizes profit under a weight constraint.
Steps:
1. Compute profit/weight ratio for each item.
2. Sort items in descending order of ratio.
3. Pick items greedily until capacity is full.
- If the item doesn’t fit, take a fraction of it.
Source Code:
Input/Output Example:
Input:
Profits: {10, 5, 15, 7, 6, 18, 3}
Weights: {2, 3, 5, 7, 1, 4, 1}
Constraint: 10
Output:
Max Profit: 55
Conclusion:
The greedy fractional knapsack guarantees an optimal solution with O(n log n)
complexity (due to sorting). It works because profit-to-weight ratio provides the best
selection criterion.
3. Minimum Coin Change Problem using Greedy Method
Logical Solution:
The problem is to make a given amount with the minimum number of coins/notes
available in denominations.
Steps:
1. Sort denominations in descending order.
2. Pick the largest possible note that fits into the remaining amount.
3. Subtract it and continue until the amount is zero.
Source Code:
Input/Output Example:
Input:
Enter the amount:
870
Output:
Minimum number of notes required: 5
Conclusion:
The greedy method works efficiently when denominations are canonical (like standard
currency). Time complexity is O(n) where n is the number of denominations.
