1. Boolean operators NAND and NOR are defined as follows
false
true true
false
NAND true false NOR true false truefalse
false true true false false 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 expression such that it will evaluate to true. (20 pts)
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)
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 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)
4. Given a weighted directed graph G(V,E), find a path in G (possibly selfintersecting) 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 (30 pts)
