Title

Substring Search With a Lie

Author(s)

Sparsho De

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.

Location

Furman Hall 121

Start Date

3-28-2020 10:45 AM

Presentation Format

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.