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