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

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

**Assignments:** Homeworks
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.

**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:** None

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 Tuesday, Feb. 14) |
Assignment_2 (Due Friday after Spring Break) |
Assignment
3(Due before Easter Break) |
Assignment
4(Due a week before Last Day of Class) |
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 |