Dynamic Programming in Computer Science: Maximizing Smartness on a Plane
DISCUSSION CLASS (DYNAMIC PROGRAMMING)
CS 141
SMARTEST STUDENT
N students
T seats in the plane
Maximum cumulative weight of students, W
Task: Maximize the total smartness on the plane
BAD IDEAS
Run 0/1 knapsack on N students
Sort students based on smartness
Sort students based on weight
Sorting would have helped if this was a greedy algorithm
HOW TO DO MEMORIZATION
Problem statement already helps with the approach
i = list of student in the class
j = number of student in the plane
k = cumulative weight of the selected students
We want to find/store the optimal smartness for a given (i, j, k)
RECURSION
BASE CASES
0 <= i <= N
0 <= j <= T
0 <= j <= i
k <= w_1 + w_2 + …. w_i
If i =0 or j = 0 or k = 0, f[i][j][k] = 0
ALGORITHM
MORSE CODE
Given,
Morse code string
Value array containing the value of all the chars
Maximize the total value of the interpretation of the given string
MORSE CODE
Given hint is to use f[i] to denote the highest value using first i elements in X
For position i, we will use
Check
function to check last few chars
If there is a matching char, we use the value of the char to maximize the current position
CHECK FUNCTION
check(X, i, j, c)
X is the Morse string
i,j are index in string
Char c
Function return true if substring X[i,j] is the Morse code of the char C
RECURSION STEP
Say for position i, char j
len(j) is the length of the char j
if
check(X, i-len(j), i, j)
is true, we would use the value from
f[i – len(j)]
f[i] = max (f[i] , f[i – len(j)] + v[j])
ALGORITHM
Discussing the application of dynamic programming in Computer Science class, specifically solving a problem of maximizing total smartness of students seated in a plane. The discussion covers strategies like memorization, recursion, base cases, and an algorithm to achieve the optimal solution. It also delves into bad ideas like using 0/1 knapsack and the importance of sorting based on smartness and weight. Additionally, it explores another problem related to maximizing the interpretation value of a Morse code string using dynamic programming techniques.
Uploaded on Sep 19, 2024 | 0 Views
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
SMARTEST STUDENT N students T seats in the plane Maximum cumulative weight of students, W Task: Maximize the total smartness on the plane
BAD IDEAS Run 0/1 knapsack on N students Sort students based on smartness Sort students based on weight Sorting would have helped if this was a greedy algorithm
HOW TO DO MEMORIZATION Problem statement already helps with the approach i = list of student in the class j = number of student in the plane k = cumulative weight of the selected students We want to find/store the optimal smartness for a given (i, j, k)
BASE CASES 0 <= i <= N 0 <= j <= T 0 <= j <= i k <= w_1 + w_2 + . w_i If i =0 or j = 0 or k = 0, f[i][j][k] = 0
MORSE CODE Given, Morse code string Value array containing the value of all the chars Maximize the total value of the interpretation of the given string
MORSE CODE Given hint is to use f[i] to denote the highest value using first i elements in X For position i, we will use Check function to check last few chars If there is a matching char, we use the value of the char to maximize the current position
CHECK FUNCTION check(X, i, j, c) X is the Morse string i,j are index in string Char c Function return true if substring X[i,j] is the Morse code of the char C
RECURSION STEP Say for position i, char j len(j) is the length of the char j if check(X, i-len(j), i, j) is true, we would use the value from f[i len(j)] f[i] = max (f[i] , f[i len(j)] + v[j])
