Skip to content Skip to navigation

Introduction to Discrete Structures II

01:198:206

Provides the background in combinatorics and probability theory required in design and analysis of algorithms, in system analysis, and in other areas of computer science.

Credits: 
4
Prerequisite: 

01:198:205 or 14:332:202; 01:640:152. Credit not given for this course and 01:640:477 or 14:332:226.

A grade below a "C" in a prerequisite course will not satisfy that prerequisite requirement.
Semesters: 
Fall, and Spring
Topics: 

Counting: Binomial Coefficients, Permutations, Combinations, Partitions.
Recurrence Relations and Generating Functions.
Discrete Probability:
Events and Random Variables;
Conditional Probability, Independence;
Expectation, Variance, Standard Deviation;
Binomial, Poisson and Geometric Distributions; law of large numbers.
Some Topics from Graph Theory: Paths, Components, Connectivity, Euler Paths, Hamiltonian Paths, Planar Graphs, Trees.

Expected Work: 

Weekly assignments

Exams: 
1 or 2 tests, Final Exam
Learning Goals: 
Computer Science majors ...
  • will be prepared to contribute to a rapidly changing field by acquiring a thorough grounding in the core principles and foundations of computer science (e.g., techniques of program design, creation, and testing; key aspects of computer hardware; algorithmic principles).
  • will acquire a deeper understanding on (elective) topics of more specialized interest, and be able to critically review, assess, and communicate current developments in the field.
  • will be prepared for the next step in their careers, for example, by having done a research project (for those headed to graduate school), a programming project (for those going into the software industry), or some sort of business plan (for those going into startups).