Instruction for Discrete Structures (2IT50)

Instructor: Tom Verhoeff

Q1 2017-2018

A N N O U N C E M E N T S
Tue 29 Aug 2017	Instructor Verhoeff is not available on Fri 22 Sep. Please, attend an instruction of another group.
Tue 29 Aug 2017	To practice your problem solving skills for this course: Register on Brilliant.org. Solve problems for the topic Discrete Mathematics. See recommended subtopics below.

Useful Information

Course webpages
Material for Logic & Set Theory:
- "The collection of tables appearing at the end of the book [used for 2IT60 (Logic & Set Theory)], summarizing the most important definitions, axioms and rules, can be downloaded here."
- See under Additional Material for examples of a formal calculation, and proofs in natural language.

How to Contact Me

Send email to T.Verhoeff@tue.nl.
In Subject, include [2IT50].
Include your id.nr. and name in your signature.
Clearly indicate what assignment or topic it concerns.

How to Submit Solutions for Homework

Email them to me (see above).
Deadline: Wed at 23:59 before instruction
Format: PDF (generated from LaTeX, Word, ...), or picture of handwritten solution
For capturing handwritten solutions, consider using Microsoft's Office Lense App
Clearly include the number of the exercise.

Instruction 1 (Fri 08 Sep 2017)

To prepare:

1.4 (pp.24-29): 1-3,
4, 5,6-7, 10, 12, 14, 16, 18, optionally 13

Why study relations?

Relations can help in specifying software.
Example (Java):
```
    /** Finds a location of the minimum in given array. */
    public static int locateMin(int[] a)
```
The input/output relation is captured by
```
  @post: {@code a.has(\result) && (a[\result] == (\min i; a.has(i); a[i]))}
```
This involves a relation from integer arrays to integer values. Note that a given array can relate to multiple correct results (viz. if the minimum occurs more than once). Therefore, a mathematical function is not appropriate as specification.
Relations can play a role in defining the semantics of programming languages: how initial and final state are related under statements (Hoare triples).
Relations can help in reasoning about software (on a level that abstracts from implementation details; see next week).
That is why it is important to understand properties of the various types of relations. For example, in Java, the method equals() (defined on the class Object, from which every other class inherits) must be implemented such that it yields an equivalence relation.
See: Java 8 API documentation for Object.equals(), which involves terminology such as equivalence relation, reflexive, symmetric, transitive.

Nontransitive dice

Warm-up problems on Brilliant.org:

Instruction 2 (Fri 15 Sep 2017)

To prepare:

1.4 (p.24-29): 25, 32, 40; 2.10 (pp.55-58): 2, 5, 6, 8
General Feedback
Video for Exercise 29

Is the geometric relation "lies-entirely-on-top-of" transitive? See Paradoxical Triangular Braid.

How can relations appear in (Java) programming?

As binary boolean operators:
```
  =   !=   <   <=   >   >=
```
Used as x R y.
As (static) boolean function with two parameters:
```
  public static boolean R(X x, Y y) . . .
```
Used as R(x, y).
As non-static boolean function with one parameter:
```
  class X {
      public boolean R(Y y) . . .
  }
```
Used as x.R(y)
Typical example: method Object.equals().
As 2-dimensional array:
```
  boolean[][] R;
```
Used as R[x][y].
As nested list of booleans:
```
  List<List<Boolean>> R;
```
Used as R.get(x).get(y)
Mixtures of the above.

Note that the syntax differs considerably, but the reasoning is all similar.

Instruction 3 (Fri 22 Sep 2017)

Absent

Instruction 4 (Fri 29 Sep 2017)

To prepare:

2.10 (page 55-58): 26; 3.9 (page 72-73): 1,2,3,4,8,9,11,12,13
Concerning Exercise 26 of 2.10, see Ramsey's Number R(4, 4)
Email me your solution for Exercise 9 of 3.9. Work this out as if it were an exam. Deadline: Fri 30 Sep 2016, 08:30.

Function notation is a bit "broken":

f : A → B (here, A is written on the left)
for a ∈ A, we have f(a) ∈ B (here a is written on the right of f)
If f : A → B and g : B → C, then g o f : A → C (note the awkward order)
For a ∈ A, we have (g o f)(a) = g(f(a)) ∈ C
One way to "fix" this, would be to write f : B ← A
If g : C ← B and f : B ← A, then g o f : C ← A
A better way to "fix" this, would be to write a.f for f(a)
For a ∈ A, we then have a.(g o f) = (a.g).f

Alternative characterizations of injective and surjective functions:

Function f : A → B is injective if and only if
(∀ C, g, h : C → A : f o g = f o h ⇒ g = h)
This is a left cancelation law for composition with an injective function.
Function f : A → B is surjective if and only if
(∀ C, g, h : B → C : g o f = h o f ⇒ g = h)
This is a right cancelation law for composition with a surjective function.

You can (more) easily prove Lemma 3.13 using these characterizations. Similarly for exercise 3.9.9.

Euler cycles and Hamilton cycles appear in the mathematical sculptures by Koos Verhoeff.

Theorem on parity of number of nodes with odd degree.

Warm-up problems on Brilliant.org:

Instruction 5 (Fri 06 Oct 2017)

To prepare:

4.5 (page 90-92): 7, 8, 9, 11, 12, 13

You can mail me your solutions (worked out as if it was an exam) for exercises 7 and 13.

Video for Exercise 7 of 4.5 (with captions)
Video for Exercise 13 of 4.5

In these videos, I have introduced the (convenient) notation X ⊑ y ("y is an upper bound of X") as abbreviation for

(∀ x : x ∈ X : x ⊑ y)

where X ⊆ U and y ∈ U .

This makes it possible to characterize sup(X) by (cf. Lemma 4.22):

(∀ y : y ∈ U : X ⊑ y ⇔ sup(X) ⊑ y)

Instruction 6 (Fri 13 Oct 2017)

To prepare:

5.7 (page 111-113): 7, 8, 9, 13, 14, 16, 18, 20, 21, 22
Some information about multiplicative groups modulo a prime p
During the instruction, we investigated Z₁₁^*.
During the lecture the following was mentioned (and this may be used during tests and exams):
- Every finite permutation can written as a composition of disjoint cycles.
- These cycles commute; that is, the order of their composition is irrelevant.
- The order of a one-cycle permutation equals the cycle's length.
- Consequently, the order of a finite permutation equals the least common multiple of the lengths of all its disjoint cycles.

Warm-up problems on Brilliant.org about Group Theory (Ch.5):

Abstract Algebra, covering Group Theory (no quizzes yet; but the Brilliant wiki might be useful)

Instruction 7 on Fri 20 Oct 2017

Warm-up problems on Brilliant.org about Combinatorics (Ch.6):

The Twelvefold Way (Wikipedia): a systematic classification of 12 related enumerative problems concerning two finite sets.

A very nice (inexpensive and short) booklet on Combinatorics (including Graphs):

Robin Wilson.
Combinatorics: A Very Short Introduction.
Oxford University Press, 2016.
(Also available as ebook.)

For the course Discrete Structures, especially Chapters 1, 2, 3, 4, and 6 are relevant.

Instruction 8 (Fri 27 Oct 2016)

I am possibly absent!

To prepare:

7.9 (page 159-161): 1, 2, 3, 4, 5, 7, 8, 9

Warm-up problems on Brilliant.org about Number Theory (Ch.7):

Divisibility
Prime Numbers
Greatest Common Divisor / Lowest Common Multiple
Modular Arithmetic Operations
Basic Applications of Modular Arithmetic
Eulers's Theorem, covering, in particular, Fermat's Little Theorem and RSA