CSE 312

Foundations of Computing Ii

Credits
4.0
Lead Instructor
Martin Tompa
Textbook
Course Description
Examines fundamentals of enumeration and discrete probability; applications of randomness to computing; polynomial-time versus NP; and NP-completeness.
Prerequisites
CSE 311; CSE 332, which may be taken concurrently.
CE Major Status
Required
Course Objectives
Course goals include an appreciation and introductory understanding of (1) methods of counting and basic combinatorics, (2) the language of probability for expressing and analyzing randomness and uncertainty (3) properties of randomness and their application in designing and analyzing computational systems, (4) some basic methods of statistics and their use in a computer science & engineering context
ABET Outcomes
(a) an ability to apply knowledge of mathematics, science, and engineering
(e) an ability to identify, formulate, and solve engineering problems
(l) knowledge of probability and statistics
(m) knowledge of discrete mathematics
Course Topics

  • permutations, combinations
  • pigeonhole principle
  • inclusion-exclusion
  • probability axioms
  • conditional probability
  • law of total probability
  • Bayes' Rule
  • independence
  • random variables
  • expectation and variance
  • joint distributions
  • binomial distribution, geometric distribution, Poisson distribution,
  • continuous random variables
  • uniform distribution, exponential distribution, normal distribution
  • central limit theorem
  • randomized algorithms
  • Markov and Chebyshev inequalities
  • Chernoff bounds
  • law of large numbers
  • maximum likelihood estimate