Assignment 3
COMP3121/9101 22T1 Released March 17, due April 5
In this assignment we apply dynamic programming and related graph algorithms. There are four problems, for a total of 80 points.
Your solutions must be typed, machine readable PDF files. All submissions will be checked for plagiarism!
Copyright By PowCoder代写 加微信 powcoder
For each question requiring you to design an algorithm, you must justify the correct- ness of your algorithm. If a time bound is specified in the question, you also must argue that your algorithm meets this time bound.
Partial credit will be awarded for progress towards a solution.
1. (20 points) You are given a 2 by n grid, where the cell on row i column j contains a non-negative number ai,j. You can start at either cell in the lefttmost column, and your goal is to reach either cell in the rightmost column by a sequence of moves. You can move to an adjacent cell (if it exists) in each of the 4 cardinal directions (up, down, left and right).
A path achieves a score equal to the sum of values in its cells. Note that a cell which is used twice in a path only counts its value once to the score of that path.
Design an algorithm which runs in O(n) time and finds a path of minimum score from the leftmost column to the rightmost column.
2. (20 points) There are m towns in a straight line, with a road joining each pair of consecutive towns. Legends say that an ordinary person in one of these towns will become a hero by completing a sequence of n quests. The first quest will be completed in their home town, but after each quest they may complete their next quest either in the same town or after moving to a neighbouring town.
For example, if n = 5 and m = 4, a resident of town 2 may become a hero as follows:
• begin in town 2 for quest 1,
• then move to town 3 for quest 2, • stay in town 3 for quest 3,
• return to town 2 for quest 4, and • move to town 1 for quest 5.
Design an algorithm which runs in O(nm) time and finds the total number of ways to complete n quests.
3. (20 points) There are n different sizes of boxes, from 1 to n. There is an unlimited supply of boxes of each size t, each with a value vt. A box of size t can hold several smaller boxes of sizes a1,a2,…,ak as long as the sum of sizes a1 + a2 + … + ak is strictly less than t. Each of these boxes may be filled with yet more boxes, and so on.
Design an algorithm which runs in O(n2) time and finds the maximum value that can be attained by taking one box, potentially with smaller boxes nested inside it.
4. (20 points) You are given a tree T with n vertices, rooted at vertex 1. Each vertex i has an associated value ai, which may be negative. You wish to colour each vertex either red or black. However, you must ensure that for each pair of red vertices, the path between them in T consists only of red vertices.
Design an algorithm which runs in O(n) time and finds the maximum possible sum of values of red vertices, satisfying the constraint above.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com