Background Truth table for AND A TRUE FALSE TRUE FALSE Truth table for OR A TRUE FALSE TRUE FALSE Truth table for XOR A TRUE FALSE TRUE FALSE B TRUE TRUE FALSE FALSE B TRUE TRUE FALSE FALSE B TRUE TRUE FALSE FALSE EXPRESSION A AND B A AND B A AND B A AND B EXPRESSION A OR B A OR B A OR B A OR B EXPRESSION A XOR B A XOR B A XOR B A XOR B RESULT TRUE FALSE FALSE FALSE RESULT TRUE TRUE TRUE FALSE RESULT FALSE TRUE TRUE FALSE Truth table for NAND A TRUE FALSE TRUE FALSE Truth table for NOT A TRUE FALSE B TRUE TRUE FALSE FALSE EXPRESSION A NAND B A NAND B A NAND B A NAND B EXPRESSION NOT A NOT A RESULT FALSE TRUE TRUE TRUE Primitives supported: 'true' and 'false' Unary operations supported: 'not' Binary operations supported: 'and', 'or', 'xor', 'nand' RESULT FALSE TRUE Problem Description Your professor has decided to start a new business as a baker. However, instead of just putting normal prices on his cakes, each cake is assigned an array of symbols that represent different operations. Sample input: [ 'true', 'or', 'true', 'and', 'false' ] The way pricing works is that if the cake's entire expression evaluates to "true" then the cake is free. In the other case, if the entire expression evaluates to "false" it cannot be purchased. You are not allowed to change any of the symbols, but you may add a set of parentheses for a fixed price (in dollars) equal to the number of units apart the parentheses are from each other. Thus, if we place a set of parentheses around ('true') that would be $1. If we were to place a set of parentheses around ('true', 'and', 'false') that would be $3. Looking at our example "true or true and false" there are only two possible ways to evaluate this expression: true Choice 1 true or true and false or true and False True Choice 2 true or (true and false) or True and False Note: You only need to place parentheses where needed as the expression will be otherwise evaluated from left to right automatically. Thus, the first choice evaluates to false: [ 'true', 'or', 'true', 'and', 'false' ] [ 'true', 'and', 'false' ] ['false'] But if we place a set of parentheses as in choice 2, it will evaluate to true: [ 'true', 'or', ('true', 'and', 'false' ) ] [ 'true', 'or', ( 'false' ) ] ['true'] Write an algorithm using dynamic programming that when given the cake's information as input you can determine the minimum cost to buy that cake. You can assume the expression provided will be legal and syntactically correct. Suggested approach: Get your program working with just AND and OR to start. Once it is working correctly, then add the 'XOR' and 'NAND' operators. Once you have that working, now you can attempt adding the 'NOT' operator. Action Items / Requirements Select your favorite programming language. The only restriction is that the instructor needs to be able to compile and execute your code. For full credit your program must: O Compile without error and run correctly O Use dynamic programming as part of the main algorithm O Accept as input from the user a series of symbols that define the cake's price. o Output the correct minimum cost to purchase that cake. The algorithm must be as efficient as possible [O( ? ) ]. Approaches that are worse receive less credit. Only the efficiency of the "price algorithm" needs to be analyzed and optimal. Have sufficient unit tests for your algorithm. "Manual testing" is not accepted ■ You may use some unit testing framework in your language or write a simple framework that executes your code with automated inputs and expected results. ● ● ● O Prepare a report (PDF or MS Word) with the following O Instructions to compile and execute your program including any necessary requirements/packages/etc. O Describe how you came up with the algorithm and explain/justify how it works. This should be sufficient so that another person should generally understand how it works. o Analyze your implementation's efficiency (The algorithm that computes the cost). Either perform a line-by-line analysis or a sufficiently detailed analysis. This should result in an overall worst-case asymptotic order notation. Example runtime: What is the description of the cake? > true Calculating... The price for that cake is $0 Do you want to examine another cake? > Yes What is the description of the cake? > false Calculating... That cake is impossible to buy Do you want to examine another cake? > Yes What is the description of the cake? > true or true and false Calculating... The price for that cake is $3 Do you want to examine another cake? > Yes What is the description of the cake? > true and true xor not false and false Calculating... The price for that cake is $4 Do you want to examine another cake? > Yes What is the description of the cake? > true and not true xor false and false xor false Calculating... The price for that cake is $5 Submission Instructions 1. Compress your source code files, tests, additional files necessary to run your program, the report, etc. in a single zip file.