This third assignment will (hopefully) give you greater insight into the various complexity classes.
This is a substantive assignment, worth 15 points towards your final grade. Please start it early and don't leave it until the last minute.
You must submit a PDF of your submission to me by email only, no later than Wednesday April 9 at 23:59.
Do exercises 10.3, 10.6 and 11.12 from the book.
Do exercises 12.1 and 12.4 from the book.
Do exercises 13.7, 13.9 and 13.11 from the book.
Information dissemination through social networks is an interesting and currently very relevant problem. Predicting or modelling whether a particular piece of information will reach a critical number of users is often computationally challenging.Â
Do some research on this problem and write a short summary of your perspective/opinion on the following issues:
The complexity of modelling information dissemination and what factors would influence which complexity class a particular proposed approach might belong to.
The complexity of verifying whether a particular information spread pattern is achievable.
Clearly state your assumptions/relevant factors which went into your analysis, and feel free to add useful citations which support your answer(s).