In Algorithmic Puzzles, Anany and Maria Levitin use many classic brainteasers as well as newer examples from job interviews with major corporations to show readers how to apply analytical thinking to solve puzzles requiring well-defined procedures. Algorithmic puzzles Download eBook pdf epub tuebl mobi. About Author Anany Levitin is a professor of Computing Sciences at Villanova University. He is the author of a popular textbook on design and analysis of algorithms, which has been translated into Chinese, Greek, Korean, and Russian.
There are n students in a class, each in possession of a different personality attribute. As they are new in the school, so they want to know about each other. To help the students, the teacher decides to conduct an activity. The rule for the activity is that the students will share the personality attributes of each other through a series of bilateral conversations (e.g., via a telephone). Assume that in every conversation both parties exchange all the personality attributes they know at the time. What is the minimum number of conversations they need to guarantee that everyone of them gets all the personality attributes?
Solution :
Let us denote the n students as S1, S2, S3, ………, Sn.
When the Number of students (n) = 1, then the number of conversations required is 0 as no bilateral conversation is possible.
For n = 2, the number of conversations required is 1 i.e, between S1 and S2.
For n = 3, three conversations are needed which are as (S1 with S2), (S2 with S3), (S1 with S3)).
Let us denote the n students as S1, S2, S3, ………, Sn.
When the Number of students (n) = 1, then the number of conversations required is 0 as no bilateral conversation is possible.
For n = 2, the number of conversations required is 1 i.e, between S1 and S2.
For n = 3, three conversations are needed which are as (S1 with S2), (S2 with S3), (S1 with S3)).
For n = 4, four conversations are needed.
For n = 5, six conversations are needed.
For n = 6, eight conversations are needed.
The above figures shows the optimal personality attribute sharing via bilateral conversations. The sequential order of conversations is indicated by the labels on the edges connecting the vertices, representing the conversing parties. The order of conversations can vary.
The logic can be further extended to n = 7, 8 and so on. If observed then it can be seen that the total number of conversations in this algorithm is equal to 2(n – 4) + 4 = 2n – 4 where n >= 4.
What is the best way to make conversations ensuring minimality:
For n > 4, the solution for n = 4 can be extended by making each of students S5, S6, . . ., Sn talk with person S1 before S1 talks with S2, S3 with S4, S1 with S4 and S2 with S3 and then making S1 talk with each of students S5, S6, . . ., Sn for the second time.
For n > 4, the solution for n = 4 can be extended by making each of students S5, S6, . . ., Sn talk with person S1 before S1 talks with S2, S3 with S4, S1 with S4 and S2 with S3 and then making S1 talk with each of students S5, S6, . . ., Sn for the second time.
Note: The order of conversations may vary but the total number of minimum conversations will remain same which can be clearly seen in images for n = 6.
Reference : Algorithmic Puzzles – Anany Levitin, Maria Levitin
Recommended Posts:
If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to [email protected]. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please Improve this article if you find anything incorrect by clicking on the 'Improve Article' button below.
- The most important change in this edition is the new order of the chapters on decrease-and-conquer and divide-and-conquer. There are several advantages in introducing decrease-and-conquer before divide-and-conquer:
- Decrease-and-conquer is a simpler strategy than divide-and-conquer.
- Decrease-and-conquer is applicable to more problems than divide-and-conquer.
- The new order makes it possible to discuss insertion sort before mergesort and quicksort.
- The idea of array partitioning is now introduced in conjunction with the selection problem. The author took advantage of an opportunity to do this via the one-directional scan employed by Lomuto’s algorithm, leaving the two-directional scan used by Hoare’s partitioning to a later discussion in conjunction with quicksort.
- Binary search is now considered in the section devoted to decrease-by-aconstant-factor algorithms, where it belongs.
- The second important change is restructuring of Chapter 8 on dynamic programming. Specifically:
- The introductory section is completely new. It contains three basic examples that provide a much better introduction to this important technique than computing a binomial coefficient, the example used in the first two editions.
- All the exercises for Section 8.1 are new as well; they include well-known applications not available in the previous editions.
- The author also changed the order of the other sections in this chapter to get a smoother progression from the simpler applications to the more advanced ones.
- More applications of the algorithms discussed are included.
- The section on the graph-traversal algorithms is moved from the decrease-and-conquer chapter to the brute-force and exhaustive-search chapter.
- The Gray code algorithm is added to the section dealing with algorithms for generating combinatorial objects.
- The divide-and-conquer algorithm for the closest-pair problem is discussed in more detail.
- Updates include the section on algorithm visualization, approximation algorithms for the traveling salesman problem, and the bibliography.
- The author added about 70 new problems to the exercises. Some of them are algorithmic puzzles and questions asked during job interviews.