Instructor: Prof. Linyuan Lu
Office: LC 400I, 409
Email: lu@math.sc.edu
Office hours: TTh 12:00PM-1:30PM or by appointment.
Lecture time: TTh & 10:05AM- 11:20AM, LC 310
Credit Hours: 3
Prerequisite: some background in graph theory and probability.
Reference textbook: Probabilistic methods (3rd edition), by Noga Alon, Joel H. Spencer, Wiley, 2008, ISBN: 978-0-470-17020-5 or fourth edition ISBN-13: 978-1119061953.
Overview: The probabilistic method is a nonconstructive method, primarily used in combinatorics and pioneered by Paul Erdos, for proving the existence of a prescribed kind of mathematical object. It works by showing that if one randomly chooses objects from a specified class, the probability that the result is of the prescribed kind is strictly greater than zero. Although the proof uses probability, the final conclusion is determined for certain, without any possible error.
This method has now been applied to other areas of mathematics such as number theory, linear algebra, and real analysis, as well as in computer science (e.g. randomized rounding), and information theory.
Learning Outcomes: On successful completion of this course, graduate students will be able to:
Subject Material: The course will begin with a description of tools applied in probabilistic arguments, including basic techniques such as expectation, variance, martingales, and correlation inequalities. We will also examine selected topics where probabilistic techniques have been applied successfully such as random graphs, phase transition, discrepancy, circuit complexity, computational geometry, and derandomization of randomized algorithms.
Assessment: The assessment consists of homeworks, an exam, and a final project. Homework will normally be assigned every other week. Although you can discuss the problems with others, you should write (type) up your homework solutions independently. A final project consists of reading a paper and presenting it into the class.
Grading: The breakup grades are homework 50%, exam 25%, and final project 25%. Your final grade is based on the percentage as follows.
Grading Scale
Grading Scale: | 90-100% A |
76-79% C+ |
60-65% D |
86-89% B+ |
70-75% C |
0-59% F |
|
80-85% B |
66-69% D+ |
|
Lecture notes: