Instructor: Xue Chen
Email: xuechen@gmu.edu
Location: Online (Zoom Link available on Blackboard)
Class Time: Tuesday 4:30-7:10 pm
Office Hour: Monday 4:00 - 6:00 pm and Tuesday after the class, or by appointment.
TA: Li Zhang (email: lzhang18@masonlive.gmu.edu) Office Hour: Thursday 4 -5 pm (Zoom link on Piazza)
(1) Hash functions: load balancing, balls into bins, cuckoo hashing, bloom filters.
(2) Hash in big data: JL lemma, heavy hitters --- how google/FB/Apple keep track of the most 100 popular websites.
(3) Randomized algorithms: Karger's min-cut algorithm, random walks, MCMC.
(4) Linear program and convex program.
(5) Approximation algorithms.
(6) Algorithms for machine learning/data science: Fourier transform, sparse recovery, sketching.
Except CS 583, I will assume some mathematical maturity. The class is based on theoretical ideas and is proof-heavy. You are expected to be able to read and write formal mathematical proofs. Some familiarity with algorithms and randomness will be assumed as well.
5% participation, 50% homework, 20% midterm exam, and 25% final exam.
All testing is take-home for 12 hours.
We will have 5-6 homework sets. I strongly recommend students to type their answers. Here is one LaTex template file and a LaTex reference from Prof. Dov Gordon (Thanks Dov!).
There is no required textbook. Lecture notes will be available from the Blackboard.
Similar courses with notes offered at Harvard, Columbia, Wisconsin-Madison.
You may find these two books helpful in some topics:
(1) Introduction to algorithms, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, MIT press
(2) Probability and Computing (Randomized Algorithms and Probabilistic Analysis) by Michael Mitzenmacher and Eli Upfal, Cambridge University Press
All coursework is to be done independently WITHOUT reading any published literature or websites besides the class text and notes. Plagiarizing the homework will be penalized by maximum negative credit and cheating on the exam will earn you an F in the course. See the GMU Honor Code System and Policies at George Mason University Honor Code.
Collaboration policy: You are encouraged to collaborate on homework. However, you MUST write up your own solutions. You should also state the names of those you collaborated with on the first page of your submission. Homework that appears overly similar will be considered to violate the honor code.
If you have a learning or physical difference that may affect your academic work, you will need to furnish appropriate documentation to the Disability Resource Center. If you qualify for accommodation, the DRC staff will give you a form detailing appropriate accommodations for your instructor. In addition to providing your professors with the appropriate form, please take the initiative to discuss accommodation with them at the beginning of the semester and as needed during the term. Because of the range of learning differences, faculty members need to learn from you the most effective ways to assist you. If you have contacted the Disability Resource Center and are waiting to hear from a counselor, please tell me.
As a member of the George Mason University community, the department of computer science plays an integral role in building an educational environment that is committed to anti-racism and inclusive excellence. An anti-racist approach to higher education acknowledges the ways that individual, interpersonal, institutional, and structural manifestations of racism against Black individuals and other people of color contribute to inequality and injustice in our classrooms, on our campuses, and in our communities, and it strives to provide our community members with resources to interrupt cycles of racism so as to cultivate a more equitable, inclusive, and just environment for all of our students, staff, faculty, alumni, and friends, regardless of racial background.