buy Midterm 2 math 324 homework solution alberta university

Question - CMPUT 204 | Winter 2011
Algorithms I
Section B1 (Stewart) Midterm Exam 2March 25, 2011 Last name:
First name:

Time allowed: 50 minutes.
 Place all answers in the spaces provided on the question pages. JUSTIFYeach answer appropriately.
 This exam counts 15% toward your nal grade in this course.
 This exam is worth 30 points in total.
 The weight of each question is indicated in square brackets by the question number.
 There are 3 questions in this exam. Please check that your exam booklet is complete.
 This is a CLOSED BOOK exam { you may refer to one 8 1 2

11 inch double-sided sheet of notes
during the exam. No other aids allowed . Question Mark Out Of
1 10
2 10
3 10
TOTAL 30

Question 1
[10 marks] Your job is to seat nrambunctio ...Read More us children in a theatre with nbalconies. The
balconies are numbered from 1 to nand arranged from
oor to ceiling such that each balcony is above all
lower numbered balconies. You are given a list of mstatements of the form \ iteases j". If iteases j, then
you do not want to seat iabove or in the same balcony as j, otherwise iwill throw popcorn at jinstead of
watching the play.
a) [2 marks] Show how to represent the problem as a directed graph.
b) [5 marks] Explain how an algorithm studied in class could be used to assign the balconies if possible, or
to indicate that it is not possible, in linear time.
c) [3 marks] Show how to alter your solution in part (b) solve the problem if the theatre has only k < n
balconies.
2

Question 2
[10 marks] A list of distinct keys, initially in decreasingorder (i.e. largest to smallest) is to be
sorted (into increasingorder) by Heapsort. This question focuses only on the HeapBottomUpprocedure, not
the actual sorting.
a) [2 marks] How many comparisons of keys are done by HeapBottomUpif there are ten keys?
b) [5 marks] How many are done if there are nkeys? Show how you derive your answer.
c) [3 marks] Is a list in decreasing order a best case, worst case, or intermediate case for HeapBottomUp?
Justify your answer.
3

Question 3
[10 marks] The currency on Mars consists of a strange collection of coins { with values 1, 5, and
7. With those coins, a greedy approach to making change doesn't always work { for example, the minimum
collection of coins adding up to 11 (5+5+1) does not include the largest coin 11. Many planets have
similar currencies.
a) [8 marks] Design a dynamic programming algorithm to make change on any planet. The inputs to your
algorithm are the coin values of the currency: integers a
1,
a
2,
: : : ,a
n ; and the value to be made up in change:
integer C. The output is the minimum number of coins that add up to C. You do not have to compute the
coin values that add up to C, only the smallest numberof coins needed. Assume that a
1 < a
2< : : : < a
n,
that there are an unlimited number of coins of each value available, and that a
1 = 1.
Do not give pseudocode. Instead, describe how your algorithm lls in a table A[0 ::n; 0::C ]: give a formula for
computing each entry of the table, indicate the order in which the entries are computed, and indicate where
the nal answer is located in the table.
b) [2 marks] What is the asymptotic running time of your algorithm? Is it polynomial in the sizeof the
input?
4 ...Read Less

Solution Preview - Exam 2 PARTIAL ANSWERS Question 1 [10 marks] Your job is to seat nrambunctious children in a theatre with nbalconies. The balconies are numbered from 1 to nand arranged from oor to ceiling such that each balcony is above all lower numbered balconies. You are given a list of mstatements of the form \ iteases j". If iteases j, then you do not want

Original Question Documents

N/A