Discrete Structures Lecture 17 Segment

Problem instances, problems, and algorithms 0:00 Problem versus problem instance 5:27 Definition: algorithm.

An exhaustive proof is a special case of proof by cases.

Insertion sort algorithm 0:00 Insertion sort algorithm to sort a finite sequence 1:04 Sample trace of the insertion sort algorithm.

The change-making problem 0:00 Definition: Change-making problem and algorithm 1:20 Theorem 1: The algorithm is correct for ...

Bubble sort algorithm 0:00 Bubble sort algorithm to sort a finite sequence 4:42 Sample trace of the bubble sort algorithm.

Binary search algorithm 0:00 Binary search algorithm to solve the same problem as before but with a sorted sequence 5:37 ...

0:00 Definition of the "resolution" inference rule 1:43 CS applications of resolution 2:26 The disjunctive syllogism is a special case ...

Pseudocode 0:00 Definition: pseudocode 1:54 Example: linear-search algorithm to solve the problem of finding a target element ...

Basic terminology pertaining to proofs 00:19 Definition: proof & theorem 02:07 Definition: lemma 02:58 Definition: corollary 03:22 ...

Proof by cases: A template.

Proof technique: Vacuous proof Prove p → q by proving that p is always false.

Basic number theory terminology 00:50 definition: even integer 01:36 definition: odd integer 01:51 definition: perfect square 02:29 ...

Proof technique: Universal generalization 00:00 Definition: arbitrary element of the domain 01:13 Proof of theorem in previous ...

Proof technique: Trivial proof Prove p → q by proving that q is always true.

Proof by cases: An example.

Proof technique: Direct proof Prove p → q by proving that, assuming p is true, q must also be true.

Proof by cases: A variation based on the logical equivalence between (P_1 OR P_2 OR ... OR P_n) → Q and (P_1 → Q) AND ...

Proof by contraposition.

Why we need more proof techniques: a sample theorem for which previously discussed proof techniques are either not applicable ...