Computer Architecture > QUESTIONS & ANSWERS > University of TexasEE 360cHomework10Solutions (All)

University of TexasEE 360cHomework10Solutions

Document Content and Description Below

EE360C: Algorithms University of Texas at Austin Homework #11 Dr. Christine Julien Due: April 20, 2014 (in class quiz) Homework #11 You should try to solve these problems by yourself. I recommend ... that you start early and get help in office hours if needed. If you find it helpful to discuss problems with other students, go for it. The goal is to be ready for the in class quiz that will cover the same or similar problems. Problem 1: Planning a Company Party You are consulting for the president of a corporation that is planning a company party. The company has a hierarchical structure; that is, the supervisor relation forms a tree rooted at the president. The personnel office has ranked each employee with a conviviality rating, which is a real number. In order to make the party the most fun for all of the attendees, the president does not want both an employee and his or her immediate supervisor to attend. You are given the tree that describes the structure of the corporation, where each node represents an employee, and a node’s children represent the employees under his or her direct supervision. Each node of the tree holds, in addition to the child pointers, the name of the employee and the employee’s conviviality rating. Give a dynamic programming algorithm to make up a guest list that maximizes the sum of the conviviality ratings of the guests. Analyze the running time of your algorithm. Hints: • Construct your solution as a binary choice. • Even the president of the company may end up not invited if that turns out to be optimal. • Argue that the problem exhibits optimal substructure, define the optimal solution via recursion, provide a description or pseudocode of the bottom-up algorithm, and analyze the running time. [Show More]

Last updated: 3 years ago

Preview 1 out of 5 pages

Buy Now

Instant download

We Accept: