Advanced Algorithms 2021 spring

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)

Description

The class covers classic and modern algorithmic ideas that are central to many areas of Computer Science. The goal for the class is to be broad rather than deep. The focus is on most powerful paradigms and techniques of how to design algorithms and analyze their performance. Besides advanced algorithmic techniques, we will also explore a variety of applications.

(Tentative) Course outline

(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.

Course requirement

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.

Grading

5% participation, 50% homework, 20% midterm exam, and 25% final exam.

All testing is take-home for 12 hours.

Homework

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!).

Text and references

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

Homework Policies

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.

Late policy: Each homework set will be due on Tuesday before the class. Each student gets 3 free late days for homework during the semester. However, use of these days must be announced in advance on blackboard.

Disability statement

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.

Diversity statement

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.