Carleton University - School of Computer Science Honours Project
Winter 2018
The Visualization of Reductions
Jennifer Franklin
SCS Honours Project Image
ABSTRACT
The goal of this honours project was to support students in the formation of a mental image of how reductions work. To realize this goal an application that visually illustrates reductions was developed. Each reduction is displayed in the visual format as shown in the table below. This visual display is meant to align with the actual reduction process where an input x to problem A is taken and using a map, f, to map that to f(x) which is then used as input to problem B. A known algorithm to solve problem B, giving solution y, is then employed. The reverse process of mapping problem B to problem A using process g is then utilized, which would give the solution g(y) for A on the original input x. The application displays as many as eight distinct reductions. A small administration application was built that allows the eight reductions available in the main application to be hidden/unhidden. Problem A Problem B Solution A Solution B Table 1 - Flow and Format of Reductions Displayed