CS 410 Top: Counting, Probability and Computing
| Credit Hours: | 4 |
| Course Coordinator: | N/A |
| Course Description: | Probability, particularly discrete probability, has become indispensable in computer science. Cryptography, algorithm design, network routing, artificial intelligence, optimization, and large data set analysis (to name just a few) all make heavy use of probablistic methods and reasoning. This course gives an introduction to probablistic techniques relevant to computer science. Since much of discrete probability can be reduced to counting, this course will also teach basic enumerative conbinatorics. The class will be largely problem based, with some portion of most class periods spent in small groups solving problems. There will be few, if any, programmining assignments. |
| Prerequisites: | CS 250 and 251, or equivalents |
| Goals: | |
| Textbooks: | |
| References: | |
| Major Topics: | Time and student interest permitting, this course will cover all of the following topics: * Basic counting: combinations, permutations, multinomials, inclusion-exclusion * Probability basics: sample spaces, events, axioms of probability * Random variables and expectation: Bernoulli, Binomial, Geometric, Hypergeometric, Negative Binomial distributions; dependent and independent random variables * Balls and Bins problems: the birthday paradox and its cousins, the Poisson approximation * Generating functions and recurrence relations * Tail bounds: Markov and Chebyshev bounds * Entropy and Information theory basics * Markov processes * Martingales and concentration inequalities |
| Laboratory Exercises: |
| CAC Category Credits | Core | Advanced |
| Data Structures | ||
| Algorithms | ||
| Software Design | ||
| Computer Architecture | ||
| Programming Languages |
| Oral and Written Communications: | |
| Social and Ethical Issues: | |
| Theoretical Content: | |
| Problem Analysis: | |
| Solution Design: |