Assignment 4 hints
Due: July 31 at 9 AM sharp
You have five problems, marked out of a total of 100 marks.
NOTE: Your solutions must be typed, machine readable .pdf files. All sub- missions will be checked for plagiarism!
1. Boolean operators NAND and NOR are defined as follows
NAND true true
f alse true
f alse true true
NOR
true f alse
true f alse
f alse f alse true
false
false
You are given a boolean expression consisting of a string of the symbols true, false, separated by operators AND, OR, NAND and NOR but without any parentheses. Count the number of ways one can put parentheses in the ex- pression such that it will evaluate to true. (20 pts)
Hint: You might want to consider contiguous substrings of that boolean ex- pression between ith and jth true/false symbols and solve subproblems which involve counting both the number of placements of the brackets such that the subexpression evaluates true AND the number of ways it evaluates to false.
2. You are given a 2D map consisting of an R¡ÁC grid of squares; in each square there is a number representing the elevation of the terrain at that square. Find a path going from square (1, R) which is the top left corner of the map to square (C, 1) in the lower right corner which from every square goes only to the square immediately below or to the square immediately to the right so that the number of moves from lower elevation to higher elevation along such a path is as small as possible. (20 pts)
Hint: This is a straightforward Dynamic Programming, filling a table of the size of the map.
3. You are on vacation for N days at a resort that has three possible activities. For each day, for each activity, you¡¯ve determined how much enjoyment you will get out of that activity if you do it on that particular day (the same
1
activity might give you a different amount at different days). However, you are not allowed to do the same activity two days in a row. What is the maximum total enjoyment possible? (30 pts)
Hint: For each day i ¡Ü N and each activity aj out of the three possible ac- tivities solve the problem P(i,j) of finding optimal activities up to day i so that on day i you do activity j.
4. Given a weighted directed graph G(V,E), find a path in G (possibly self- intersecting) of length exactly K that has the maximum total weight. The path can visit a vertex multiple times and can traverse an edge also multiple times. It can also start and end at arbitrary vertices or even start and end at the same vertex. (30 pts)
Hint: For every node i and every 1 ¡Ü k ¡Ü K find the maximum weight path of length exactly k which ends at i.
2