Proof Workshop & Asymptotic Analysis

Proof workshop via Ed Discussion

Outline for reference.

Anatomy of a Proof

Put the implementation and proof of correctness for selection sort (recursive approach) in the right order.
- Solutions will be available on moodle after class.

In your groups:

Find the flaw in ChatGPT's argument that there is a flaw in the chat linked below...
Post your analysis to Ed Discussion before you look at my solutions below.

- The proof I gave it is from Proofs from THE BOOK: a book of mathematical proofs by Martin Aigner and Günter M. Ziegler. The book is dedicated to the mathematician Paul Erdős, who often referred to "The Book" in which God keeps the most elegant proof of each mathematical theorem.

In the response, there is an assignment of colors to vertices of a graph:
Now, let's say the proof assigns colors as follows:

It then goes on to say:

Triangle ABC ... only contains vertices of color 2 and color 3.

This is faulty logic, since Triangle ABC contains vertex A, which was assigned color 1.

If you have more time...

See if you can create a chat with ChatGPT that contains a response with faulty logic. Post the links (and analysis) to the Ed Discussion thread.
Compile a list of concerns around proofs and/or Discrete Math topics. Use Ed Discussion thread to post (you can do this anonymously if you prefer).
Check out this online book that might help with reasoning about proofs.
Work together to start the first few levels of The Incredible Proof Machine.

CS 312 Topic 2: Asymptotic analysis (big-O, big-theta, big-omega))

AsymptoticsWorksheet.pdf