Πρώτο Σύνολο Ασκήσεων
Παράδοση 2006.05.02

Οι δυο πρώτες ασκήσεις έχουν σκοπό την εμπέδωση της "θεωρίας" και
έχουν διδαχθεί στην τάξη.

1. Περιγράψτε προσεκτικά τον αλγόριθμο και την ανάλυση του πιθανοτικού
   αλγορίθμου για το MAX3SAT, καθώς και τη εφαρμογή της μεθόδου
   derandomization with conditional probabilities για το συγκεκριμένο
   πρόβλημα. 

2. Δώστε μια απόδειξη της πρότασης: Αν d(v) δηλώνει το βαθμό ενός
   κόμβου v, τότε το μέγιστο ανεξάρτητο σύνολο ενός γράφου έχει
   μέγεθος τουλάχιστον \sum_{v\in V} 1/(1+d(v)).

3. Έστω Υ μια τυχαία μεταβλητή με τιμές στους φυσικούς αριθμούς
   {0,1,2,...}. Δείξτε ότι
          Ε[Υ]^2/Ε[Υ^2] <= P[Y >=1 ] <= E[Y]

4. Έστω ένας τυχαίος γράφος του Gn,p με p=c/n, όπου c κάποια
   σταθερά. Έστω Χ η τυχαία μεταβλητή που εκφράζει τον αριθμό των
   τριγώνων (3-κλικών) σε ένα τέτοιο γράφο. 
   - Με τη βοήθεια της ανισότητας Markov δείξτε ότι P[X>=1]<=c^3/6
   - Με την second moment method δείξτε ότι Pr[X=0]<= (12+9c)/(2c^3).