Difference between revisions of "CR: COMP 2804 Learning Objectives"
Jump to navigation
Jump to search
(Created page with "=Calendar Description= =Assumed Background= Learning objectives completed before this course. =Learning Objectives= Objectives for the whole course =Topics= ==Topic 1== …") |
|||
| (10 intermediate revisions by 2 users not shown) | |||
| 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= | ||
* COMP 1805 (Minimum grade of B-?) | |||
* MATH 1007 | |||
* MATH 1104 | |||
* COMP 1406 | |||
=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. Design and analysis of several simple randomized algorithms will be discussed | |||
during the course. Statistical ... | |||
=Topics= | =Topics= | ||
* Counting: Permutations, Combinations, Binomial Coefficients, Pigeon-Hole Principle, Inclusion-Exclusion. | |||
* Asymptotic Complexity: O, Theta, Solving recurrence relations. | |||
* Probability: Random Variables, Expected Value, Indicator, Markov Inequality, Chernoff Bounds. | |||
* Randomized Algorithms: Median, Quicksort, Binary Search Trees, Skip Lists, 2-dimensional Linear Programming. | |||
* Statistics: Confidence tests and Intervals, Hypothesis Testing, p-values, chi square, ANOVA (Analysis of Variance) | |||
* Probability distributions: Poisson, normal, power laws (Zipf's law) | |||
Latest revision as of 13:51, 11 April 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 (Minimum grade of B-?)
- MATH 1007
- MATH 1104
- COMP 1406
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. Design and analysis of several simple randomized algorithms will be discussed during the course. Statistical ...
Topics
- Counting: Permutations, Combinations, Binomial Coefficients, Pigeon-Hole Principle, Inclusion-Exclusion.
- Asymptotic Complexity: O, Theta, Solving recurrence relations.
- Probability: Random Variables, Expected Value, Indicator, Markov Inequality, Chernoff Bounds.
- Randomized Algorithms: Median, Quicksort, Binary Search Trees, Skip Lists, 2-dimensional Linear Programming.
- Statistics: Confidence tests and Intervals, Hypothesis Testing, p-values, chi square, ANOVA (Analysis of Variance)
- Probability distributions: Poisson, normal, power laws (Zipf's law)