Skip to content Skip to navigation

01:198:206 - Introduction to Discrete Structures II

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:20201:640:152. Credit not given for this course and01:640:477 or 14:332:226.

Please note that courses for which a student has received a grade of D cannot be used to satisfy prerequisite requirements.

Semester: 
Fall
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).
Course Type: 
Undergraduate
Course Name: 
Introduction to Discrete Structures II