(183) Mathematical Thinking in Computer Science | Discrete Mathematics for Computer Science

Introduction to Discrete Mathematics

  • Discrete mathematics is essential for various computer science fields, such as data science, machine learning, and software engineering.

  • The teaching method includes engaging interactive puzzles to help students understand and discover important ideas in discrete mathematics.

Importance of Proofs

  • Contrary to popular belief, proofs are significant for both mathematicians and programmers, especially in complicated systems like operating systems and cryptographic protocols.

  • Understanding proofs enables students to appreciate arguments and convince others about the validity of their claims.

  • Course objectives include understanding, inventing, explaining proofs, and enjoying the learning process.

The Story of Paul Erdős

  • Hungarian mathematician Paul Erdős believed in a divine book containing perfect proofs for every statement.

  • Some researchers have attempted to collect proofs in a book, and some are more challenging than those presented in the course.

Puzzles to Solve

  • The course begins with simple puzzles, including whether an 8x8 chessboard can be tiled with domino pieces (1x2 rectangles) without overlaps.

  • The solution confirms that it can be done in multiple ways.

  • However, if a square is removed from the chessboard, tiling it becomes impossible due to an odd number of remaining cells.

Impossibility Proofs

  • When trying to prepare a tiled board with a square missing, students explore the impossibility through numerical reasoning.

  • A similar problem with two opposite corners missing on a chessboard demonstrates that the configuration is not tileable due to parity (even-odd counting).

The Challenge of Tiling

  • The puzzles evolve to include cutting shapes into congruent pieces or transitioning from simple shapes to geometrically complex problems.

  • Working through geometric puzzles like cutting an octagon into pieces illustrates the principles of symmetry and congruence.

Tensegrity Concept

  • The course introduces tensegrity structures, which appear impossible to construct until demonstrated through engaging examples, like using drinking straws and strings.

  • Students will attempt constructing tensegrity structures as a fun, hands-on learning method.

Recursion and Mathematical Induction

  • Recursion is essential in problems like counting the number of people in a line, exemplifying how recursive definitions work in a concrete scenario.

  • The course also discusses mathematical induction and proofs by contradiction through real-world problems, demonstrating their relevance to the broader computational theory.

Reductio ad Absurdum Proof Technique

  • A proof by contradiction (reductio ad absurdum) shows the importance of assumptions and draws conclusions based on them.

  • The proof requires revealing contradictions within logical assumptions guiding towards truth through numerical reasoning.

Pigeonhole Principle

  • The pigeonhole principle proves that if items exceed the available categories, at least one category must contain multiple items.

  • Applying this principle in real scenarios shows how logical deduction often unveils simple truths within complex situations.

Double Counting and Invariants

  • Invariants are unchanging properties used to analyze systems, allowing conclusions about potential outcomes based on fixed attributes within processes.

  • Both double counting and invariants help solve mathematical problems by providing distinct perspectives on system states and properties.

Conclusion

  • The course promotes a fun, engaging approach to discrete mathematics that emphasizes understanding through puzzles, promoting critical thinking and enjoyment in the learning process.

  • Students are prepared to tackle mathematical proofs, explore algorithmic reasoning, and apply logical principles in varied computational contexts.