Syllabus for Computer Science 202a, Mathematical Tools for Computer Science. Instructor: James Aspnes.

1. Meeting times

Lectures are Mondays, Wednesdays, and Fridays from 11:30am to 12:20pm in AKW 500.

2. On-line course information

On-line information about the course, including copies of all handouts, can be found using the URL http://pine.cs.yale.edu/pinewiki/CS202. This will also be the main location for announcements about the course, lecture schedules, and so forth. Please check it frequently.

3. Readings

Kenneth H. Rosen, Discrete Mathematics and Its Applications, Sixth Edition, McGraw-Hill, 2006. ISBN 0073312711. QA39.3 R67X 2007 (LC).

4. Course requirements

Ten weekly homework assignments (approximately 50 percent of the grade), a midterm (15 percent), and a final (35 percent).

5. Use of outside help

Students are free to discuss homework problems and course material with each other, and to consult with the instructor or a TA. Solutions handed in, however, should be the student's own work. If a student benefits substantially from hints or solutions received from fellow students or from outside sources, then the student should hand in their solution but acknowledge the outside sources, and we will apportion credit accordingly. Using outside resources in solving a problem is acceptable but plagiarism is not.

6. Clarifications for homework assignments

From time to time, ambiguities and errors may creep into homework assignments. Questions about the interpretation of homework assignments should be sent to the instructor at <aspnes@cs.yale.edu>. Clarifications will appear in the on-line version of the assignment.

7. Late assignments

Late assignments will not be accepted without a Dean's Excuse.

8. Topics

List of things you should know about if you want to do ComputerScience. Italicized entries are not covered in CS202.

Things you should already know about:

High school algebra: solving equations etc.
High school calculus: derivatives, integrals. (Not actually required but will be more useful than you think.)

Things you should learn somewhere along the way:

Logic
- Propositional logic: ¬, ∧, ∨, ⇒, ⇔
- First-order logic: ∀, ∃, P(x)
- Equality and uniqueness
Proofs
- Direct proofs
  - Proving P ∧ Q
  - Proving P ∨ Q
  - Proving P ⇒ Q
  - Proving P ⇔ Q
  - Proving ¬P
  - Proving statements with quantifiers: ∀x P(x), ∃x P(x)
- Indirect proofs
- Induction
Mathematical structures
- The natural numbers ℕ; Peano axioms
- Sets
  - Membership (∈), subsets (⊆)
  - Comprehension: { x ∈ S | P(x) }
  - Unions (A∪B), intersections (A∩B), and set differences (A\B)
  - Power sets
  - Proving equality
  - Russell's Paradox, ZFC axioms
- Relations
- Functions
  - Injections, surjections, and bijections
  - Inverses
  - Composition
- Orders
  - Partial orders
  - Total orders
  - Well orders
  - Ordinals and order types
Graphs
- Undirected graphs
- Directed graphs
- Subgraphs
- Special classes of graphs
  - Paths
  - Cycles
  - Trees
  - Bipartite graphs
- Hypergraphs
Algebraic structures
- Semigroups
- Monoids
- Groups
  - Cyclic groups
  - Products
  - Abelian groups: definition, classification of finite abelian groups
  - Homomorphisms
- Rings
- Fields
- Vector spaces
- Lattices and Boolean algebras
- Categories
Standard algebraic structures
- Integers: ℤ
- Integers mod m: ℤ_m
- Rationals: ℚ
- Reals: ℝ
- Complex numbers: ℂ
Tools for algorithm analysis
- Inequalities
- Asymptotic notation
- Sums
- Recurrences
Combinatorics
- Counting
- Binomial coefficients
- Stirling numbers
- Generating functions
Linear algebra¹
- Vectors
- Vector addition
- Dot-product
- Matrices and linear transformations
  - Matrix multiplication
  - Transposition
  - Inverses
  - Eigenvalues and eigenvectors
  - Complex matrices
- Subspaces
  - Bases
  - Projections
  - Subspaces associated with matrices
Probability
- Probability spaces and probability axioms
- Basic probability laws
- Conditional probability
- Expectation and related concepts
  - Expectation
  - Variance
  - Conditional expectation
- Stochastic processes
  - Markov chains
  - Poisson processes
  - Martingales and stopping times
Number theory
- Divisibility
  - Primes and composites
  - Prime factors
  - GCD
- Structure of ℤ_m
  - Chinese Remainder Theorem
  - Fermat's Little Theorem
  - Inverses in ℤ^*_p
  - Cryptographic primitives: RSA, Diffie-Hellman, discrete logarithm

CategoryMathNotes

Very important for many areas. You should plan on taking at least one linear algebra course if you plan to do anything involving graphics, robotics, scientific computing, vision, or neural networks. The puny linear algebra you will get in ["CS202"] will be no match for these superior electives. (1)