Lectures: TR 8:30 - 9:45, 217 College Center
Office Hours: TR 11:00 - 12:30, or by appointment
Texts: Discrete Mathematics and its Applications, Rosen, McGraw Hill, 8th edition.
Pettofrezzo, Anthony J. Matrices and Transformations. New York: Dover, 1978.
Exams: There will be 6 quizzes (25%), the lowest grade will be dropped, and one final examination (35%). The final examination will be in our classroom on Tuesday, May 6, 9 AM. Here is a quizlet from TA Tiziana Hernandez, (now in a PhD program at RPI), for final practice.
Teaching Assistant: Rory Paul. There will be help regularly scheduled help sessions every other Monday 5-7 - look for his emails.
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.
Description: The two-semester discrete math sequence covers the mathematical topics most directly related to computer science. Topics include: logic, relations, functions, basic set theory, countability and counting arguments, proof techniques, mathematical induction, graph theory, combinatorics, discrete probability, recursion, recurrence relations, linear algebra, and number theory. Emphasis will be placed on providing a context for the application of the mathematics within computer science. The analysis of algorithms requires the ability to count the number of operations in an algorithm. Recursive algorithms in particular depend on the solution to a recurrence equation, and a proof of correctness by mathematical induction. The design of a digital circuit requires the knowledge of Boolean algebra. Software engineering uses sets, graphs, trees and other data structures. Number theory is at the heart of secure messaging systems and cryptography. Logic is used in AI research in theorem proving and in database query systems. Proofs by induction and the more general notions of mathematical proof are ubiquitous in theory of computation, compiler design and formal grammars. Probabilistic notions crop up in architectural trade-offs in hardware design. Linear algebra has a vast variety of applications including: Markov chains, cryptography, computer graphics, curve fitting, electrical circuits, and data mining. The first semester concentrates on induction, proofs, combinatorics, recurrence relations, computational complexity, Big-O, and number theory. The second semester concentrates on logic, sets, set algebra, countability, functions, Boolean algebra, linear algebra and applications.
Web Mining:
Web Mining Using Eigenvalues The Paper Math at Google How Google Finds Your Needle in the Web's Haystack
Fun Links: Halting Problem Video Monopoly Markov Chain Wolfram Alpha My Video Lectures
Calculators: Matrix Calculator I Matrix Visualizer Matrix Calculator II Desmos Graphing Calculator Modular Matrix Calculator
Readings:
Week 0: If you haven't done it yet, then read How to Read Mathematics.
Week 1-2: Read this handout: Low level bit hacks you absolutely must know: by Peteris Krumins, also published on page 32 of Hacker Monthly.
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.
My Class Notes for matrix algebra will help you if you miss any classes.
(Due Tuesday, Feb. 11)
(Due Thursday, March 6, before Spring break)
(Due Tuesday, April 1)
(Due Tuesday, April 15)
(Due Last Day of Class)
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.
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 - Web Searching, 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