Skip to content

Implementation of classical problems in Computer Science in the Answer Set Solving dialect of Clingo.

Notifications You must be signed in to change notification settings

joshuaguerin/Answer-Set-Programming-Algorithms

Repository files navigation

Answer Set Programming "Algorithms"

Background

I have been a logic programming enthusiast for some time. My first experiences were during my undergrad years with Prolog in the early 2000's at Transylvania University. My interest in the subject really began to grow during graduate school at the University of Kentucky where I received formal training in Answer Set Programming and other related topics in formal logic.

My goal for this repo is to bring together solutions/algorithms to classical problems in computer science in the Answer Set Programming dialect of Clingo. Perhaps one day I will write a book on the subject, using this repo as a basis for the text.

"Algorithms"

You are absolutely correct! The term really doesn't apply based on the definition of an algorithm in Computer Science. "Patterns" or "implementations" may be better, but don't really have a solid sound to them. I needed something to call the repo, and I'm modeling the idea off the myriad of books out there with titles like "Algorithms in C++" or "Algorithms in Python." What I'm going for is essentially similar to the purposes of those books--just in a language that isn't inherently algorithmic.

Organization

While I am opting for a flat directory organization at the moment for ease of navigation, one possible organization of the problems for the reader could be:

First Header Second Header
Number Theory Composite Numbers
Prime Sieve
Perfect Numbers
Numerical Set/Partitioning Subset Sum
Equal Sum Partition
Numerical 3-Dimensional Matching
Combinatorial Optimization Knapsack
Bin-Packing
Puzzles/Games N-Queens
Sudoku
Graphs Graph Coloring
Clique
Dominating Set
Independent Set
Vertex Cover
Deterministic Planning Hamiltonian Path
Traveling Salesman
Sequential/Time-Based Planning Wolf, Goat, and Cabbage
Network Flow Max-Flow
Data Mining Clustering

The organization of this table is design to roughly correspond with relative difficulty level of each problem/implementation.

Note about implementations

My goal for this repo is to produce a set of original solutions to common/classical problems in Computer Science, however natural similarities are likely to exist between my own sources and those written by others. I've been influenced greatly over the course of my own studies by the educational resources provided by the good folks over at Potassco. Many of the conventions in my coding carry over from theirs, and similar authors. Additionally, ASP solutions tend to be much smaller than other conventional programming languages. Many NP-Complete or NP-Hard problems can be solved in <10 lines (often <5) of actual code. Variations are likely to exist, however it is entirely likely to have two authors describe the same basic ideas/constraints in their code.

Bugs and other issues

Oh, yea, there will be bugs. It's going to be a while before I'm comforatble enough to label anything as being "done." Assume that everything here is experimental--prone to incorrectness or breakage. Having said that, I'm trying to upload mostly correct code even before I get to thorough testing ;) With that in mind, I would be thrilled if anyone found benefit in reading the examples I've produced here.

I will be using the Issues page to keep organized in terms of progress, bugs, and future ideas for the page.

I don't know if anyone will discover this repo, but if you do and you find a bug or want to chat feel free to hit me up! If you discover any untracked bugs, discussion points, or want to request a solution to a problem please feel free to add or comment on an Issue.

Future updates

I'm mainly pushing this out for fun at the moment, but life is hectic. I have no idea how frequently I'll be able to update, or whether I'll forget about it entirely!