CR: COMP 2804 Learning Objectives: Difference between revisions
| Line 11: | Line 11: | ||
=Learning Objectives= | =Learning Objectives= | ||
To learn basic tools and techniques from combinatorics and probability theory | |||
which are used in several areas in CS. To learn basic counting techniques, asymptotic analysis, | |||
probability and statistics. Several simple randoimized algorithms (design and analysis) will be discussed | |||
during the course. | |||
=Topics= | =Topics= | ||
Revision as of 17:38, 22 March 2011
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
To learn basic tools and techniques from combinatorics and probability theory which are used in several areas in CS. To learn basic counting techniques, asymptotic analysis, probability and statistics. Several simple randoimized algorithms (design and analysis) will be discussed during the 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.