Core Knowledge and Skills
ICS 6D: Discrete Mathematics for Computer Science
Other courses:
21 |
22 |
23 | 51 |
52 | 132
ICS 6D
Catalog Description |
Covers essential tools from discrete mathematics used in computer
science with an emphasis on the process of abstracting computational
problems and analyzing them mathematically. Topics include:
combinatorics, mathematical induction, elementary probability, and
asymptotic analysis. |
ICS 6D
Course Prerequisites |
High school mathematics through trigonometry. |
ICS 6D
Restrictions |
|
ICS 6D
Knowledge Prerequisites: Skills and Concepts |
|
ICS 6D
Minimum Knowledge and Skills |
Logic
- Mastery:
- Understand and apply logical connectives, and operators
- Construct truth tables
- Determine whether Boolean expressions are logically
equivalent using truth tables
- Construct proofs of logical equivalences of Boolean
expressions using truth tables
- Proficiency:
- Convert from Boolean expressions to English sentences
- Convert from English sentences to Boolean expressions
- Determine whether Boolean expressions are logically
equivalent using logical identities
- Construct proofs of logical equivalences of Boolean
expressions using logical identities
Sets
- Mastery:
- Understand and apply set operations, Venn diagrams
- Understand and apply computer representations of sets
- Construct proofs of set identities using membership
functions
- Proficiency:
- Construct proofs of set identities using set operations,
identities
Sequences and sums
- Mastery:
- Understand and apply the definition of sigma notation
- Convert to and from sigma notation
- Evaluate terms of a geometric series
- Compute the sum of a geometric series
Combinatorics
- Mastery:
- Understand and apply basic counting principles: sum rule,
product rule, inclusion-exclusion, pigeonhole principle
- Understand and apply formulas for counting permutations
and combinations of distinguishable objects without repetitions
- Understand and apply basic formulas involving binomial
coefficients and Pascal's triangle
- Understand and apply formulas for counting permutations
and combinations of distinguishable objects with repetitions allowed
- Understand and apply formulas for counting permutations
with indistinguishable objects
- Exposure:
- Apply definitions and basic formulas involving binomial
coefficients to derive more complicated identities (e.g., Vandermonde's
identity)
- Understand and apply generalized inclusion-exclusion
principle
Probability
- Mastery:
- Understand and apply basic concepts from probability: Sample
spaces, combinations of events, computing simple probabilities
- Understand and apply conditional probability,
independence
- Understand and apply definition of random variables,
expectations
- Proficiency:
- Understand and apply definition of Bernoulli trials, binomial
distribution
- Exposure:
- Understand concept of average-case computational complexity
- Understand, apply, and compute variance, standard
deviations
Proof techniques and methods
- Mastery:
- Understand the difference between direct proofs, indirect
proofs, and proofs by contradiction, and construct simple examples of
each
- Understand and apply principle of mathematical induction;
construct proofs by induction
- Exposure:
- Understand and construct nonconstructive existence proofs
Recursion and recurrences
- Mastery:
- Understand and construct recursive definitions
- Understand and construct recurrence relations
- Solve simple recurrence relations
- Proficiency:
- Solve linear recurrence relations
- Solve divide-and-conquer recurrences
- Exposure:
- Understand and apply generating functions
|
Return
to top of page