3. The Holocron Cipher [10 Points] Guided by an unknown power whispering through the Force, Belman Grede wanders the desolate reaches of the galaxy, drawn to a forgotten Dai Bendu temple. There, he uncovers an ancient robot, CPP0, imbued with a mystical sentence-generation algorithm capable of decoding the Sith’s cryptic network patterns. With strategic brilliance inspired by ancient optimization techniques, Belman Grede embarks on a perilous quest to harness the robot’s arcane knowledge. As the Sith tighten their hold, Belman must unravel the Holocron network and fulfill the will of the mysterious power guiding him to restore balance to the Force… Let be the set of words that constitute CPP0’s vocabulary.Let be a constant such that no sentence will be longer than . Consider a sentence which is a string of words spoken by CPP0. As CPP0 is a robot, the first word spoken is always “Beepboop”. Thus, is “Beepboop”. Let denote the probability that a person would say sentence . Given conversation input from CPP0’s auditory sensors, CPP0 will generate a sentence

3.2 (d) Justify that your algorithm has runtime .

2.3 Prove the correctness of your algorithm given in 2.2.

 4.3 Justify the runtime.

 4.2 Justify that your algorithm is correct.

3.2 Describe a dynamic programming algorithm to find

2.1 Suppose all location numbers are integers in the range . For example: Design an algorithm which tells you which settlements can be built and which cannot be built.

1. Initech Task Planning [10 Points] You finally finished your CS degree and got a job at the banking software company Initech. But you are finding that the real world is not all it’s cracked up to be. You do have a red Swingline stapler, but, on the downside, you have constant TPS reports, a printer that always says “PC LOAD LETTER”, and a large set  of tasks to complete (each task takes the same amount of time to complete). You consider a subset

3.2 (b) Give a Bellman equation that can be used to achieve this.

5.2 (b) Show that MFAN is -hard.