CS 202 - Discrete Mathematics for Computer Scientists II

Shai Simonson    306 Stanger    (508) 565-1008

Email:  shai@stonehill.edu

Homepage: http://www.stonehill.edu/compsci/shai.htm


Lectures:  MW 1:00 - 2:15,  001 Stanger

Texts: Discrete Mathematics and its Applications, Rosen, McGraw Hill.

Pettofrezzo, Anthony J. Matrices and Transformations. New York: Dover, 1978.
Exams:  There will be one midterm (25%) and one final examination (35%).

Teaching Assistant:  TBA

Assignments:  Homeworks will be worth 40% of your grade.   You may do these with a partner, and one grade will be given to both people in the group.

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: Class on Monday April 21 is cancelled due to Passover.

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, functions, comutational complexity, and number theory.  The second semester concentrates on logic, sets, countability, Boolean algebra, linear algebra and applications.

 

Useful Links

Mathworld Cut-the-Knot Google's Ranking Method History of Set Theory
Math Review - Matrix Algebra
 Matrix Calculator Math in CS Linear Algebra Refs
Web Mining Using Eigenvalues - Blurb
The Paper


Assignments

If you haven't done it yet, then read How to Read Mathematics
Read Google's Ranking Method to learn why computer scientists need to know about all this linear algebra.
 
Assignment 1  (Due-Monday February 11)
 Assignment 2 Assignment 3 Assignment 4 

 
 

Brief Syllabus

Week Topics Reading
1 Set Theory - Inclusion/Exclusion Theorem, Associative, Distributive, and De Morgan's Laws.
Functions, 1-1 correspondence, and Countability -  Diagonalization.  Applications to Computability and Undecidability. 		Rosen:  1.6 - 1.8, 6.5,
pages 233 - 236.
2 Propositional and First Order Logic -  Predicates, Quantifiers. 
Applications to automatic theorem proving,  and Resolution.
 Rosen:  1.1 - 1.5
3 Boolean Algebra - Operators, completeness, normal forms, identities.
Applications of Boolean Algebra to circuits, logic, databases, PROLOG. 		 Rosen:  10.1 - 10.4
4 Linear Algebra - Introduction.  Matrices, addition, multiplication, and motivation. 
Associative, distributive laws.		 Rosen:  2.7, 
Pettofrezzo: 1.1-1.4 
5 LA - Theory of Solving Equations, Gaussian elimination, Diagonal and triangular matrices. Petto: 2.5.
6 LA - Inverses and Gauss/Jordan elimination, linear independence, bases. Petto:  2.2, 2.4
7 LA - Determinants for nxn matrices, properties of determinants and the relationship to inverses. 
Transpose and theorems.		 Petto:  2.1
8 LA - Geometric interpretations, and linear transformations. Petto:  3.1-3.5
9 Midterm Examination: Wednesday, March 19.
10 LA - Eigenvalues and Eigenvectors, Diagonalizing a Matrix, Similar Matrices. Petto:  4.1-4.2
11 LA -  Applications:  The Hamilton-Caley Theorem and calculating powers of a matrix. 
Least Squares, Curve Fitting. 		 Petto: 4.3-4.5
12 LA - Applications - Probablility and Markov Chains. Class Notes
13 LA - Applications - Computer Graphics. Class Notes
14 LA - Applications -  Cryptography and Matrix Ciphers. Class Notes
15 LA - More Applications if time allows - Data Mining, Warps and Morphs. Class Notes