Pigeonhole principle and algorithm

In fifth slide of Quiz 1(Intro to Computation ,under computer science algorithm course and Algorithm section ) there is a concept of Pigeonhole principle used to find minimum number of comparison required to sort four elemnt list. how pigeonhle principle is applied here and from where that 22=42^2=4 possible outcomes came?Can anyone explain that?

#Combinatorics

Note by Ankit Mahlawat
3 years ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list
  • bulleted
  • list

1. numbered
2. list
  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai−1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 ∑i=13 \sum_{i=1}^3
\sin \theta sin⁡θ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

So, suppose you have been given four (assume them to be distinct, for convenience) numbers and you want to sort them. In the interest of saving time and creating faster algorithms, one might wonder what is the minimum number of comparisons that an algorithm needs to make so that it can correctly sort the numbers.

  1. The numbers in the input could have come in 24 different orders, but there is only one correct order for the output.
  2. For each of the 24 inputs above, the algorithm needs different strategies to switch the elements, so that it can sort them correctly.
  3. Now, let's ask, is it possible to have an algorithm that sorts any array of 4 elements with just two comparisons?
  4. With two comparisons, there are at most 4 possibilities. Why? Each of the comparisons are questions of the form "Is this number larger than that one?", and then each of them have two possible answers, "Yes" or "No". So there are 2×22 \times 2 possibilities
  5. Since the only source of information for the algorithm are the comparisons, there are only 4 possible "computational paths" or switching strategies the algorithm could possibly output.
  6. But clearly, 4 strategies are not enough to sort 4 numbers, since we decided that we require 24 different strategies.

Does this argument make sense to you now? I agree that this argument may not be familiar to one when they are taking their first introduction to algorithms, and hence, I'd encourage you to ask questions.

Agnishom Chattopadhyay - 3 years ago
×

Problem Loading...

Note Loading...

Set Loading...