Substring Search With a Lie

School Name

Spring Valley High School

Mathematics

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.

Furman Hall 121

Start Date

3-28-2020 10:45 AM

Oral and Written

Group Project

No

COinS

Mar 28th, 10:45 AM

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.