List, Sample, and Count

<p>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.</p> <p>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.</p>

Name thesis:degree_name

Doctor of Philosophy

Level thesis:degree_level

Doctoral

Discipline thesis:degree_discipline

Computer Science

Grantor

The Graduate School and University Center of The City University of New York

Year dc:date.available

2018

Author dc:creator

• Assarpour, Ali

Advisor dc:contributor.advisor

• Amotz Bar-Noy

Committee members dc:contributor.committeemember

• Theodore Brown
• Matthew Johnson
• Stathis Zachos

• Software Engineering
• Theory and Algorithms

Repository record dc:identifier

https://academicworks.cuny.edu/gc_etds/2869

OAI identifier oai:identifier

oai:academicworks.cuny.edu:gc_etds-3992