Teaching Discrete Mathematics

Teaching Discrete Mathematics

• Teaching Discrete Mathematics

• Active Learning in Discrete Mathematics

• Educational Technology Research at UW

• Big Ideas: Complexity Theory

http://cs.washington.edu/homes/anderson

• http://cs.washington.edu/homes/anderson

• Home page

• http://cs.washington.edu/homes/anderson/iucee

• Workshop websites
• Updates might be slow (through July 20)

• Google groups

• IUCEE Workshop on Teaching Algorithms

Monday, June 30, Active learning and instructional goals

• Monday, June 30, Active learning and instructional goals

• Morning
• Welcome and Overview (1 hr)
• Introductory Activity (1 hr). Determine background of participants
• Active learning and instructional goals (1hr) in Discrete Math, Data Structures, Algorithms.
• Afternoon
• Group Work (1.5 hrs). Development of activities/goals from participant's classes.
• Content lectures (Great Ideas in Computing): (1.5 hr) Problem mapping

• Tuesday, July 1, Discrete Mathematics

• Morning
• Discrete Mathematics Teaching (2 hrs)
• Activities in Discrete Mathematics (1 hr)
• Afternoon
• Educational Technology Lecture (1.5 hrs)
• Content Lecture: (1.5 hrs) Complexity Theory

Each group:

• Each group:

• Design two classroom activities for your classes. Identify the pedagogical goals of the activity.

• Five of the groups will give progress report to the class

• Overnight each group should prepare ppt slides

• Thursday there will be a feedback/critique session

Each group will develop a presentation on how they are going to apply ideas from this workshop.

• Each group will develop a presentation on how they are going to apply ideas from this workshop.

• Thursday

• Two hours work time

• Friday

• Three hours presentation time
• 15 minutes per group with PPT slides

Discrete Mathematics and Its Applications, Rosen, 6-th Edition

• Discrete Mathematics and Its Applications, Rosen, 6-th Edition

• Ten week term

• 3 lectures per week (50 minutes)
• 1 quiz section
• Midterm, Final

Logic (4)

• Logic (4)

• Reasoning (2)

• Set Theory (1)

• Number Theory (4)

• Counting (3)

• Probability (3)

• Relations (3)

• Graph Theory (2)

What is the purpose of each unit?

• What is the purpose of each unit?

• Long term impact on students

• What are the learning goals of each unit?

• How are they evaluated

• What strategies can be used to make material relevant and interesting?

• How does the context impact the content

Analysis of course content

• Analysis of course content

• How does this apply to the courses that you teach?

• Reflect on challenges of your courses

First course in CSE Major

• First course in CSE Major

• Students will have taken CS1, CS2
• Various mathematics and physics classes

• Broad range of mathematical background of entering students

• Goals of the course

• Formalism for later study
• Learn how to do a mathematical argument

• Many students are not interested in this course

Begin by motivating the entire course

• Begin by motivating the entire course

• “Why this stuff is important”

• Formal systems used throughout computing

• Propositional logic and predicate calculus

• Boolean logic covered multiple time in curriculum

• Relationship between logic and English is hard for the students

• implication and quantification

Understanding boolean algebra

• Understanding boolean algebra

• Connection with language

• Represent statements with logic

• Predicates

• Meaning of quantifiers
• Nested quantification

Language and formalism for expressing ideas in computing

• Language and formalism for expressing ideas in computing

• Fundamental tasks in computing

• Translating imprecise specification into a working system
• Getting the details right

A statement that has a truth value

• A statement that has a truth value

• Which of the following are propositions?

• The Washington State flag is red
• It snowed in Whistler, BC on January 4, 2008.
• Hillary Clinton won the democratic caucus in Iowa
• Space aliens landed in Roswell, New Mexico
• Ron Paul would be a great president
• Turn your homework in on Wednesday
• Why are we taking this class?
• If n is an integer greater than two, then the equation an + bn = cn has no solutions in non-zero integers a, b, and c.
• Every even integer greater than two can be written as the sum of two primes
• This statement is false

• Propositional variables: p, q, r, s, . . .

• Truth values: T for true, F for false

Negation (not)  p

• Negation (not)  p

• Conjunction (and) p  q

• Disjunction (or) p  q

• Exclusive or p  q

• Implication p  q

• Biconditional p  q

Implication

• Implication

• p implies q
• whenever p is true q must be true
• if p then q
• q if p
• p is sufficient for q
• p only if q

You cannot ride the roller coaster if you are under 4 feet tall unless you are older than 16 years old

• You cannot ride the roller coaster if you are under 4 feet tall unless you are older than 16 years old

• q: you can ride the roller coaster
• r: you are under 4 feet tall
• s: you are older than 16

Terminology: A compound proposition is a

• Terminology: A compound proposition is a

• Tautology if it is always true
• Contradiction if it is always false
• Contingency if it can be either true or false

To show P is equivalent to Q

• To show P is equivalent to Q

• Apply a series of logical equivalences to subexpressions to convert P to Q

• To show P is a tautology

• Apply a series of logical equivalences to subexpressions to convert P to T

 x Even(x)

•  x Even(x)

•  x Odd(x)

•  x (Even(x)  Odd(x))

•  x (Even(x)  Odd(x))

•  x Greater(x+1, x)

•  x (Even(x)  Prime(x))

 x  y Greater (y, x)

•  x  y Greater (y, x)

•  y  x Greater (y, x)

•  x  y (Greater(y, x)  Prime(y))

•  x (Prime(x)  (Equal(x, 2)  Odd(x))

•  x  y(Equal(x, y + 2)  Prime(x)  Prime(y))

Logic programming language

• Logic programming language

• Facts and Rules

Iteration over multiple variables

• Iteration over multiple variables

• Nested loops

• Details

• Use distinct variables
•  x( y(P(x,y)   x Q(y, x)))
• Variable name doesn’t matter
•  x  y P(x, y)   a  b P(a, b)
• Positions of quantifiers can change (but order is important)
•  x (Q(x)   y P(x, y))   x  y (Q(x)  P(x, y))

Students have difficulty with mathematical proofs

• Students have difficulty with mathematical proofs

• Attempt made to introduce proofs

• Describe proofs by technique

• Some students have difficulty appreciating a direct proof

• Proof by contradiction leads to confusion

Understand the basic notion of a proof in a formal system

• Understand the basic notion of a proof in a formal system

• Derive and recognize mathematically valid proofs

• Understand basic proof techniques

“If Seattle won last Saturday they would be in the playoffs”

• “If Seattle won last Saturday they would be in the playoffs”

• “Seattle is not in the playoffs”

• Therefore . . .

Start with hypotheses and facts

• Start with hypotheses and facts

• Use rules of inference to extend set of facts

• Result is proved when it is included in the set

Proof methods

• Proof methods

• Direct proof
• Contrapositive proof
• Proof by contradiction
• Proof by equivalence

If n is odd, then n2 is odd

• If n is odd, then n2 is odd

Show that at least four of any 22 days must fall on the same day of the week

• Show that at least four of any 22 days must fall on the same day of the week

Can an n  n checkerboard be tiled with 2  1 tiles?

• Can an n  n checkerboard be tiled with 2  1 tiles?

Can an 8  8 checkerboard with upper left and lower right corners removed be tiled with 2  1 tiles?

• Can an 8  8 checkerboard with upper left and lower right corners removed be tiled with 2  1 tiles?

Students have seen this many times already

• Students have seen this many times already

• Still important for students to see the definitions / terminology

• Russell’s Paradox discussed

Important for a small number of computing applications

• Important for a small number of computing applications

• Students should know a little number theory to appreciate aspects of security

• Students who will go on to graduate school should know this stuff

• Concepts such as modular arithmetic important for algorithmic thinking

• Mixed background of students coming in

• Top students understand this from their math classes
• Other students unable to transfer knowledge from other disciplines

Understand modular arithmetic

• Understand modular arithmetic

• Provide motivating example

• RSA encryption
• Students should understand what public key cryptography is, but the details do not need to be retained
• Something of interest for most advanced students

• Introduce algorithmic and computational topics

• Fast exponentiation

a +7 b = (a + b) mod 7

• a +7 b = (a + b) mod 7

• a  b = (a  b) mod 7

Euclid’s theorem: if x and y are relatively prime, then there exists integers s, t, such that:

• Euclid’s theorem: if x and y are relatively prime, then there exists integers s, t, such that:

• Prove a  {1, 2, 3, 4, 5, 6} has a multiplicative inverse under 

Map values from a large domain, 0…M-1 in a much smaller domain, 0…n-1

• Map values from a large domain, 0…M-1 in a much smaller domain, 0…n-1

• Index lookup

• Test for equality

• Hash(x) = x mod p

• Often want the hash function to depend on all of the bits of the data

• Collision management

Linear Congruential method

• Linear Congruential method

Compute 7836581453

• Compute 7836581453

• Compute 7836581453 mod 104729

An integer p is prime if its only divisors are 1 and p

• An integer p is prime if its only divisors are 1 and p

• An integer that is greater than 1, and not prime is called composite

• Fundamental theorem of arithmetic:

• Every positive integer greater than one has a unique prime factorization

If you pick a random number n in the range [x, 2x], what is the chance that n is prime?

• If you pick a random number n in the range [x, 2x], what is the chance that n is prime?

Primality Testing:

• Primality Testing:

• Given an integer n, determine if n is prime

• Factoring

• Given an integer n, determine the prime factorization of n

Is the following 200 digit number prime:

• Is the following 200 digit number prime:

How can Alice send a secret message to Bob if Bob cannot send a secret key to Alice?

• How can Alice send a secret message to Bob if Bob cannot send a secret key to Alice?

Rivest – Shamir – Adelman

• Rivest – Shamir – Adelman

• n = pq. p, q are large primes

• Choose e relatively prime to (p-1)(q-1)

• Find d, k such that de + k(p-1)(q-1) = 1 by Euclid’s Algorithm

• Publish e as the encryption key, d is kept private as the decryption key

Bob

• Bob

• Precompute p, q, n, e, d
• Publish e, n

• Alice

• Read e, n from Bob’s public site
• To send message M, compute C = Me mod n
• Send C to Bob

• Bob

• Compute Cd to decode message M

de = 1 + k(p-1)(q-1)

• de = 1 + k(p-1)(q-1)

• Cd  (Me)d= Mde = M1 + k(p-1)(q-1) (mod n)

• Cd M (Mp-1)k(q-1)  M (mod p)

• Cd M (Mq-1)k(p-1)  M (mod q)

• Hence Cd  M (mod pq)

Considered to be most important part of the course

• Considered to be most important part of the course

• Students will have seen basic induction

• but more sophisticated uses are new
• “Strong induction”
• link it with formal proof
• recursion is new to most students

• Matter of discussion how formal to make the coverage

Be able to use induction in mathematical arguments

• Be able to use induction in mathematical arguments

• understand how to use induction hypothesis

• Give recursive definitions of sets, strings, and trees

• Be able to use structural induction to establish properties of recursively defined objects

• Appreciate that there is a formal structure underneath computational objects

Prove 3 | 22n -1 for n  0

• Prove 3 | 22n -1 for n  0

F(0) = 0; F(n + 1) = F(n) + 1;

• F(0) = 0; F(n + 1) = F(n) + 1;

• F(0) = 1; F(n + 1) = 2  F(n);

• F(0) = 1; F(n + 1) = 2F(n)

Recursive definition

• Recursive definition

• Basis step: 0  S
• Recursive step: if x  S, then x + 2  S
• Exclusion rule: Every element in S follows from basis steps and a finite number of recursive steps

The set * of strings over the alphabet  is defined

• The set * of strings over the alphabet  is defined

• Basis:   * ( is the empty string)
• Recursive: if w  *, x  , then wx  *

L1

• L1

•   L1
• w  L1 then awb  L1

• L2

•   L2
• w  L2 then aw  L2
• w  L2 then wb  L2

A single vertex r is a tree with root r.

• A single vertex r is a tree with root r.

• Let t1, t2, …, tn be trees with roots r1, r2, …, rn respectively, and let r be a vertex. A new tree with root r is formed by adding edges from r to r1,…, rn.

(, T1, T2), tree with left subtree T1 and right subtree T2

• (, T1, T2), tree with left subtree T1 and right subtree T2

•  is the empty tree

• Extended Binary Trees (EBT)

•   EBT
• if T1, T2  EBT, then (, T1, T2)  EBT

• Full Binary Trees (FBT)

•   FBT
• if T1, T2  FBT, then (, T1, T2)  FBT

N(T) - number of vertices of T

• N(T) - number of vertices of T

• N() = 0; N() = 1

• N(, T1, T2) = 1 + N(T1) + N(T2)

• Ht(T) – height of T

• Ht() = 0; Ht() = 1

• Ht(, T1, T2) = 1 + max(Ht(T1), Ht(T2))

Show P holds for all basis elements of S.

• Show P holds for all basis elements of S.

• Show that P holds for elements used to construct a new element of S, then P holds for the new elements.

If T is a binary tree, then N(T)  2Ht(T) - 1

• If T is a binary tree, then N(T)  2Ht(T) - 1

Convey general rules of counting

• Convey general rules of counting

• Material has been seen in math classes – but the connection to Computing is important

• Don’t want to spend too much time on this because it is specialized and won’t be retained

• Combinatorial proofs can be very clever (but its not clear what students get out of them)

• Some of this material has little general application

• Easy topic to for creating homework and exam questions

Convey general rules of counting

• Convey general rules of counting

• Cartesian product is important

• Link material they have seen in math classes to computing

• Strengthen algorithmic skills by solving counting problems

• Decomposition
• Mapping

Cartesian product

• Cartesian product

• |A1  A2  …  An| = |A1||A2||An|

• Subsets of a set S

• |P(S)|= 2|S|

• Strings of length n over 

• |n| = ||n

How many binary strings of length 9 start with 00 or end with 11

• How many binary strings of length 9 start with 00 or end with 11

A class has of 40 students has 20 CS majors, 15 Math majors. 5 of these students are dual majors. How many students in the class are neither math, nor CS majors?

• A class has of 40 students has 20 CS majors, 15 Math majors. 5 of these students are dual majors. How many students in the class are neither math, nor CS majors?

How many ways are there of selecting 1st, 2nd, and 3rd place from a group of 10 sprinters?

• How many ways are there of selecting 1st, 2nd, and 3rd place from a group of 10 sprinters?

• How many ways are there of selecting the top three finishers from a group of 10 sprinters?

How many paths are there of length n+m-2 from the upper left corner to the lower right corner of an n  m grid?

• How many paths are there of length n+m-2 from the upper left corner to the lower right corner of an n  m grid?

How many different ways are there of selecting 5 letters from {A, B, C} with repetition

• How many different ways are there of selecting 5 letters from {A, B, C} with repetition

Viewed as a very important topic for some subareas of Computer Science

• Viewed as a very important topic for some subareas of Computer Science

• Students required to take a statistics course
• Some faculty want to add Probability for Computer Scientists

• Students will have seen the topics many times previously

• Discrete probability is a direct application of counting

• Advanced topics included (Bayes’ theorem)

Provide a domain for practicing counting techniques

• Provide a domain for practicing counting techniques

• Remind students of a few probability concepts

• Sample space, event, distribution, independence, conditional probability, random variable, expectation

• Introduce an advanced topic to see what is to come in other classes

• Understand applications of linearity of expectation

Experiment: Procedure that yields an outcome

• Experiment: Procedure that yields an outcome

• Sample space: Set of all possible outcomes

• Event: subset of the sample space

Set S

• Set S

• Probability distribution p : S  [0,1]

• For s  S, 0  p(s)  1
• sS p(s) = 1

• Event E, E S

• p(E) = sEp(s)

Some of this material is highly relevant

• Some of this material is highly relevant

• Relational database theory
• Difficult to cover the material in any depth

• Large number of definitions

• Easy to generate homework and exam questions on definitions
• Definitions without applications unsatisfying

Convey basic concepts of relations

• Convey basic concepts of relations

• Sets of pairs
• Relational operations as set operations

• Understand composition of relations

• Connect with real world applications

End of term material – limited chance for homework

• End of term material – limited chance for homework

• Cannot ask deep questions on the exam

• Graph theory is split across three classes

• Algorithmic material is covered in other classes

Understand the basic concept of a graph and associated terminology

• Understand the basic concept of a graph and associated terminology

• Model real world with graphs

• Real world to formalism

• Elementary mathematical reasoning about graphs

Graph formalism

• Graph formalism

• G = (V, E)
• Vertices
• Edges

• Directed Graph

• Edges ordered pairs

• Undirected Graph

• Edges sets of size two

Web Graph

• Web Graph

• Hyperlinks and pages

• Social Networks

• Community Graph
• Linked In, Face Book
• Transactions
• Ebay
• Authorship
• Erdos Number

Determine the value of a page based on link analysis

• Determine the value of a page based on link analysis

• Model of randomly traversing a graph

• Weighting factors on nodes
• Damping (random transitions)

Find a graph with degree sequence

• Find a graph with degree sequence

• 3, 3, 2, 1, 1

• Find a graph with degree sequence

• 3, 3, 3, 3, 3

Let A be the Adjacency Matrix. What is A2?

• Let A be the Adjacency Matrix. What is A2?