2

I don't understand the logic behind the algorithm of counting all the 729 students in the auditorium. It seems to be working (though the result 637 is not exactly the same.). But I don't know how it works in all people standing up first, then when/who/how to sit down while counting?

Can anyone explain in more details? Thanks,

Improve this question
1
  • This happens in the first lecture of wk0.
    – Marconi Jiang
    Commented Dec 20, 2014 at 12:36

2 Answers 2

Reset to default
2

Suppose each [1] represents a standing person that carries a value (in this case, everybody carries 1).

[1] [1] [1] [1] [1] [1] [1] [1] [1] [1]
[1] [1] [1] [1] [1] [1] [1] [1] [1] [1]
[1] [1] [1] [1] [1] [1] [1] [1] [1] [1]
[1] [1] [1] [1] [1] [1] [1] [1] [1] [1]
[1] [1] [1] [1] [1] [1] [1] [1] [1] [1]
[1] [1] [1] [1] [1] [1] [1] [1] [1] [1]
[1] [1] [1] [1] [1] [1] [1] [1] [1] [1]
[1] [1] [1] [1] [1] [1] [1] [1] [1] [1]
[1] [1] [1] [1] [1] [1] [1] [1] [1] [1]
[1] [1] [1] [1] [1] [1] [1] [1] [1] [1]

How would you suggest counting the number of these people? Well, one way to solve this problem is to stop by each person and ask him/her about the value he/she carries and add these values together. For example, we would add

1 + 1 + ... + 1 for each person in the room

If there are n persons in the room, this would take us exactly n steps. This algorithm has a linear run time because as the number of people in the room grows larger, the number of steps we take will grow linearly larger. For example, if the there were n + 10 persons in the room, we would take n + 10 steps to count them.

Fortunately, there's a faster algorithm in the sense that we can take less number of steps. This algorithm is as follows

  1. let exactly half the number of persons in the room leave.
  2. for each person that leaves, have his/her value added to a stayed person.
  3. repeat until you only have one person left.

Let's visualize this algorithm

Step 1:

[2] [2] | [2] [2] | [2] [2] | [2] [2] | [2] [2]
-----------------------------------------------
[2] [2] | [2] [2] | [2] [2] | [2] [2] | [2] [2]
-----------------------------------------------
[2] [2] | [2] [2] | [2] [2] | [2] [2] | [2] [2]
-----------------------------------------------
[2] [2] | [2] [2] | [2] [2] | [2] [2] | [2] [2]
-----------------------------------------------
[2] [2] | [2] [2] | [2] [2] | [2] [2] | [2] [2]

Step 2:

[4] [4] | [4] [4] | [4] [4]
---------------------------
[4] [4] | [4] [4] | [4] [4]
---------------------------
[4] [4] | [4] [4] | [4] [4]
---------------------------
[4] [4] | [4] [4] | [4] [4]
---------------------------
[4]

Step 3: 

[8] [8] | [8] [8] | [8] [8]
---------------------------
[8] [8] | [8] [8] | [8] [12] 
/* NOTICE that we added the values of 2 leaving person to one stayed person
 * BECAUSE we cannot have 1/2 a person leave */

Step 4:

[16] [16] | [16] [16] | [16] [20]

Step 5:

[32] [32] | [36]    
/* NOTICE that we added the values of 2 leaving person to one stayed person
 * BECAUSE we cannot have 1/2 a person leave */

Step 6:

[100]

So it took us exactly 6 steps to count the number of people. The run time of this algorithm is logarithmic (exactly log base 2 of n where n is the size of input). Because as the size of input doubles, we take only one extra step to count the number of people. So if we had 200 persons in the room, we would take 7 steps. You can try that!

Improve this answer
9
  • I could visualize something better than before. But, Will you please explain how log (math thing) is related here?
    – Sathya R
    Commented Dec 20, 2014 at 14:14
  • Great visualization way to illustrate the concept. While I still have one question is who is controlling it, or passing the information among the crowd. In your illustration, you watch the crowd from a helicopter, who oversees all the people and make the grouping. But among the crowd itself, how people know who will stand/sit down (or leave) and who carries the numbers to the one who still stands. It is still not clear to me.
    – Marconi Jiang
    Commented Dec 20, 2014 at 15:57
  • @MarconiJiang well, this was a demonstrating problem. The idea is to understand what an algorithm is and that there are algorithms that are more efficient than other algorithms. In this situation, the people in the room are the ones that are executing your algorithm themselves. If you took that to a computer, and as you will shortly know, you write a set of instructions (a computer program) and the computer processor (aka CPU) is the one that is responsible for executing these instructions.
    – kzidane
    Commented Dec 20, 2014 at 16:54
  • "how people know who will stand/sit down (or leave) and who carries the numbers to the one who still stands." ... the two people involved will decide. one will sit down and one will keep counting.
    – curiouskiwi ♦
    Commented Dec 21, 2014 at 3:07
  • @curiouskiwi is certainly right! It doesn't matter at all in this situation who stays and who leaves. This decision could be randomly made.
    – kzidane
    Commented Dec 21, 2014 at 4:10
0

Use the similar illustration from Kareen, and my own interpretation. Though it is still more structured way of implementation. In reality, it could be more randomly.

Step 1

[1] [1] [1] [1] [1] [1] [1] [1] [1] [1] [1] [1] [1] [1] [1] [1] [1] [1] [1] [1] [1] [1] [1] [1] [1]

Step 2 ([T] means sit down)

            # for all 5 rows, 1st passed to 2nd, 3rd passed to 4th

[T] [2] [T] [2] [T] # the 5th person passed to 5th of row 2 [T] [2] [T] [2] [2] [T] [2] [T] [2] [T] # the 5th person passed to 5th of row 4
[T] [2] [T] [2] [2] [T] [2] [T] [2] [1]

Step 3 ([t] means sit down in previous step, [T] mean sit down at this step.)

[t] [T] [t] [T] [t] # 2nd and 4th passed (2p) to row 2 [t] [4] [t] [4] [2] [t] [T] [t] [T] [t] # 2nd and 4th passed (2p) to row 4 [t] [4] [t] [4] [T] # 5th passed (2P) to row 5 [t] [2] [t] [T] [5] # 4th passed (2P) to 5th

Step 4 ([t] means sit down in previous steps, [T] mean sit down at this step.)

[t] [t] [t] [t] [t] [t] [4] [t] [T] [6] # 4th pass (4p) to 5th [t] [t] [t] [t] [t] [t] [T] [t] [4] [t] # 2th passed (4P) to row 5 [t] [6] [t] [t] [5]

Step 5: Count the numbers of the persons who are still standing 4 + 6 + 4 + 6 + 5 = 25

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .