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
Mining Using Eigenvalues
|Math at Google||Math in CS||Halting
|Monopoly Markov Chain||Matrix Calculator||Wolfram Alpha||My
(Due Tuesday, Feb. 14)
(Due Friday after Spring Break)
(Due before Easter Break)
(Due a week before Last Day of Class)
(Due before Final)
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|
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.
|Rosen: 1.1 - 1.5|
- NP-Complete Theory and Reductions, Satisfiability, 3SAT
and 2SAT, operators, completeness, normal forms, identities.
Karnaugh maps, applications to circuits.
|Rosen: 12.1 - 12.4|
||Linear Algebra -
Introduction. Matrices, addition, multiplication, and
Associative, distributive laws.
||LA - Theory of Solving Equations, Gaussian elimination, Diagonal and triangular matrices.||Petto: 2.5.|
||LA - Inverses and Gauss/Jordan elimination, linear independence, bases.||Petto: 2.2, 2.4|
Determinants for n
by n matrices,
properties of determinants and the relationship to
Transpose and theorems.
||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.
|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|