Homework 1
Algorithms and Data
Spring 2012
Karl Lieberherr

Due date:
Jan. 18, 2012, beginning of class.
Propose or oppose claims on Piazza by Jan. 12, 2012.
Remember to sign up for Piazza asap.

Page numbers refer to the text book by Kleinberg and Tardos.

The claims covered are from or motivated by
chapter 1. Read Chapter 1 first.
The claims
IntervalScheduling
WeightedIntervalScheduling
BipartiteMatching
IndependentSet
QuantifiedNumerical 
are families of claims that have a numerical parameter x or c.
Your goal is to choose x so that the claim is true and so that
the claim becomes false for a value >x. (similar for c)

Claim 
QuantifiedBoolean1, for example, 
asks you to come up with a simple algorithm 
that maps an x to a y. The same with claim
QuantifiedNumerical. 

Get together in small teams of 2 students to work on the claims.
It is up to you to decide who plays proposer and opposer/agreer.
The rules to follow are summarized here:
http://www.ccs.neu.edu/home/lieber/courses/algorithms/general/quantifier-game/rules

Use Piazza to propose exactly one of the following claims.
Your objective must be to propose true and maximum claims
that nobody can strengthen nor refute.
Try not to make the same claim twice. 
When all true and maximum claims have been made
refute, strengthen  or agree with one of the
claims already on Piazza.
Try not to refute, strengthen or agree the 
same claim twice.

The students who don't propose and oppose/agree
check the consistency of the exchanges. For example,
an independent set of a graph must be a subset of the node
set of the graph.

Claim IntervalScheduling(S,x)
The Interval Scheduling instance S in Fig. 1.4 on page 13
has a subset of compatible requests of size x. Maximize x.
Number the requests left to right and top to bottom.

Claim WeightedIntervalScheduling(S,x)
The WeightedInterval Scheduling instance S in Fig. 6.1 on 
page 252
has a subset of compatible requests of weight x. Maximize x.

Claim BipartiteMatching(G,x):
The bipartite graph G in Figure 1.5 on page 15
has a matching of size x. Maximize x.

Claim IndependentSet(G,x):
The undirected graph G in Figure 1.6 on page 16
has an independent set of size x. Maximize x.

(what follows is similar to Competitive Facility Location (only 2 steps))

Bool = Boolean

Claim QuantifiedBoolean1: 
ForAll x in Bool Exists y in Bool:
  (or (and x y) (and !x !y))

Claim !QuantifiedBoolean1: 
Exists x in Bool ForAll y in Bool:
  (! (or (and x y) (and !x !y)))

Claim QuantifiedBoolean2:
ForAll x in Bool Exists y in Bool:
  (and (or x y) (or !x y) (or x !y))

Claim !QuantifiedBoolean2:
Exists x in Bool ForAll y in Bool:
  (! (and (or x y) (or !x y) (or x !y)))

Some of the claims are true and others are false.


[0,1] real numbers between 0 and 1. 

Claim QuantifiedNumerical(c):
ForAll x in [0,1] Exists y in [0,1] 
  x*y + (1-x)*(1-y^2) >= c
Maximize c.
Family of claims QuantifiedNumerical(c) where c in [0,1].
For example, QuantifiedNumerical(0.5) is a true claim
and QuantifiedNumerical(0.75) is a false claim.
For each value of c between 0 and 1 we have a corresponding
claim which is either true or false. Somewhere between
0.5 and 0.75 there is a maximum c called cmax so that 
QuantifiedNumerical(cmax) is true but for all eps>0, eps a real number,
QuantifiedNumerical(cmax + eps) is false. 

What to turn in:
For each claim say whether it is true or false and for the maximization claims
whether they can be strengthened or are maximum. 
For the true claims give an argument how you defend them against
your partner.
For the false claims give your approach to refute them.

It is sufficient to turn in one document per team of two.
But the postings on Piazza have to be done individually.