3. You are given a boolean expression consisting of a string of the symbols true, false, and, or, and xor. Count the number of ways to parenthesize the expression such that it will evaluate to true. For example, there is only 1 way to parenthesize true and false xor true such that it evaluates to true. Give a dynamic programming algorithm to solve this problem and analyze the time complexity of your algorithm

5. You have n1 items of size s1, n2 items of size s2, and n3 items of size s3. Youd like to pack all of these items into bins each of capacity C, such that the total number of bins used is minimized. Give a dynamic programming algorithm to solve this problem and analyze the time complexity of your algorithm.

6. Consider a chain structured computation represented by a weighted graph G = (V, E) where V = {v1, v2, , vn} and E = {(vi , vi+1) | 1 ? i ? n ? 1}. We are also given a chain-structure m identical processors P = {P1, , Pm} (i.e., there exists a communication link between Pk and Pk+1 for 1 ? k ? m ? 1). The set of vertices V represents computation modules, and the set of edges E represents communication between the two modules. Each node vi is assigned a weight wi denoting the execution time of the module on a single processor. Each edge (vi , vi+1) is assigned a weight ci denoting the amount of communication time between the two modules if they are assigned two different processors. If multiple modules are assigned to the same processor, the modules assigned to the same processor must be consecutive. Suppose modules va, va+1, , vb are assigned to Processor Pk. Then, the time taken by Pk, denoted by Tk, is the time to compute assigned modules plus the time to communicate between neighboring processors. Hence, Tk = P a?i?b wi + ca?1 + cb. Note here that ca?1 = 0 if a = 1 and cb = 0 if b = n. The objective of the problem is to find an assignment ? : V ? P such that max1?k?m Tk is minimized, where we assume that each processor must take at least one module. (This assumption can be relaxed by adding m dummy modules with zero weight on computational and communication time.) Develop a dynamic programming algorithm to solve this problem in polynomial time.