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.
","abstract_html":"<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>","abstract_has_math":false,"creators":["Assarpour, Ali"],"institution":"The Graduate School and University Center of The City University of New York","degree_name":"Doctor of Philosophy","degree_level":"Doctoral","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":["Amotz Bar-Noy"],"committee_chairs":[],"committee_members":["Theodore Brown","Matthew Johnson","Stathis Zachos"],"year":2018,"date_issued":"2018-09-01T07:00:00Z","date_published":"2018-09-01T07:00:00Z","updated_at":"2026-07-24T01:59:14Z","subjects":["Software Engineering","Theory and Algorithms"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://academicworks.cuny.edu/gc_etds/2869","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Amotz Bar-Noy"]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Theodore Brown","Matthew Johnson","Stathis Zachos"]},{"key":"dc:creator","label":"Author","values":["Assarpour, Ali"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2020-09-30T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Doctoral"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["The Graduate School and University Center of The City University of New York"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Software Engineering","Theory and Algorithms"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://academicworks.cuny.edu/gc_etds/2869"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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.
"]},{"key":"dc:title","label":"Title","values":["List, Sample, and Count"]}]}],"canonical_facts":{"dc:contributor.advisor":["Amotz Bar-Noy"],"dc:contributor.committeemember":["Theodore Brown","Matthew Johnson","Stathis Zachos"],"dc:creator":["Assarpour, Ali"],"dc:date.available":["2020-09-30T07:00:00Z"],"dc:description.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.
"],"dc:identifier":["https://academicworks.cuny.edu/gc_etds/2869"],"dc:subject":["Software Engineering","Theory and Algorithms"],"dc:title":["List, Sample, and Count"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Doctoral"],"thesis:degree_name":["Doctor of Philosophy"],"thesis:institution_name":["The Graduate School and University Center of The City University of New York"]},"updated_at":"2026-07-24T01:59:14Z"}