Algorithmic Toolbox | Week 3
Course Name: Algorithmic Toolbox
Course Link: Algorithmic Toolbox
These are Algorithmic Toolbox Week 3 Programming Assignment Coursera Answers
Programming Assignment 3: Greedy Algorithms
3-1: Money Change
def get_min_coins(money):
# Define the denominations
denominations = [10, 5, 1]
num_coins = 0
# Iterate over each denomination
for coin in denominations:
if money == 0:
break
num_coins += money // coin
money %= coin
return num_coins
if __name__ == '__main__':
money = int(input().strip())
print(get_min_coins(money))These are Algorithmic Toolbox Week 3 Programming Assignment Coursera Answers
3-2: Maximum Value of the Loot (Fractional Knapsack)
def get_max_value(capacity, weights, values):
# Calculate value to weight ratio
items = []
for i in range(len(weights)):
if weights[i] != 0:
items.append((values[i] / weights[i], weights[i], values[i]))
# Sort items by value to weight ratio in descending order
items.sort(reverse=True, key=lambda x: x[0])
total_value = 0.0
for value_per_weight, weight, value in items:
if capacity == 0:
break
amount = min(weight, capacity)
total_value += amount * value_per_weight
capacity -= amount
return total_value
if __name__ == '__main__':
import sys
input = sys.stdin.read
data = input().split()
n = int(data[0])
capacity = int(data[1])
weights = []
values = []
for i in range(n):
values.append(int(data[2 + 2*i]))
weights.append(int(data[2 + 2*i + 1]))
max_value = get_max_value(capacity, weights, values)
print(f"{max_value:.4f}")
These are Algorithmic Toolbox Week 3 Programming Assignment Coursera Answers
3-3: Car Fueling
def min_refills(distance, tank, stops):
# Add start (0) and end (distance) to the list of stops
stops = [0] + stops + [distance]
num_refills = 0
current_position = 0
while current_position < len(stops) - 1:
last_refill_position = current_position
# Move to the furthest reachable stop
while (current_position < len(stops) - 1 and
stops[current_position + 1] - stops[last_refill_position] <= tank):
current_position += 1
# If no progress is made, it means the next stop is unreachable
if current_position == last_refill_position:
return -1
# If we haven't reached the last stop, we need a refill
if current_position < len(stops) - 1:
num_refills += 1
return num_refills
if __name__ == '__main__':
import sys
input = sys.stdin.read
data = input().split()
d = int(data[0])
m = int(data[1])
n = int(data[2])
stops = list(map(int, data[3:3 + n]))
result = min_refills(d, m, stops)
print(result)
These are Algorithmic Toolbox Week 3 Programming Assignment Coursera Answers
3-4: Maximum Advertisement Revenue (Maximum Dot Product)
def max_dot_product(prices, clicks):
# Sort both sequences
prices.sort()
clicks.sort()
# Calculate the dot product
max_product = sum(p * c for p, c in zip(prices, clicks))
return max_product
if __name__ == '__main__':
import sys
input = sys.stdin.read
data = input().split()
n = int(data[0])
prices = list(map(int, data[1:n+1]))
clicks = list(map(int, data[n+1:2*n+1]))
result = max_dot_product(prices, clicks)
print(result)
These are Algorithmic Toolbox Week 3 Programming Assignment Coursera Answers
3-5: Collecting Signatures (Covering Segments by Points)
def cover_segments(segments):
# Sort segments by their right endpoint
segments.sort(key=lambda x: x[1])
points = []
current_point = None
for segment in segments:
if current_point is None or segment[0] > current_point:
current_point = segment[1]
points.append(current_point)
return points
if __name__ == '__main__':
import sys
input = sys.stdin.read
data = input().split()
n = int(data[0])
segments = []
index = 1
for i in range(n):
l = int(data[index])
r = int(data[index + 1])
segments.append((l, r))
index += 2
points = cover_segments(segments)
print(len(points))
print(' '.join(map(str, points)))
These are Algorithmic Toolbox Week 3 Programming Assignment Coursera Answers
3-6: Maximum Number of Prizes (Different Summands)
def find_maximum_k(n):
summands = []
current_sum = 0
current_number = 1
while current_sum + current_number <= n:
summands.append(current_number)
current_sum += current_number
current_number += 1
# Adjust the last number if the sum is not exactly n
if current_sum < n:
summands[-1] += (n - current_sum)
return summands
if __name__ == '__main__':
n = int(input())
result = find_maximum_k(n)
print(len(result))
print(' '.join(map(str, result)))
These are Algorithmic Toolbox Week 3 Programming Assignment Coursera Answers
3-7: Maximum Salary (Largest Number)
from functools import cmp_to_key
def largest_number(numbers):
# Custom comparison function
def compare(a, b):
if a + b > b + a:
return -1
elif a + b < b + a:
return 1
else:
return 0
# Convert numbers to strings for concatenation
numbers = list(map(str, numbers))
# Sort numbers using the custom comparison function
numbers.sort(key=cmp_to_key(compare))
# Concatenate the sorted numbers
largest_num = ''.join(numbers)
# To handle the case where there are leading zeros (e.g., [0, 0])
return '0' if largest_num[0] == '0' else largest_num
if __name__ == '__main__':
n = int(input())
numbers = list(map(int, input().split()))
print(largest_number(numbers))
These are Algorithmic Toolbox Week 3 Programming Assignment Coursera Answers
More Weeks of the course: Click Here
More Coursera courses: https://progiez.com/coursera
