Size Minimizing Strategies for Removing of Redundant Expressions From a Superset

School Name

Governor's School for Science & Mathematics

Grade Level

12th Grade

Presentation Topic

Computer Science

Presentation Type

Mentored

Mentor

Mentor: Chris Healy, Furman University

Abstract

A British gameshow titled “Countdown” has contestants generate mathematical expressions using arithmetic operations and a randomized set of values. The goal is to generate an expression which evaluates nearest to a target quantity given a random set of operators. To simulate contestant’s answers permutations and other strategies generate an exhaustive superset of possible solutions for the given parameters. However, the solution set is huge, filled with redundancies, and needs to be pruned. Our research identified and removed unnecessary expressions based on associativity and commutativity, and further defined a process for deleting operations that nullify a previous operation. The minimized list of expressions will be used for future research on the relative difficulty of evaluating each of these expressions for humans.

Location

Wall 119

Start Date

3-25-2017 11:15 AM

Presentation Format

Oral Only

Group Project

No

COinS
 
Mar 25th, 11:15 AM

Size Minimizing Strategies for Removing of Redundant Expressions From a Superset

Wall 119

A British gameshow titled “Countdown” has contestants generate mathematical expressions using arithmetic operations and a randomized set of values. The goal is to generate an expression which evaluates nearest to a target quantity given a random set of operators. To simulate contestant’s answers permutations and other strategies generate an exhaustive superset of possible solutions for the given parameters. However, the solution set is huge, filled with redundancies, and needs to be pruned. Our research identified and removed unnecessary expressions based on associativity and commutativity, and further defined a process for deleting operations that nullify a previous operation. The minimized list of expressions will be used for future research on the relative difficulty of evaluating each of these expressions for humans.