DRAFT
February 22, 2000
IST 230
Language, Logic, and Discrete Mathematics
Text: Washburn, Marlowe, & Ryan, Discrete Mathematics
Addison Wesley Longman, 2000
(done by Lambert)
Lecture 
Topic(s) 
Sections 
Problem 
Notes 
1 
Pascal’s Triangle, simple recursion, binomial coefficients 
1.1 
How many paths in a full binary tree from the root to the terminal nodes? 

2,3 
Induction 
1.2 
What is the minimum number of steps to solve the Towers of Hanoi Problem? 
Section has summation sigmas. This may take some time 
4,5 
Sets, Subsets, Binary strings 
1.3 
How do you solve the knapsack problem? 
Talks about Gray codes. This section may take 2 lectures 
6 
Set Operations 
1.4 
How do you construct errorcorrecting codes? 
Talks about Hamming codes. Should be able to finish lecture 5 here if needed 
7 
Recursion 
1.5 
Just cover Fibonacci numbers and trees 

8,9 
Integers, primes, gcd, lcm, Euclidean Algorithm, unique factorization, Fermat Factorization 
2.1 
Do prime numbers have any real world applications? 
This could take some time. We skip section 2.2 
10,11 
Integers mod n, examples mod 2, mod 3, mod 4, 
2.3 
What is public key encryption? 
May have to take a full lecture on PKE. Decide whether to include or not 
12,12,5 
Functions and Relations, composition of functions, injective, surjective, bijective, equivalence relations 
3.1 
This might take 1.5 lectures 

12.5,13 
Counting, pigeonhole principle, permutations, combinations 
3.2 
This might take 1.5 lectures as well 

14,15 
Graphs, directed, complete, matrix representations, planar, Eulerian cycle, circuit, Hamiltonian circuit, TSP 
4.1, 4.2 
How can we represent networks? 
Give definitions, expect ability to recognize, but little on the proof side 
16 
Exam I 
Ch 1,2,3 

17,18 
Trees, spanning trees, Breadth first, depth first, traversals of binary trees 
4.3 
Opportunity to do some recursion 

19 
Proof techniques 
5.1 
How do you pose and solve problems? 
Explain the proofs that sqrt(2) is irrational but do not expect students to reconstruct 
20,21 
Logic, prepositional calculus 
5.2, 5.3 
How do you convince others that your solution is correct? 
5.2 should be quick 
22,23 
Boolean algebra and functions, disjunctive and conjunctive normal forms, Karnaugh maps 
6.1,6.2 
How can we simplify Boolean queries? 

24 
Predicate calculus 
6.3 
Explain the notation, don’t expect much more 

25,26,27 
Algorithms, Euclidean, Merge Sort, Quicksort, Binary Search 
8.1 
Do fast sorting and searching algorithms exist? 
Explain the algorithms, note recursion, do not expect much 
28,29,30 
Graph, Network Algorithms, spanning trees, Dijkstra’s, network flows 
8.2 
How do we find a critical path in a job process? 

31 
Exam II 
Up to an including what is appropriate in 8.2 

32,33 
Algorithm complexity 
8.3 
Can a problem actually be solved in a reasonable amount of computer time? 
Don’t go overboard! Talk about best, worst case, average case but do not expect much 
34,35 
Probability 
9.2 
Cover Network reliability, no need to do much with Central Limit Thm. 

36,37,38 
Language, grammars, regular expressions, 
10.1 
Are regular expressions used in the real world? 
Show examples 
39,40,41 
Finite state machines 
10.2 
How does a soda machine work? Or a traffic light? Or an elevator call system? 
Have students design the state machine 
42.43,44,45 
Slack 
Can be used for Shannon’s Entropy or whatever else we decide 