Category: Publishing

Chomp

In 2008, I attended a conference in Athens, the 4th Conference on Computability in Europe (CiE), where my student Craig Wilson and I presented a paper that was fun to write, as it examined the algorithmic complexity of a strategy game called Chomp.

Chomp is a two-player strategy game played on a rectangular grid made up of smaller square cells, which can be thought of as the blocks of a chocolate bar. The players take it in turns to choose one block and “eat it” (remove from the board), together with those that are below it and to its right. The top left block is “poisoned” and the player who eats this loses.

This fun paper, turned out to be one of my most cited works, and how the Wikipedia page dedicated to chomp cites it in its references: Chomp – Wikipedia. 

The paper itself was first published in the conference proceedings, and then in the journal Theory of Computing Systems, 48(3):680-692, 2011:

Cloudifying the Curriculum with AWS

My paper, Cloudifying the Curriculum with AWS, was presented at Frontiers in Engineering (FiE) 2021, in Lincoln, Nebraska, October 14, 2021.

Abstract: This is an Innovate Practice Full Paper. The Cloud has become a principal paradigm of computing in the last ten years, and Computer Science curricula must be updated to reflect that reality. This paper examines simple ways to accomplish curriculum cloudification using Amazon Web Services (AWS), for Computer Science and other disciplines such as Business, Communication and Mathematics.

This paper is an expanded version of a technical report (see here). In particular, it contains material related to teaching Machine Learning (see here).

At the same conference, FiE 2021, I was also part of a panel with Joshua C. Nwokeji, Myra Roldan, and Terry Holmes, on A Hands-on Approach to Cloudifying Curriculum in Computing and Engineering Education.

Abstract: The term cloud computing is used to describe a pool of configurable virtualized computing resources (databases, software, storage, network, servers, etc.) delivered as a service via the Internet. The demand for cloud computing professionals continues to increase, yet academic institutions make little effort to integrate cloud computing into the computing curriculum. Lack of cloud computing resources has been identified as a major hindrance to teaching and learning cloud computing in higher education. This workshop aims to explore resources that could help computing educators teach cloud computing to students. Through hands-on activities, participants will learn about the various resources, tools, and technologies that are freely available for teaching and learning cloud computing.

Algorithmic work of Tyler King from Newbury Park Highschool

During the summer 2021, I was contacted by a high-school student from Newbury Park High School, Tyler King. In his email Tyler said that over the previous summer (2020) he completed a research project on pathfinding algorithms, and that he wanted to share his results with me.

Tyler and I discussed his paper online, and I was really impressed with his work which he titled: Minimum Path Star Topology Algorithms for Weighted Regions and Obstacles. I gave Tyler some feedback, but the work was original and interesting – Tyler’s incredible mathematical maturity made me think that I was lucky to be engaging with a modern day Évariste Galois!

We met a few times, and Tyler invited me to be his co-author, although the work in the paper is his. Tyler is now a student at Cornell university, and his work can be read here: https://arxiv.org/abs/2109.06944.

Enrollment Predictions with Machine Learning

Happy to announce that our joint paper, Enrollment Predictions with Machine Learning, co-authored with Hung Dang, Ginger Reyes Reilly and Katharine Soltys, has appeared in Volume 9, number 2, of the Strategic Enrollment Management Quarterly (SEMQ).

In this paper a Machine Learning framework for predicting enrollment is proposed. The framework consists of Amazon Web Services SageMaker together with standard Python tools for Data Analytics, including Pandas, NumPy, MatPlotLib and Scikit-Learn. The tools are deployed with Jupyter Notebooks running on AWS SageMaker. Based on three years of enrollment history, a model is built to compute — individually or in batch mode — probabilities of enrollments for given applicants. These probabilities can then be used during the admission period to target undecided students. The audience for this paper is both SEM practitioners and technical practitioners in the area of data analytics. Through reading this paper, enrollment management professionals will be able to understand what goes into the preparation of Machine Learning model to help with predicting admission rates. Technical experts, on the other hand, will gain a blue-print for what is required from them.

This paper has been made possible in part by the AWS Pilot Program in Machine Learning where California State University Channel Islands was one if the participating institutions.

Our results in “Edge Covers” picked up by an Astronautics research group at MIT

In May 2018, Ryan McIntyre defended his masters thesis (at CSUCI under my supervision) on  Bounding the size of minimal clique covers. We followed up with a publication of the results in the Journal of Discrete Algorithms (https://doi.org/10.1016/j.jda.2018.03.002) [post], and now, two years later, our results are cited and built upon in an interesting paper Static beam placement and frequency plan algorithms for LEO constellations (https://doi.org/10.1002/sat.1345) written by an Astronautics research group at MIT.

What is interesting about this is the serendipitous manner in which results build on each other: our result consisted in a partial solution to an original problem in combinatorics posed by the itinerant mathematician Paul Ërdos (posed in the mid 1960s), which we then used to partially solve a problem related to string indeterminates (also in this case working on previous results of Joel Helling [post]), which are related to genetics. Now, our work is being used to solve the problem of satellite allocation.

My book “An Intro to the Analysis of Algorithms”

My book, An Introduction to the Analysis of Algorithms, has been identified by the publisher, World Scientific, as one of the most downloaded ebooks. See my page http://www.msoltys.com/book with all the book details and resources (slides, GitHub repository with implementations of all algorithms, solutions to problems, errata, etc.).

Our paper with Neerja Mhaskar on logic of stringology appeard in Discrete Applied Math

In this paper, A new formal framework for Stringology is proposed, which consists of a three-sorted logical theory $latex S$ designed to capture the combinatorial reasoning about finite strings. We propose a language $latex L_S$ for expressing assertions about strings, and study in detail two sets of formulas $latex \Sigma_0^B$, a set of formulas decidable in polytime, and $latex \Sigma_1^B$, a set of formulas with the property that those provable in $latex S$ yield polytime algorithms.

Paper with Ryan McIntyre to appear in the Journal of Discrete Algorithms

Happy to announce that Ryan McIntyre’s masters thesis results, An improved upper bound and algorithm for clique covers (prelim), will be published as our joint paper in Journal of Discrete Algorithms.

Our paper is on indeterminate strings, which are important for their applicability in bioinformatics. (They have been considered, for example, in Christodoulakis 2015  and Helling 2017.)

An interesting feature of indeterminate strings is the natural correspondence with undirected graphs. One aspect of this correspondence is the fact that the minimal alphabet size of indeterminates representing any given undirected graph corresponds to the size of the minimal clique cover of this graph. This paper first considers a related problem proposed in Helling 2017: characterize $latex\Theta_n(m)$, which is the size of the largest possible minimal clique cover (i.e., an exact upper bound), and hence alphabet size of the corresponding indeterminate, of any graph on $latex n$ vertices and $latex m$ edges. We provide improvements to the known upper bound for $latex \Theta_n(m)$. Helling 2017 also presents an algorithm which finds clique covers in polynomial time. We build on this result with an original heuristic for vertex sorting which significantly improves their algorithm’s results, particularly in dense graphs.

This work was the result of building on Helling 2017 (see this post) and of a year of research undertaken by Ryan McIntyre under my (Michael Soltys) supervision at the California State University Channel Islands.

An article from the CSUCI news center about this work can be found here.

Happy that our paper with Ariel Fernandez & Ryszard Janicki will appear in IJCA

Very happy that our paper Computing covers from matchings with permutations, with Ariel Fernández and Ryszard Janicki, is going to appear in the International Journal of Computer Applications.

We present a matrix permutation algorithm for computing a minimal vertex cover from a maximal matching in a bipartite graph. Our algorithm is linear time and linear space, and provides an interesting perspective on a well known problem. Unlike most algorithms, it does not use the concept of alternating paths, and it is formulated entirely in terms of combinatorial operations on a binary matrix. The algorithm relies on permutations of rows and columns of a 0-1 matrix which encodes a bipartite graph together with its maximal matching. This problem has many important applications such as network switches which essentially compute maximal matchings between their incoming and outgoing ports.