Algorithmic Toolbox

Solutions of Coursera's "Algorithmic Toolbox" course, part of the "Data Structures and Algorithms Specialization"; offered by the University of California San Diego and HSE University.

Assignment 1 (Week 1): Programming Challenges

1. APlusB.java

• Description: Simple problem to go through the pipeline of reading the problem statement, designing an algorithm, implementing it, testing and debugging the program, and submitting it to the grading system.

• Input Format: Integers a and b on the same line (separated by a space).

• Constraints: 0 $\leq$ a; b $\leq$ 9

• Output Format: The sum of a and b.

2. MaximumPairwiseProduct.java

• Description: Given a sequence of non-negative integers a₁, ..., a_n, compute
  $\underset{{1 \leq i \neq j \leq n}}{max}$ a_i $\cdot$ a_j

Note that i and j should be different, though it may be the case that a_i = a_j.

• Input Format: The first line contains an integer n. The next line contains n non-negative integers a₁, ..., a_n (separated by spaces).

• Constraints: 2 $\leq$ n $\leq$ 2 · 10⁵; 0 $\leq$ a₁, ..., a_n $\leq$ 2 · 10⁵.

• Output Format: The maximum pairwise product.

---

Assignment 2 (Week 2): Algorithmic Warm-up

1. FibonacciNumber.java

• Description: Recall the definition of Fibonacci sequence: F₀ = 0, F₁ = 1, and F_i = F_i-1 + F_i-2 for 𝑖 $\geq$ 2. Given an integer 𝑛, find the 𝑛th Fibonacci number F_n.

• Input Format: The input consists of a single integer 𝑛.

• Constraints: 0 $\leq$ 𝑛 $\leq$ 45.

• Output Format: Output F_n.

2. GreatestCommonDivisor.java

• Description: The greatest common divisor GCD(𝑎, 𝑏) of two non-negative integers 𝑎 and 𝑏 (which are not both equal to 0) is the greatest integer 𝑑 that divides both 𝑎 and 𝑏. Implement the Euclidean algorithm for computing the greatest common divisor.

$GCD(1344, 217) = GCD(217, 42) = GCD(42, 7) = GCD(7, 0) = 7$

Given two integers 𝑎 and 𝑏, find their greatest common divisor.

• Input Format: The two integers 𝑎, 𝑏 are given in the same line separated by space.

• Constraints: 1 $\leq$ 𝑎, 𝑏 $\leq$ 2 $\cdot$ 10⁹.

• Output Format: Output $GCD(a, b)$.

3. LastDigitOfLargeFibonacciNumber.java

• Description: Find the last digit of 𝑛-th Fibonacci number. As 𝑖 grows the 𝑖^the iteration of the loop computes the sum of longer and longer numbers. Tip: store in 𝐹[𝑖] not the 𝑖th Fibonacci number itself, but just its last digit (that is, F_i mod 10). Given an integer 𝑛, find the last digit of the 𝑛^th Fibonacci number F_n (that is, F_n mod 10).

• Input Format: The input consists of a single integer 𝑛.

• Constraints: 0 $\leq$ 𝑛 $\leq$ 10⁷.

• Output Format: Output the last digit of F_n.

4. LeastCommonMultiple.java

• Description: The least common multiple of two positive integers 𝑎 and 𝑏 is the least positive integer 𝑚 that is divisible by both 𝑎 and 𝑏. Given two integers 𝑎 and 𝑏, find their least common multiple.

• Input Format: The two integers 𝑎 and 𝑏 are given in the same line separated by space.

• Constraints: 1 $\leq$ 𝑎, 𝑏 $\leq$ 2 $\cdot$ 10⁹.

• Output Format: Output the least common multiple of 𝑎 and 𝑏.

---

Assignment 3 (Week 3): Greedy Algorithms

1. CarFueling.java

• Description: We are going to travel to another city that is located 𝑑 miles away from your home city. We can travel at most 𝑚 miles on a full tank and you start with a full tank. Along your way, there are gas stations at distances stop₁, stop₂, . . . , stop_n from your home city. What is the minimum number of refills needed?

• Input Format: The first line contains an integer 𝑑. The second line contains an integer 𝑚. The third line specifies an integer 𝑛. Finally, the last line contains integers stop₁, stop₂, . . . , stop_n

• Constraints: 1 $\leq$ 𝑑 $\leq$ 10⁵; 1 $\leq$ 𝑚 $\leq$ 400; 1 $\leq$ 𝑛 $\leq$ 300; 0 $<$ stop₁ $<$ stop₂ $<$ · · · $<$ stop_n $<$ 𝑚

• Output Format: Assuming that the distance between the cities is 𝑑 miles, a car can travel at most 𝑚 miles on a full tank, and there are gas stations at distances stop₁, stop₂, . . . , stop_n along the way, output the minimum number of refills needed. Assume that the car starts with a full tank. If it is not possible to reach the destination, output −1.

2. MaximumLootValue.java

• Description: Implement an algorithm for the fractional knapsack problem to find the most valuable combination of items assuming that any fraction of a loot item can be put into a "bag".

• Input Format: The first line of the input contains the number 𝑛 of items and the capacity 𝑊 of a knapsack. The next 𝑛 lines define the values and weights of the items. The 𝑖-th line contains integers v_i and w_i — the value and the weight of 𝑖-th item, respectively.

• Constraints: 1 $\leq$ 𝑛 $\leq$ 10³, 0 $\leq$ 𝑊 $\leq$ 2 $\cdot$ 10⁶; 0 $\leq$ v_i $\leq$ 2 · 10⁶, 0 $<$ w_i $\leq$ 2 · 10⁶ for all 1 $\leq$ 𝑖 $\leq$ 𝑛. All the numbers are integers.

• Output Format: Output the maximal value of fractions of items that fit into the knapsack. The absolute value of the difference between the answer of your program and the optimal value should be at most 10^-3. To ensure this, output your answer with at least four digits after the decimal point (otherwise your answer, while being computed correctly, can turn out to be wrong because of rounding issues).

3. MoneyChange.java

• Description: Design and implement an elementary greedy algorithm to find the minimum number of coins needed to change the input value (an integer) into coins with denominations 1, 5, and 10.

• Input Format: The input consists of a single integer 𝑚.

• Constraints: 1 $\leq$ 𝑚 $\leq$ 10³.

• Output Format: Output the minimum number of coins with denominations 1, 5, 10 that changes 𝑚.

---

Assignment 4 (Week 4): Divide-and-Conquer

1. BinarySearch.java

• Description: implement the binary search algorithm that allows searching LIST very efficiently, provided that the list is sorted.

• Input Format: The first line of the input contains an integer 𝑛 and a sequence a₀ $<$ a₁ $<$ . . . $<$ a_n-1 of 𝑛 pairwise distinct positive integers in increasing order. The next line contains an integer 𝑘 and 𝑘 positive integers b₀, b₁, . . . , b_k-1.

• Constraints: 1 $\leq$ 𝑛, 𝑘 $\leq$ 10⁴; 1 $\leq$ a_i $\leq$ 10⁹ for all 0 $\leq$ 𝑖 $<$ 𝑛; 1 $\leq$ b_j $\leq$ 10⁹ for all 0 $\leq$ 𝑗 $<$ 𝑘;

• Output Format: For all 𝑖 from 0 to $𝑘−1$, output an index 0 $\leq$ 𝑗 $\leq$ $𝑛−1$ such that a_j $=$ b_i or −1 if there is no such index.

2. MajorityElement.java

• Description: Majority rule is a decision rule that selects the alternative which has a majority, that is, more than half the votes. Given a sequence of elements a₁, a₂, . . . , a_n, check whether it contains an element that appears more than 𝑛/2 times. Use the divide-and-conquer technique to design an 𝑂(𝑛 log 𝑛) algorithm.

• Input Format: The first line contains an integer 𝑛, and the next one contains a sequence of 𝑛 non-negative integers a₀, a₁, . . . $<$ a_n-1.

• Constraints: 1 $\leq$ 𝑛 $\leq$ 10⁵; 0 $\leq$ a_i $\leq$ 10⁹ for all 0 $\leq$ 𝑖 $<$ 𝑛.

• Output Format: Output 1 if the sequence contains an element that appears strictly more than 𝑛/2 times, and 0 otherwise.

---

Assignment 5 (Week 5): Dynamic Programming I

1. EditDistance.java

• Description: The edit distance between two strings is the minimum number of operations (insertions, deletions, and substitutions of symbols) to transform one string into another. It is a measure of similarity of two strings. The goal of this problem is to implement the algorithm for computing the edit distance between two strings.

• Input Format: Each of the two lines of the input contains a string consisting of lowercase Latin letters.

• Constraints: The length of both strings is at least 1 and at most 100.

• Output Format: Output the edit distance between the given two strings.

2. MoneyChangeAgain.java

• Description: A natural greedy strategy for the change problem does not work correctly for any set of denominations. For example, if the available denominations are 1, 3, and 4, the greedy algorithm will change 6 cents using three coins (4 + 1 + 1) while it can be changed using just two coins (3 + 3). The goal now is to apply dynamic programming for solving the Money Change Problem for denominations 1, 3, and 4.

• Input Format: Integer money.

• Constraints: 1 $\leq$ money $\leq$ 10³.

• Output Format: The minimum number of coins with denominations 1, 3, and 4 that change money.

3. PrimitiveCalculator.java

• Description: Given a primitive calculator that can perform the following three operations with the current number 𝑥: multiply 𝑥 by 2, multiply 𝑥 by 3, or add 1 to 𝑥. Given an integer 𝑛, compute the minimum number of operations needed to obtain the number 𝑛 starting from the number 1.

• Input Format: The input consists of a single integer 1 $\leq$ 𝑛 $\leq$ 10⁶.

• Output Format: In the first line, output the minimum number 𝑘 of operations needed to get 𝑛 from 1. In the second line, output a sequence of intermediate numbers. That is, the second line should contain positive integers a₀, a₁, . . . , a_k-1 such that a₀ $=$ 1, a_k-1 = 𝑛 and for all 0 $\leq$ 𝑖 $<$ $𝑘−1$, a_i+1 is equal to either a_i+1, 2a_i, or 3a_i. If there are many such sequences, output any one of them.

---

Assignment 6 (Week 6): Dynamic Programming II

1. MaximumAmountGold.java

• Description: Given a set of bars of gold, the goal is to take as much gold as possible into a bag. There is just one copy of each bar and for each bar you can either take it or not (hence you cannot take a fraction of a bar). Given 𝑛 gold bars, find the maximum weight of gold that fits into a bag of capacity 𝑊.

• Input Format: The first line of the input contains the capacity 𝑊 of a knapsack and the number 𝑛 of bars of gold. The next line contains 𝑛 integers w₀, w₁, . . . , w_n-1 defining the weights of the bars of gold.

• Constraints: 1 $\leq$ 𝑊 $\leq$ 10⁴; 1 $\leq$ 𝑛 $\leq$ 300; 0 $\leq$ w₀, w₁, . . . , w_n-1 $\leq$ 10⁵.

• Output Format: Output the maximum weight of gold that fits into a knapsack of capacity 𝑊.

2. MaximumValueOfArithmeticExpression.java

• Description: Find the maximum value of an arithmetic expression, by specifying the order of applying its arithmetic operations by adding parentheses.

• Input Format: The only line of the input contains a string 𝑠 of length $2𝑛 + 1$ for some 𝑛, with symbols s₀, s₁, . . . , s_2n. Each symbol at an even position of s is a digit (that is, an integer from 0 to 9) while each symbol at an odd position is one of three operations from {+,-,*}.

• Constraints: 1 $\leq$ 𝑛 $\leq$ 14 (hence the string contains at most 29 symbols).

• Output Format: Output the maximum possible value of the given arithmetic expression among different orders of applying arithmetic operations.