Exploring Algorithm Design Approaches with Dr. Jey Veerasamy
Discover a range of algorithm design approaches including quick-sort, merge-sort, divide and conquer characteristics, greedy approach, and solutions to various optimization problems such as petrol cost minimization, number of stops minimization, activity selection, and knapsack problem. Dive into the efficient implementations like dynamic programming to solve complex Fibonacci number problems efficiently.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Algorithm Design approaches Dr. Jey Veerasamy
Petrol cost minimization problem S T You need to go from S to T by car, spending the minimum for petrol. 2
# of stops minimization problem S T Similar to petrol cost minimization problem, but we are minimizing # of stops.
Fractional knapsack problem Gold powder, silver powder, Thief has limited weight capacity
Fibonacci number problem Definition of Fibonacci number: F(1) = 1 F(2) = 2 F(n) = F(n-1) + F(n-2), when n > 2 Recursive solution using D&C approach: int f(int n) { if (n == 1) return 1; else if (n == 2) return 2; else return f(n-1) + f(n-2); } 10
D&C Solution for F(6) F(6) F(4) F(5) F(4) F(3) F(3) F(2) F(3) F(2) F(2) F(1) F(2) F(1) Several subproblems are solved repeatedly - Not an efficient approach. F(2) F(1) 11
DP solution for F(6) DP uses a table and bottom-up approach (note that D&C used top-down approach): int fib(int n) { int f[n+1]; f[1] = 1; f[2] = 2; for (i=3 ; i<= n ; i++) f[i] = f[i-1]+f[i-2]; return f[n]; } Computations are NOT repeated! F(1) F(2) F(3) F(4) F(5) F(6) 12
Knapsack problem Individual pieces with specific weights, thief wants to know whether there is an exact match for his weight limit.
