Graduate Thesis Or Dissertation
 

Connections between combinatorics of permutations and algorithms and geometry

Public Deposited

Downloadable Content

Download PDF
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/h128ng800

Descriptions

Attribute NameValues
Creator
Abstract
  • Geometric Problems become increasingly intractable and difficult to visualize as the number of dimensions increases beyond three. Inductions from lower dimensional spaces are possible yet often awkward. This thesis shows how elementary linear algebra, vector calculus, and combinatorics offer improved methods for calculating the dihedral angles of n-simplicies and proving a generalization of the Pythagorean theorem directly. A large class of search problems are solved in O(log n) time with a traditional binary search. This thesis extends this to a class of problems where the cost of high guesses differs from the cost of low guesses. Weighted binary searches have broad applicability, and in particular, the bulb drop problem is extended, analyzed and solved. Modern Rubik cube research focuses on solving the cube as fast as possible using heavy machinery and computation. Speed cubists routinely memorize 115 different move sequences and practice relentlessly so that they might solve the cube in 15-20 seconds. Mathematicians apply abstract algebra to perform massively parallel computations in order to seek out the fastest way to solve the cube from any position. The diameter of the Rubik's cube group remains undetermined as of this writing; recently, God's Algorithm, the method of solving the cube in the fewest possible moves from a scrambled position, was given a least upper bound of 26 moves. This thesis considers the problem from the opposite end of the spectrum. What simple classes of move sequences exist that solve the the cube? Since every position of the cube can be achieved by making quarter turns of the faces, quarter turns is a class of moves that solves the cube. It can also be shown that half turns is insufficient. This thesis shows that commutators of quarter turns suffices using methods that have applicability to other cube related problems. There are many ways that the permutation groups may be mapped onto the integers. Some of these maps have interesting properties. This thesis defines several desirable properties for such maps and show how they may aid computation.
License
Resource Type
Date Available
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Publisher
Peer Reviewed
Language
Replaces

Relationships

Parents:

This work has no parents.

In Collection:

Items

Thumbnail Title Date Uploaded Visibility Actions
file details Thesis1e.pdf 2017-08-01 Public Download