2023年11月25日

算法代写 | Sequence Assignment 3

本次澳洲代写主要为算法相关的assignment

1. Boolean operators NAND and NOR are de ned as follows
NAND true false
true false true
false true true
NOR true false
true false false
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 ex-
pression such that it will evaluate to true. (20 pts)

2. You are given a 2D map consisting of an RC 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 ies. 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 ies 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 ies on that lily pad (i.e.,
fi = 0). So you want to distinguish between lily pads without ies 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
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 di erent amounts of enjoyment at di erent 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), nd 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)