| For the first part of this dissertation, we look at two standard algorithms used to sort permutations by t stacks in series. The first is the right-greedy algorithm created by West. The second is the left-greedy algorithm introduced by Atkinson, Murphy, and Ruskuc. They showed that the left-greedy algorithm is optimal for t = 2. By considering where entries of the permutation are at key points in the process, we show that the use of the left-greedy algorithm on t stacks in series will result in sorting any permutation that could be sorted using the right-greedy algorithm on t stacks in series. For t ≥ 2, we show how to construct permutations that can be sorted by just two stacks in series using the left-greedy algorithm, but cannot be sorted by t stacks in series using the right-greedy algorithm. We also prove that when applied to t stacks in series where t > 2, the use of the left-greedy algorithm is not optimal nor is the class of permutations sorted by the left-greedy algorithm closed.; Then we allow the addition of a type of movement on the stacks where entries from the last stack can return to the first stack instead of going to the output. We show that this allowance does nothing to improve the sorting ability of two stacks in series. However, when this move is introduced to three or more stacks in series, we are then able to sort any permutation.; We also look at the parity of the number of permutations of length n sortable by one or two stacks. In the case of one stack, this result is well known. The parity of the number of 2-stack sortable permutations of length n has been recently determined combinatorially by Bona. We present a semi-combinatorial proof that the number of permutations of length n which are sortable by two stacks in series is odd exactly half the time.; Finally, we consider the problem of permutation reconstruction. This problem is an analogue of graph reconstruction, a long-considered question in graph theory. In the case of permutations, the problem can be stated as follows: In all possible ways, delete k entries of the permutation p = p1p2 p3...pn and renumber accordingly, creating &parl0;nk&parr0; substrings. How large must n be in order for us to be able to reconstruct p from this multiset of substrings? That is, how large must n be to guarantee that this multiset is unique to p? It is not difficult to show that if k = 1, then n must be at least five to guarantee the reconstruction of p. We will then present a proof that when k = 2, we only need n to be at least six to guarantee the reconstruction of p. We also present some partial results for when k > 2. |
