PPDM Homework Due 5/4

Problem 1: 
Givne : 100 doors, 100 people
Initial state: all closed – 0
Final state: some open, some closed.
Problem: How many open?
Problem: which ones? 
Operations: Person 1 – all doors, Person 2 – even doors (0/1), Person 3 – door#3,6…. (0/1)….. 


Problem 2: 

Given two graphs of the nature: 

G1: 

 P------W
  ------W
  ------W

 P -----W

and 
G2:
 
 P------W
  ------W
  
 P------W
  ------W
 

Find an algorithm to say y if they are similar and n if they are not similar. 

State your assumptions clearly and define the distance metrics you use to decide y or n. 

NOTE: you can imagine the two graphs to be be two documents, each document containing two paragraphs P and each paragraph having some words where we really don't care that he words can be different for the same of simplicity. 


----------------------------------------------------------------