**Texts: **Discrete
Mathematics
and its Applications, Rosen, McGraw Hill, 8th edition.

You can
use Edition 7 as well -- whichever is cheaper for you to find.

Pettofrezzo, Anthony J. Matrices and Transformations. New York: Dover, 1978.

**Assignments:** Homework
assignments are worth 40% of your grade. You may do
these with a partner, and one grade will be given to both people
in the group. Read our department's academic integrity
guidelines before you hand in any written work.

**Grading: **Your grade is
25% quizzes, 40% homework, and 35% exam. You can guarantee
an A- or better with 90%, a B- or better with 80% etc. I may
curve these numbers in your favor, if I feel it is warranted.

**Goals: **To understand the
mathematics that underlies computer science, and to appreciate
where it is used. Last semester concentrated on functions,
number theory, recurrence equations, recursion, combinatorics, and
their applications. This semester concentrates on sets,
graphs, Boolean algebra, linear algebra, and their applications.

**Special Dates:** There will
be no class Wednesday April 15 due to Passover. I will
probably schedule an in-class quiz.

Web
Mining Using Eigenvalues The Paper |
Math at Google | Math in CS | Halting
Problem Video |

Monopoly Markov Chain | Matrix Calculator | Wolfram Alpha | My
Video Lectures |

- Week 0: If you haven't done it yet, then read How to Read Mathematics.
- Week 1-2: Bit
Manipulation and Useful Hacks.

- Week 1-2: Read this cute but accurate poem-proof
that the Halting Problem is Undecidable.

- Week 13-14: Read Google's Ranking Method to learn why computer scientists need to know about all this linear algebra.

Assignment
1(Due Friday, Feb. 7) |
Assignment_2 (Due Friday, February 28) |
Assignment
3(Due Friday, March 27) |
Assignment
4(Due Friday, April 17) |
Assignment
5(Due before Final) |

Week | Topics | Reading |

1-2 | Set
Theory - Inclusion/Exclusion Theorem. Set Algebra: Associative, Distributive, and De Morgan's Laws. Applications of sets: Bit Operations in Java, Union-Find data structure, functions, 1-1 correspondence, and Countability - Diagonalization. and applications to Computability and Undecidability. |
Rosen: 2.1 - 2.5, 8.5 |

3-4 |
Boolean
Algebra. Truth tables. Applications to Propositional
and First Order Logic - Predicates, Quantifiers,
Formal proofs of Set Theorems Applications to automatic theorem proving, and Resolution. Prolog and AI. EightQueens-PrologExample |
Rosen: 1.1 - 1.5 |

5-6 |
Boolean
Algebra
- NP-Complete Theory and Reductions, Satisfiability, 3SAT
and 2SAT, operators, completeness, normal forms, identities. Karnaugh maps, applications to circuits. |
Rosen: 12.1 - 12.4 |

7 |
Linear Algebra -
Introduction. Matrices, addition, multiplication, and
motivation. Associative, distributive laws. |
Rosen:
2.6, Pettofrezzo: 1.1-1.4 |

8 |
LA - Theory of Solving Equations, Gaussian elimination, Diagonal and triangular matrices. | Petto: 2.5. |

9 |
LA - Inverses and Gauss/Jordan elimination, linear independence, bases. | Petto: 2.2, 2.4 |

10 |
LA -
Determinants for n
by n matrices,
properties of determinants and the relationship to
inverses. Transpose and theorems. |
Petto: 2.1 |

11 |
LA - Geometric interpretations, and linear transformations. Applications: Computer graphics. | Petto: 3.1-3.5 |

12 | LA - Eigenvalues
and Eigenvectors, Diagonalizing a Matrix, Similar Matrices.
The Hamilton-Caley Theorem and calculating powers of a matrix. |
Petto: 4.1-4.5 |

13 | LA - Applications - Linear Regression, Least Squares, Curve Fitting. Cryptography and Matrix Ciphers. | Class Notes |

14 | LA - Applications - Probablility and Markov Chains. | Class Notes |

15 | LA - More Applications if time allows - More Web Mining, Warps and Morphs and More Computer Graphics. | Class Notes |