COMP2711 (L1) - Discrete Mathematical Tools for Computer Science - Fall 2020

COMP 2711,  L1	Prof. Dimitris Papadias, Rm 3555, dimitris@cse.ust.hk	Tue, Thu: 1:30-2:50
Tutorial T1A	TBA	Mon: 6:00-6:50
Tutorial T2	TBA	Wed: 1:30-2:20

Description
This course presents basic concepts in discrete mathematics needed for the study of computer science: logic and proofs, number theory, combinatorics, probability theory, induction and recursion, and basic graph theory. The approach of this course is specifically computer science application oriented.

Textbook
Discrete Mathematics and its Applications. Kenneth H. Rosen, 7th Edition, McGraw-Hill

Tentative Grading Scheme
Assignments, Quizzes, Polls 50%
Final Exam 50%

Slides and Video Links

We will post in advance the slides for the coming week. After each lecture, we will also post a link to the video of the lecture, and the updated slides which may contain additional exercises solved during the lecture. 

Topics

• Introduction, Propositional Logic, Quantifiers
• Inference
• Sets and Functions, Basic Counting
• Binomial Coefficient, More Counting
• Probability, Inclusion and Exclusion
• Independence, Random Variables
• Random Variables
• Variance, Wrap-Up Probability
• Number Theory, Inverses and GCDs
• RSA Algorithm
• Induction
• Recurrence, Complexity
• Algorithms, Advanced Induction
• Graphs (if there is enough time)

Coordination among lecture sections
All three lecture sections will cover the same material, but may cover it at different pace. All sections will have the final exams and assignments/tutorials/quizzes.

Course Outcomes
On successful completion of this course, students are expected to be able to:

• Understand the formulation of common problems in several areas of discrete mathematics, including combinatorics, number theory and cryptography, logic and proof, recursion and recurrences, probability theory and graph theory.
• Understand the connection between the discrete mathematical tools learned and some core computer science topics covered later in the curriculum, including computational complexity, information security, recursive functions and data structures.
• Apply the mathematical techniques learned to solve problems in a range of topics.
• Demonstrate a level of mathematical maturity by solving problems using an array of different proof techniques.

See CANVAS page for slides and video recordings of the lectures