Assignment 3
Due: July 27 at noon 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 f alse
true f alse true
f alse true true
NOR
true f alse
true f alse f alse
f alse f alse true
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)
2. You are given a 2D map consisting of an C¡ÁR 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)
3. In a pond there is a sequence on n lily pads arranged in a straight line: 1,2,3…n . On lily pad i there are fi ¡Ý 0 flies. On lily pad 1 there is a frog sitting. The frog can only jump forward from a lily pad i to either lily pad i + 3 or lily pad i + 4. Find the largest number of flies that the frog can catch. (20 pts)
Hint: be careful: not all lily pads are accessible to the frog; the frog can only jump from the starting lily pad 1 to lily pads 4 and 5 but cannot access lily pads 2 and 3. Also, for some i there might be no flies on that lily pad (i.e., fi = 0). So you want to distinguish between lily pads without flies but which are accessible and lily pads which are not accessible.
4. You are on vacation for N days at a resort that has three possible activities 1,2 and 3. For each day i, for each activity 1,2 or 3, you¡¯ve determined how
1
much enjoyment e(i,j) (1 ¡Ü i ¡Ü n; 1 ¡Ü j ¡Ü 3) you will get out of that activity if you do it on that particular day (the same activity might give you a different amounts of enjoyment at different days). However, you are not allowed to do the same activity two days in a row. Design an algorithm for determining the maximum total enjoyment possible over the entire stay of N days and the sequence of activities you should do at each day. (20 pts)
5. 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. (20 pts)
2