Algorithms and Complexity Homework 1 Solution

About  homework submission.  You must  submit  a PDF  file in HuskyCT.  This will help our grader in the  grading.   I think  typing  a solution  also helps you to think  and  allow you to edit  more easily. If you don’t  know how to  typeset, you may  write  it  up  by hand  and  then  scan  into  PDF.  I would recommend  you to learn some typesetting software tools (such as Latex).  Google it:  Latex is the most popular  typesetting tool in math  and computer science.

The deadline  is the end of the day when the homework is due.

0.  Basic Concepts.

 

This problem is only for  self-study only; do  not hand in.  This problem checks your knowledge of some basic facts used in this  course.  Note:  these  do not  cover all the  needed  background; but  if you do not know how to answer some of these, it is time to review what  you learned in CSE 2100 and

2500.

 

1.  ln(ex)  =?  log10 (1000) =?  log2(1024) =?



2.
 
Pn i=1


 

i = ?

3.  Pn


1   =?

i=1 2i

4.  What  is approximately Pn      1 ?

 



5.
 
Pn i=1


 



Pm
 
x=1 ix = ?


i=1 i

 

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 {1,2,3,4,5}?  How many (un-ordered) pairs are there  from

{1,2,3,4,5}?

 

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

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.