Dissertations, Theses, and Capstone Projects
Date of Degree
9-2018
Document Type
Dissertation
Degree Name
Ph.D.
Program
Computer Science
Advisor
Amotz Bar-Noy
Committee Members
Theodore Brown
Matthew Johnson
Stathis Zachos
Subject Categories
Software Engineering | Theory and Algorithms
Abstract
Counting plays a fundamental role in many scientific fields including chemistry, physics, mathematics, and computer science. There are two approaches for counting, the first relies on analytical tools to drive closed form expression, while the second takes advantage of the combinatorial nature of the problem to construct an algorithm whose output is the number of structures. There are many algorithmic techniques for counting, they cover the explicit approach of counting by listing to the approximate approach of counting by sampling.
This thesis looks at counting three sets of objects. First, we consider a subclass of boolean functions that are monotone. They appear naturally in great variety of contexts including combinatorics, cryptography, voting theory, and game theory. Next, we consider permutations of n pairs of numbers, called Skolem sequences. These sequences are employed in several areas including construction of Steiner triple systems, binary sequences with controllable complexity, interference resistant codes, and graph labeling. Finally, we consider a variation of the n-queens problem, called the queens of the night. This constraint satisfaction problem is not just a recreational puzzle, but rather it is useful in designing conflict free access in parallel systems. In each case we verify previously known values and provide the next unknown exact value(s) in the counting sequence. Furthermore, we approximate the count for the next unknown values in the sequence by employing a sampling procedure.
Recommended Citation
Assarpour, Ali, "List, Sample, and Count" (2018). CUNY Academic Works.
https://academicworks.cuny.edu/gc_etds/2869