This is my project for CS 131. I worked on the Pigeonhole Principle.
In the documentation file I included a link to my notes/script that I used. Any work information I found in the textbook I wrote here and in the presentation for my work. I linked my google doc file below which has formatting for a better reading experience.
While it may seem like a pretty simple concept at first glance the pigeonhole principle has some very important and relevant applications in the real world. The pigeonhole principle has limited applications in writing code from what I have found, but it excels at helping us understand and plan for programming situations. It allows us to predict outcomes and better adapt our programs to account for said outcomes. An example is the lossless data compression, we are able to use the pigeonhole principle to predict what file size we may end up with depending on the files inputted. It is difficult to adapt this into code or pseudocode as it is less of a programming principle, and more of a mathematical principle to help us understand our programs, so I provided a real world example instead of a coded project. I will provide a short pseudocode program to show how the pigeonhole principle works but not necessarily how it would be implemented in a real world scenario as it seems less of something you would program in and more of an analytical tool. The pseudocode provides a loop that demonstrates how the pigeonhole principle works in the case that we apply a new object to a low-value box each time. This means that the post of the algorithm will have a nested array that fills each of the first nests boxes with values in the second nest. There will be at a minimum one box containing the value ⌈N objects / k boxes⌉. In conclusion, I was pleasantly surprised when doing this topic. I found it to be very interesting and despite it seeming simple, and it had a lot of valuable information. I expected it to be difficult to find resources regarding the topic but due to its important nature, it was not hard to learn about.
Here I linked the video presentation and a link to my slides file. I originally only linked my video but updated it to have the slides so you can view that better today. (12/4)
This is where I describe my findings in a lesson format. The video contains information about the principle definitions, proofs, and applications.
As I explained in my conclusion, this principle does not have many direct coding applications, rather it is best for analyzing code and predicting output mathematically. In the src file I included some basic pseudocode that outlines how the pigeonhole principle applies to rudimentary programming subjects. In a more advanced setting, the principle can be used to analyze more complex things like lossless compression algorithms as I explain in my presentation and notes.
Video: https://youtu.be/eLQ4UCR6HrI
Presentation: https://docs.google.com/presentation/d/1S_P8TjSuAFU2WAfEcmmJSj3E2YJZVt8uKauJlq-FcBs/edit?usp=sharing
Notes/Script & Conclusion: https://docs.google.com/document/d/12AkWFNiVt4BIH400lzSQZ9qepv_GLOPzJzEUACkFBXk/edit?usp=sharing