Algorithms and Complexity Assignment 1

1. ln(ex) =? log10(1000) =? log2(1024) =?
2. Pn i=1 i = ?
3. Pn i=1 21i =?
4. What is approximately Pn i=1 1i ?
5. Pn i=1 Pm x=1 ix = ?
6. We define unrooted tree as a undirected, acyclic graph. How many edges are there in an unrooted
tree with n nodes?
7. How many permutations are there for f1,2,3,4,5g? How many (un-ordered) pairs are there from
f1,2,3,4,5g?
8. Given n ≥ 2 distinct items, how many pairs of items are there?
9. How many ways of choosing k different elements from a set of n different elements are there?
Suppose we need to consider all k = 0 : : : n, and for each k we need to consider all possible
subsets with k different elements from a set of n different elements. How many subsets do we
need to consider?
10. Let S be a set with n elements. How many distinct subsets does S have?
1 Matrix Multiplication
Given two n by n matrices A and B, write a simple algorithm to compute the product of A and B.
Then, analyze your algorithm to find out how many additions and multiplications your algorithm will
take. Here, treat each addition or multiplication of two whole integers as one operation. You do not
need to come up with the most efficient algorithm; the goal of this problem is getting you started on
algorithm analysis.
2 Stable Matching: A Generalization
This problem is taken from the textbook (also see the book chapter posted on the class web page):
Exercise 4 on p.23. For convenience, I re-phrase the problem as follows.
One generalization of stable matching discussed in class is to consider the situation of National
Resident Matching Program, which matches medical students to hospitals. Here, there are m hospitals
and n students. Each hospitals has one or more openings for residents, and each student can only work
for one hospital. We assume there are more students than the number of openings. That is, there will
1
be students who can not find positions. Like before, each student has a ranking of (all) hospitals and
each hospital has a ranking of (all) students. The problem is to find a stable assignment of students
to hospitals, so that all openings are filled. We say an assignment is stable if neither of the following
occurs:
1. First type of instability. There are two students, s, s0, and a hospital h, where s is assigned with
h, s0 is free, and h prefers s0 over s.
2. Second type of instability. There are two students, s who is assigned to hospital h, and s0 who
is assigned to h0. But h prefers s0 over s and s0 prefers h over h0.
Now show that there always exists a stable assignment by giving an efficient algorithm for this problem.
3 The Pancake Problem
A stack of n pancakes is placed in front of you. You have a spatula which you can insert anywhere
into the stack and flip over all the pancakes above the spatula. You want to arrange the pancakes in
order of their diameter (they are perfectly round), and you want to use as few flips as possible. As an
example suppose n = 6, and the pancakes are numbered 1 through 6 in order of their diameter with 1
the smallest and 6 the largest. Suppose the original order is 346215, and the left end of the sequence
represents the top of the stack. In one flip I can get 643215 (by flipping the first three pancakes: 346),
then in the next flip 512346, then 432156, then 123456, so four flips are enough in this case. Let F (n)
be the worst case number of flips needed to arrange a stack of n pancakes. Find an efficient (in a
worst case sense) algorithm for this problem, where efficiency is measured by the worst case number
of flips. Remember that your algorithm should work for pancakes with any order. To start you off
you should easily be able to show that F (n) is at most 2n.
4 How to divide the stolen gold bars?
Five robbers, Adam, Bob, Chuck, Dave and Eric (ordered by the level of experience, with Eric being
the most experienced), just robbed a bank and stole 100 gold bars. Now they are hiding in a cave,
where there are hungry wolves roaming outside. The key problem they need to resolve is how to split
the gold bars among themselves. After a long grueling debate, they settle on the following process for
determining how to split the fortune: starting from Eric (and follow the decreasing order of experience),
each time one person proposes a way to split the gold bars among all (surviving) robbers. For example,
Eric could propose to give himself 60 bars, and give each of the rest 10 bar each. If at least half (yes
the one proposing the plan is counted) of the remaining guys agree to the proposed way of splitting
the gold bars, that is the final way of splitting the fortune and the process stops; otherwise, the one
who just proposed the splitting plan must leave the cave (and will surely be eaten by the wolves) and
then the process continues.
Now imagine you are Eric. Tell me what you are going to propose the way of splitting the fortune.
You need to justify your answer. Note: you can assume each person is selfish and logical: each wants
to be alive and at the same time he wants the maximum amount of gold bars.
5% Extra Credits In case you still have energy left after working on this homework, you can think
about the following questions: (i) what if there are k = 6; 7; : : : robbers? (ii) is it always better to be
the first to propose a splitting method? If not, how many robbers will there be in that case? You
don’t need to answer these and no solutions will be given for these questions. But if you answer these
correctly, you get 5% extra credits.
Hint: this seems hard at first; things will be easier if you think about the situation when there are
only two people left; what about the case with three people left? And so on