Instructor: Feng-Hao Liu
email: fenghao.liu@fau.edu
Office: Engineering East 529
Office Hour: 2pm- 4pm every Wednesday. Additional time: 10:30am – 12:30 pm Aug 21 (Fri).
Course Information
Place: Computing Bldg Boca 128
Time: 11:00 am – 12:20 pm, Tuesday and Thursday
Course description: Probability, randomness, statistics have been playing an important role in computer science, ranging from purely theoretical studies (e.g. complexity theory) to highly practical applications (e.g. secure communication, page ranking, network routing, etc.) Research in the related fields has been extremely active since the past three decades.
This course will introduce several basic techniques in the design and analysis of randomized algorithms. With each technique, we will demonstrate various applications to see how it can be applied. We will see how and why randomness can be so powerful; in particular we will discuss its advantages over deterministic algorithm, and as well its limitations.
Here is a list of topics that we would like to cover. (The syllabus can be found here as well.) Please feel free to contact me if you have questions about the course.
- Introduction: the power of randomness in computer science
- Background of (discrete) probability: random variables, expectations
- Chernoff bounds and applications
- Balls, bins, and random graphs
- The probabilistic methods
- Markov chains and random walks
- Entropy, randomness, and information
- Other selected topics (e.g. Monde Carlo methods, Martingale, Derandomization, Applications in Cryptography)
Textbook: Probability and Computing: Randomized Algorithm and Probabilistic Analysis
Lectures
See the Blackboard.
Homework Assignments
See the Blackboard.