Difference between revisions of "CR: COMP 2804 Learning Objectives"
Jump to navigation
Jump to search
(→Topics) |
|||
| Line 1: | Line 1: | ||
=Calendar Description= | =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= | =Assumed Background= | ||
Revision as of 13:32, 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
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.