Description

Meeting times: Tue, Thu 2:10pm-3:30pm
Location: PEARSON 2125

General Information

Textbooks
The textbook for the course is "Probability and Computing: Randomized Algorithms and Probabilistic Analysis" by Michael Mitzenmacher and Eli Upfal.

The following book is recommended: "Randomized Algorithms" by Rajeev Motwani and Prabhakar Raghavan.

You will not regret buying either of these books.

Announcements

Final project due date + class on 5/1
4/30/14 12:47 PM

Your project is report is due by the end of day on May 4th. Please email it to me.

Please plan to attend class tomorrow. In addition to presentations by three students, I will give out the course evaluations, and it is very important for me to get your feedback. Thank you.

Reading for Data Stream Algorithms for Thu 3/27
3/26/14 3:09 AM

Please read the following paper from VLDB 2013 before Thursday's class:

Counting and Sampling Triangles from a Graph Stream

This is available at the following URL.

http://www.ece.iastate.edu/~snt/pubs/vldb13.pdf

Homework 4 (Bloom Filter): deadline extended till Thursday 3/13
3/10/14 2:10 PM

All:

I am extending the deadline for homework 4 (Bloom filter). It is no longer due on Tuesday 3/11, but due on Thursday 3/13, in class.

--Srikanta

Homework 4 : Bloom Filter
3/06/14 1:29 PM

All:

For the homework assignment on Bloom Filter, your task is:

1) Find an existing application of Bloom Filter, different from the ones we saw in class. The database and networking literature has many such instances.

2) Describe how the Bloom Filter helps (or if you disagree, also explain why).

3) Describe why false positives are not a problem (or if you disagree, also explain why).

You should give me a writeup with these answers in class on Tuesday 3/11. Please provide references to the work that you are describing, and describe the answers in your own words.

--Sri

Guidelines for Class Project and Presentation
2/27/14 1:23 PM

Dear Students:
The following are the requirements for your class project.
1. You should inform me about the project topic by March 15th. Along with the topic, please also give an abstract (20 lines or less) about what you will study as a part of your project.

2. You should meet with me at least two times, once to discuss the tasks for the project, and once to discuss your preparation for the presentation.

3. You have to write a 6-10 page report discussing your work. A guideline for the report is as follows.
A. What is the problem you are looking at? Why is it important?
B. What are the currently known techniques for the problem?
C. What is the application of probability here? You can discuss the techniques in your own words, but the material itself can be drawn from prior research work.
D. What did you do to test/validate/improve on existing work on this problem?
E. Conclusion. Here you can make a statement about the suitability of existing techniques, and what you learnt from the project.
F. List of references. I expect to see at least five, if not more relevant references.


4) You have to give a presentation in class. A rough outline for the presentation could be as follows.

First explain the problem and its importance. For example, you could start off with "look at the prevalence of disease X in the world, it affects 20% of the people, we really need to stop it. Now I am going to talk about stopping disease X". Give some data here if possible to get the listeners interested. If you are working on an abstract problem, then you can describe the beauty/fundamental nature of the problem, so that we all start paying attention. For example, you could say "I will talk about Solving Diophantine equations. Here is an example of a Diophantine equation.. It is a basic problem, which
appears in X Y Z scenarios.. And it has been studied for ... years." Basically, whatever it is that attracted you to this problem, you should convey to the audience. Usually, a precise problem statement should appear at the end of this section.

Now is a good time for an outline of the talk. You could have a punchline saying "at the end of this presentation, you will know about the following...".

Next, describe the solution that you have studied. Be as precise as possible given the time limit. Define any variables, tools that you are using. Give time to describe the intuition. Define every symbol that you use on the slide.

As much as possible, have one idea per slide. This will help to focus the content. Needless to say, have as many pictures as possible, especially in describing the solution and the intuition.
Next present your work. If you are implementing an algorithm, describe the difficulties you found/anticipate in the implementation.

Conclusion/recap.


class canceled today (2/20/14)
2/20/14 12:09 PM

Dear Students:

Due to bad weather, Iowa State is canceling today's afternoon classes. We are not meeting today at 2pm, and we will be discussing skip lists on Tuesday.

-Srikanta

Topic for class on 2/20, Thursday
2/19/14 6:18 PM
I will cover "skip list", a simple data structure that is an alternative to a search tree. Please see http://en.wikipedia.org/wiki/Skip_list for an introduction. I will cover the data structure and the analysis in class.
Homework 3 has been added to class homepage under Resources
2/19/14 1:45 PM

The teaching staff has posted a new homework resource.

Title: Homework 3
http://www.piazza.com/class_profile/get_resource/hpdhxdd3uq83t2/hrv0ewsqjok7gc

Due date: Mar 4, 2014

You can view it on the course page: https://piazza.com/iastate/spring2014/cpre528/resources

Staff Office Hours
NameOffice Hours
Srikanta Tirthapura
When?
Where?
Sneha Aman Singh
When?
Where?