DRAFT

February 22, 2000

IST 230

Language, Logic, and Discrete Mathematics

Text: Dymacek & Sharp, Introduction to Discrete Mathematics

WCB McGraw-Hill, 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 1-1 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 25-28 Omit Statistics 25 0-1 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