Homework 1
Algorithms and Data
					Karl Lieberherr

Out: September 7, 2011
Due: September 15, 2011

Reading: Chapter 1
Study table 2.1 on page 34.
Read section 4 "Quantifiers as games" in
http://www.ccs.neu.edu/home/lieber/courses/algorithms/general/pros.pdf

Sign up for the Mailing List on the course Home Page
by Monday of the second week.

----------------------------------
Objectives:
Designing a simple algorithm from scratch
  while playing the Quantifier Game
Distinguish true from false mathematical claims
Learning to defend a true mathematical claim
Learning to refute a false mathematical claim

Mathematical claims as requirements:
An existential quantifier in a true mathematical claim
plays the role of defining a function (Skolem function).

Working with ForAllExists and ExistsForAll claims.
Transition from finding counterexamples to finding a winning strategy.
----------------------------------

Terminology: claim is a synonym for sentence.

Part 1:
Exercise 1 Chapter 1. 
=========================================

Part 2:
Exercise 2 Chapter 1.
=========================================

Part 3:
Variables usage:
All variables range over the rational numbers.
All variables are in the interval [0,1].

We consider claims of the form:
Claim k(c):
For all  [x in [0,1]] Exists [y in [0,1]] (x*y + (1-x)(1-y^2)) >= c

and their negation:
!k(c):
Exists  [x in [0,1]] ForAll [y in [0,1]] (x*y + (1-x)(1-y^2)) < c

Consider 
k(0.62), k(0.61), !k(0.62), !k(0.61).

Which of those claims are true claims?
To sharpen our intuition we engage Alice and Bob
to play a game: (Alice is you and Bob is your partner)

Let f(x,y)=(x*y + (1-x)(1-y^2)).

Alice claims k(0.61).
Bob opposes by strengthening the claim to k(0.611).
Alice tries to refute k(0.611) as follows:
Alice provides x0, Bob provides y0 so that: f(x0,y0)>=0.611.
If Bob succeeds, he has defended his strengthening
and otherwise if f(x0,y0)<0.611 Bob has not successfully
strengthened and Alice wins.

Alice claims !k(0.62).
Bob opposes by strengthening the claim to !k(0.619).
Alice tries to refute !k(0.619) as follows:
Bob provides x0, Alice provides y0 so that f(x0,y0)<0.619.
If Bob succeeds, he has defended his strengthening
and otherwise if f(x0,y0)>=0.619 Bob has not successfully 
strengthened and Alice wins.

This kind of game helps to gain insight into the
problem and it might give us the idea for a proof
that k(c) holds or !k(c) holds.

What is the maximum value of c, called cmax, so that k(cmax) is true
but k(cmax + epsilon) is false for epsilon arbitrarily small?

Find an algorithm, called GoldenDefenseStrategy,
that takes as input x and c and produces 
y=S1(x,c) so that f(x,S1(x,c)) >= c.
S1 is called a Skolem function for the existential quantifier.

Algorithm GoldenDefenseStrategy provides the winning 
strategy to defend true claims k(c).

To compute a lower bound on cmax, use the simplest possible 
function S1: the identity function S1(x,c)=x.

To help with the calculus, I suggest you use WolframAlfa:
Try one line at a time:
plot 1-x+x^3
derivative of 1-x+x^3
solve 3*x^2-1=0
which gives you a lower bound of 0.6151 for cmax.

Wolfram|Alpha is a computational knowledge engine, 
not a search engine. It is pretty easy to use.

Useful commands:
Partial derivatives, e.g., d/dy (3 + (-3 + y) y + x (-2 + y (3 + y)))/4
Partial interpretation, e.g., 
(x*y + (1-x)(1-y^2)) >= c where c=0.61, x=0.57, y=0.21 
(x*y + (1-x)(1-y^2)) where x=y

How can you improve on the identity function to achieve
a better value and find the true cmax?

Find an algorithm, called GoldenRefutationStrategy  
that takes as input a value c > cmax and produces
x=S2(c) so that for all y: f(S2(c),y) < c.

Algorithm GoldenRefutationStrategy
provides the winning strategy to refute
false claims when c is too high.

The general picture is that in order to defend a claim
of the form Exists x-ForAll y, we need to find a "hard"
or "worst-case" x to win. Such an x is often called a
counterexample.

Part 4:
Consider claim k2(c) =
ForAll x in [0,1] Exists y in [0,1]:
  (x*y + (1-x)(1-y^3)) >= c

Find a cmax so that you can defend the claim k2(cmax)
and refute the claim k2(cmax+1/1000).


What to turn in:

Part 1:
Winning strategy to defend or refute.

Part2:
Winning strategy to defend or refute.

Part 3:
Winning strategies to defend or refute
claims of the form k(c) for c >=0.61 and <=0.62.
What is the value of cmax?
What is the value of cmax if we allow the variables
to be real numbers?
Where in table 2.1 of the text book do you position algorithm
GoldenDefenseStrategy?

Part 4:
Winning strategies to defend or refute.
What is the value of cmax?
What is the value of cmax if we allow the variables
to be real numbers?

Part 5:
Answering the questions in this homework requires
the application of lots of algorithms.
Make a list of algorithms that are used.
Some examples of algorithms are:
Addition and multiplication of rational numbers.
Solving a linear or quadratic equation.
Taking the (partial) derivative of a function.
Etc.