CSC 495/591 - CS Theory Toolkit (Spring 2025)

Course Description | Evaluation | Schedule | Resources

Course description

This course showcases how different areas of mathematics can be useful in computer science. We will study several mathematical tools such as Algebra (Groups, Rings, Fields), Matrix theory, (Discrete) Probability, Fourier analysis, and see how they are used in developing modern algorithms and proving impossibility results in various areas in computer science.

This covers some of basic tools that would be useful for students who are interested in doing research in the theory side of computer science.

Prerequisites and Homework 0

You are expected to be familiar with topics covered in Discrete Math (CSC 226), Data structures and Algorithms (CSC 316). In particular, it is important to refresh your memory on the following concepts before coming to class:

• Asymptotic notations (e.g. Big-O and Big-Omega)
• Basic counting and graph theory
• Proof techniques such as proof by contradiction, proof by induction, proof by counterexample (and NEVER by examples). As with every theory course, you will encounter many proofs in class and will be required to write proofs in homeworks and exams.

The free book "Mathematics for Computer Science" by Lehman, Leighton, and Meyer is an excellent resource for learning these concepts. It also comes with a set of online lectures.

Evaluation

To be decided

Tentative Topics

• Hashing
• Randomized algorithms
• Sublinear algorithms
• Communication complexity

Resources