DRAFT
February 22, 2000
IST 230
Language, Logic, and Discrete Mathematics
Text: Dymacek & Sharp, Introduction to Discrete Mathematics
WCB McGrawHill, 1998
(done by Lambert)
Lecture 
Topic(s) 
Sections 
Problem 
Notes 
1 
Numbers, set notation 
1 

Very Introductory 
2 
Concept of proof, simple logic 
2 

Very Introductory 
3 
Simple number theoretic proofs 
3 

Starts easy 
4 
Indirect proofs, prime numbers, simple algorithms 
4 

This does start out SLOW 
5 
Equivalence classes, integers mod n 
5 

Starts to get challenging 
6 
Rationals, Euclid’s algorithm, pigeonhole principle, floors, ceilings 
6 

Not clear we have to show a rational has a terminating or periodic representation 


7 

Define a 11 correspondence Skip the rest of the section. Skip section 8 
7 
Quantification statements and their negation 
9 

Skip Ramsey numbers! 
8,9 
Well ordering axiom, induction 
10,11 

In section 10, just give definition and explanation of woa 
10 
More on induction 
12 


11,12 
Functions and sequences, induction, recursion 
13 


13 
Deductive logic, conjunction, disjunction, DeMorgan’s laws 
14 


14 
Sets, subsets, set cross product, counting 
15 

Straight forward 
15 
Exam I 


Section up to 14 
16 
Permutations and combinations 
16 


17 
Binomial Theorem, skip binomial series 
17 

Plenty of slack in this section, give back the test 
18 
Set operations, Venn diagrams, counting 
18 




19 

Skip this section on generating functions 
19 
Simple probability 
20 


20 
Conditional probability, tree representation 
21 


21 
Probability, independent events 
22 


22 
Bayes’ Theorem 
23 


24 
Finite Probability Theory 
24 




2528 

Omit Statistics 
25 
01 matrices 
29 


26 
Elementary matrix /vector operations 
30 

2 dimensional 
27 
Unit, zero, identity, transform matrices 
31 


28 
Graphs, matrix representation 
34 


29,30 
Subgraphs, walks, spanning subgraphs, Hamiltonian paths 
35 

This is a lot for one class 
31 
Exam II 


Up to section 34 
32 
Serious matrix representations 
36 

Clear author expects students to be comfortable with matrix computations 


37,38 

Skip graph isomorphism, Eulerian graphs; author is now a mathematician 
33,34 
Tree, spanning subtrees, matrix tree theorem 
39 

Level of complexity has jumped 
35,36 
Digraphs, tournaments, networks 
40 

Take two classes 
37,38,39 



Need to prepare a week of lectures on grammars/regular expressions 
40,41,42 



Need to prepare a week of lectures on finite state machines 
43,44,45 



slack 