Calendar Description

COMP2804 Discrete Structures II

Introduction to discrete mathematics and discrete structures. Topics include: counting, sequences and sums, discrete probability (including random variables, expectation, linearity of expectation, dependence, concentration results, distributions), recurrence relations. Material is illustrated through examples from computing.

Assumed Background

COMP 1805

Learning Objectives

Objectives for the whole course

Topics

Counting: Permutations, Combinations, Binomial Coefficients, Pigeon-Hole Principle, Inclusion-Exclusion.
Asymptotic Complexity: O, Theta.
Probability: Random Variables, Expected Value, Indicator, Markov Inequality, Chernoof Bounds.
Randomized Algorithms: Median, Quicksort, Binary Search Trees, Skip Lists, 2-dimensional Linear Programming.
Statistics: Confidence tests and Intervals, Hypothesis Testing.