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?

This section may take 2 lectures

6

Set Operations

1.4

How do you construct error-correcting 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

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

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

Have students design the state machine

42.43,44,45

Slack

Can be used for Shannon’s Entropy or whatever else we decide