Abstract
dc:description.abstractThe two well-known approaches to designing combinatorial generation algorithms are the recursive approach and the iterative approach. In this thesis a third design approach using coroutines, introduced by Knuth and Ruskey, is explored further. An introduction to coroutines and their implementation in modern languages (in particular Python) is provided, and the coroutine-based approach is introduced using an example, and contrasted with the recursive and iterative approaches. The coroutine sum, coroutine product, and coroutine symmetric sum constructs are defined to create an algebra of coroutines, and used to give concise definitions of coroutine-based algorithms for generating ideals of chain and forest posets. Afterwards, new coroutine-based variations of several algorithms, including the Steinhaus-Johnson-Trotter algorithm for generating permutations in Gray order, the Varol-Rotem algorithm for generating linear extensions in Gray order, and the Pruesse-Ruskey algorithm for generating signed linear extensions of a poset in Gray order, are given.
Degree
thesis:*- Level thesis:degree_level
- Master of Science M.Sc.
- Department thesis:degree_department
- Department of Computer Science
- Year dc:date.issued
- 2015
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Saba, Sahand
- Advisor dc:contributor.supervisor
-
- Ruskey, Frank
Subjects
dc:subject × 3Rights
dc:rights- Statement dc:rights
-
- Available to the World Wide Web
- Licence dc:rights.uri
- Language dc:language.iso
- en, English
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/1828/5879