Substring Search With a Lie
School Name
Spring Valley High School
Grade Level
11th Grade
Presentation Topic
Mathematics
Presentation Type
Non-Mentored
Abstract
In Ulam's liar game, Paul searches for an element e hidden by Carole within the set S = {1, 2, 3, 4, . . . , n-1, n} by asking yes-no questions about the location of the element within subsets of $S$. Carole is allowed to lie to exactly one of Paul's questions. Paul wins in k moves once he knows the value of the hidden element. We extend the results of the traditional Remyi-Ulam Liar Game to a new variation on searching for binary substrings within the analogous binary equivalent of S. Questions are only allowed to ask if the hidden element contains a specific substring. First we considered the game without a lie. We were able to implement a greedy algorithm and additionally determined a log time algorithm that was almost as efficient. With the addition of a lie, we were able to implement an algorithm that worked with bounds n <= 2^{k/2 - 2}. This was not as efficient as q-ary Yes/No questions nor Prefix questions. This was due to the nature of substring search as opposed to a bad algorithm.
Recommended Citation
De, Sparsho, "Substring Search With a Lie" (2020). South Carolina Junior Academy of Science. 106.
https://scholarexchange.furman.edu/scjas/2020/all/106
Location
Furman Hall 121
Start Date
3-28-2020 10:45 AM
Presentation Format
Oral and Written
Group Project
No
Substring Search With a Lie
Furman Hall 121
In Ulam's liar game, Paul searches for an element e hidden by Carole within the set S = {1, 2, 3, 4, . . . , n-1, n} by asking yes-no questions about the location of the element within subsets of $S$. Carole is allowed to lie to exactly one of Paul's questions. Paul wins in k moves once he knows the value of the hidden element. We extend the results of the traditional Remyi-Ulam Liar Game to a new variation on searching for binary substrings within the analogous binary equivalent of S. Questions are only allowed to ask if the hidden element contains a specific substring. First we considered the game without a lie. We were able to implement a greedy algorithm and additionally determined a log time algorithm that was almost as efficient. With the addition of a lie, we were able to implement an algorithm that worked with bounds n <= 2^{k/2 - 2}. This was not as efficient as q-ary Yes/No questions nor Prefix questions. This was due to the nature of substring search as opposed to a bad algorithm.
