The Australian National University Research School of Computer Science
COMP3600/6466 – Algorithms
This tutorial is compiled by:
Cormac Kikkert, William Cashman, and Hanna Kurniawati
Semester 2, 2020 Tutorial 7
Exercise 1 Exercise 2
Exercise 3
Questions on A3
Questions on Final Project – Final Deliverables
For those who want to start early
Dynamic Programming
1. How many ways can you roll a sum of n by throwing a 6-sided dice at most n times? Note that in this question, order matters. For example if n = 3 then there are 4 ways:
•1+1+1 •1+2 •2+1
•3
Please answer the above question by developing a dynamic programming algorithm to solve it. Specifically, please provide the four steps of the Dynamic Programming development steps (the steps are discussed in class in week-8 Tuesday lecture and based in [CLRS] 15.Intro and 15.3).
2. Suppose the question above is slightly modified that order does not matter. In this case, rolling a 2, 3 then a 5 is considered the same as rolling a 5, 2 then 3. Please provide the first two steps of the Dynamic Programming development steps to solve this modified problem.
3. ! [Optional, only do this if you’ve finished the above questions.] You have a grid with height H and width W. Each square in the grid is either Black or White, with the colour of each cell being given to you. Alice lives on the grid, and would like to travel from square (1,1) to square (H,W), by moving by one square either right or down while only staying on white squares. To help Alice you can perform the following operation as many times as you like:
• Pick a rectangle in the grid, and flip the colour of every square contained in the rectangle.
What is the minimum amount of operations you need to perform to allow Alice to make it to (H, W )? Develop an efficient algorithm that solves this problem.