TABLE OF CONTENTS

I dedicate this work to my parents, my sister Amy, my aunt Linda and my uncle Michael, and my grandparents. ACKNOWLEDGMENTS I would first like to thank my family for being so supportive throughout my graduate school career. I would also want to thank my advisor, Miklós Bóna, for his guidance. His suggestion to look at stack sorting was definitely the turning point in my research. I am very appreciative of David Drake, Andrew Vince, and Neil White for their helpful suggestions and questions during my seminar presentations as well as for serving on my committee. In addition, I would like to thank Meera Sitharam for agreeing to be on my committee and bringing a computer science point of view to the algorithms considered in my thesis. I would also like to thank Kevin Keating and Jonathan King for consistently attending my seminar talks and asking questions I had not considered. In particular, Chapter 3 is the direct result of a question Prof. King asked me when I was presenting my work from Chapter 2. Finally, I am grateful to Bruce Sagan for his suggestions regarding Chapter 5. Thanks to his comments, the proofs in this chapter are significantly less complicated. i