[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

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.

9. Foundations and logic

Why: This is the assembly language of mathematics—the stuff at the bottom that everything else complies to.

  • Propositional logic.
  • Predicate logic.
  • Axioms, theories, and models.
  • Proofs.
  • Induction and recursion.

10. Fundamental mathematical objects

Why: These are the mathematical equivalent of data structures, the way that more complex objects are represented.

  • Naive set theory.
    • Predicates vs sets.
    • Set operations.
    • Set comprehension.
    • Russell's paradox and axiomatic set theory.
  • Functions.
    • Functions as sets.
    • Injections, surjections, and bijections.
    • Cardinality.
    • Finite vs infinite sets.
    • Sequences.
  • Relations.
    • Equivalence relations, equivalence classes, and quotients.
    • Orders.
  • The basic number tower.
    • Countable universes: ℕ, ℤ, ℚ. (Can be represented in a computer.)
    • Uncountable universes: ℝ, ℂ. (Can only be approximated in a computer.)
  • Other algebras.
    • The string monoid.
    • ℤ/m and ℤ/p.
    • Polynomials over various rings and fields.

11. Modular arithmetic and polynomials

Why: Basis of modern cryptography.

  • Arithmetic in ℤ/m.
  • Primes and divisibility.
  • Euclid's algorithm and inverses.
  • The Chinese Remainder Theorem.
  • Fermat's Little Theorem and Euler's Theorem.
  • RSA encryption.
  • Galois fields and applications.

12. Linear algebra

Why: Shows up everywhere.

  • Vectors and matrices.
  • Matrix operations and matrix algebra.
  • Geometric interpretations.
  • Inverse matrices and Gaussian elimination.

13. Graphs

Why: Good for modeling interactions. Basic tool for algorithm design.

  • Definitions: graphs, digraphs, multigraphs, etc.
  • Paths, connected components, and strongly-connected components.
  • Special kinds of graphs: paths, cycles, trees, cliques, bipartite graphs.
  • Subgraphs, induced subgraphs, minors.

14. Counting

Why: Basic tool for knowing how much resources your program is going to consume.

  • Basic combinatorial counting: sums, products, exponents, differences, and quotients.
  • Combinatorial functions.
    • Factorials.
    • Binomial coefficients.
    • The 12-fold way.
  • Advanced counting techniques.
    • Inclusion-exclusion.
    • Recurrences.
    • Generating functions.

15. Probability

Why: Can't understand randomized algorithms or average-case analysis without it. Handy if you go to Vegas.

  • Discrete probability spaces.
  • Events.
  • Independence.
  • Random variables.
  • Expectation and variance.
  • Probabilistic inequalities.
    • Markov's inequality.
    • Chebyshev's inequality.
    • Chernoff bounds.
  • Stochastic processes.
    • Markov chains.
    • Martingales.
    • Branching processes.

16. Tools

Why: Basic computational stuff that comes up, but doesn't fit in any of the broad categories above. These topics will probably end up being mixed in with the topics above.

These you will have seen before:

  • How to differentiate and integrate simple functions.
  • Things you may have forgotten about exponents and logarithms.

These may be somewhat new:

  • Inequalities and approximations.
  • ∑ and ∏ notation.
  • Computing or approximating the value of a sum.
  • Asymptotics.


2014-06-17 11:57