Posts

See “Computational Category Theory” by Rydeheard and Burstall for implementation, in ML, of the algorithms in elementary category theory. Following their lead, we present data types in Haskell that can be used to implement basic algorithms in category theory. We use a category in which addition (of integers) can be performed to ground the discussion. You will also need familiarity with types, type variables and classes in Haskell (see learnyouahaskell.com website) to proceed.

CONTINUE READING

A tale of two Knapsacks MathJax.Hub.Config({ tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}, TeX: { equationNumbers: { autoNumber: "AMS" } } }); pre.hljl { border: 1px solid #ccc; margin: 5px; padding: 5px; overflow-x: auto; color: rgb(68,68,68); background-color: rgb(251,251,251); } pre.hljl span.hljl-t { } pre.hljl span.hljl-w { } pre.hljl span.hljl-e { } pre.hljl span.hljl-eB { } pre.hljl span.hljl-o { } pre.hljl span.hljl-k { color: rgb(148,91,176); font-weight: bold; } pre.

CONTINUE READING

⚡ Pluto.jl ⚡ mjx-container[jax="SVG"] { direction: ltr; } mjx-container[jax="SVG"] svg { overflow: visible; } mjx-container[jax="SVG"] svg a { fill: blue; stroke: blue; } mjx-assistive-mml { position: absolute !important; top: 0px; left: 0px; clip: rect(1px, 1px, 1px, 1px); padding: 1px 0px 0px 0px !important; border: 0px !important; display: block !important; width: auto !important; overflow: hidden !important; -webkit-touch-callout: none; -webkit-user-select: none; -khtml-user-select: none; -moz-user-select: none; -ms-user-select: none; user-select: none; } mjx-assistive-mml[display="

CONTINUE READING

This post is a follow-on to the post on the reflection trick in quantum computing. The recipe that we will learn hands-on in this post is again a viral trick that is used all over the place in quantum algorithms that rely on the query model of Boolean functions. The method will also give an alternate way to implement the operator $R$ in $HRH$ in the reflection part of Grover’s algorithm.

CONTINUE READING

This hands-on post aimed at senior undergraduate and graduate students in CS illustrates the amplification trick due to Grover that is central to Quantum Search. Basic familiarity with python and linear algebra (tensor multiplication) is helpful to appreciate the trick and the construction of the quantum circuit. An understanding of Quantum Mechanics is not needed to understand and use Grover’s algorithm. The following beliefs are sufficient to appreciate the power of Quantum i) $n$ particle system keeps track of $N=2^n$ states in its belly, and ii) state changes can be accomplished efficiently by manipulating few particles (local changes) at a time.

CONTINUE READING

! pronounced “cut” is a special goal in prolog which always succeeds. The purpose of cut, loosely speaking, is to freeze some of the choices made by the backtracking sytem so far. Cuts can therefore be used to increase the efficiency (time) of prolog programs. First we will see how the backtracking is affected by the use of cuts. Then we will give an example use of cuts to speed up prolog programs.

CONTINUE READING

We will look at terms (the basic data structure) in prolog. All prolog data and prolog programs are stored as terms. A widely used term type is a list. We will look at several non-deterministic predicates over lists. Using the predicates on lists and their non-deterministic capabilities, we develop a program to do breadth first search (BFS) and a program to solve the n-queens problem. BFS is the basis for many search algorithms in AI such as $A^*$, IDA, $\alpha-\beta.

CONTINUE READING

The starwars way Prolog stands for programming in logic. Prolog programs are specified as relations and rules around the relations defined by programming in logic. The programs can be queried to determine the veracity of facts or to infer new facts using the rules. The specification of the facts and rules will be illustrated using the STAR WARS family tree as per the end of episode 8 at the end of this post (obtained from google images).

CONTINUE READING

“All your proof are belong to us“ The first way we learn to do proofs is by induction. Proofs by induction are done in three steps. First, we establish a base case. Next we assume a hypothesis, and finally, we prove the inductive step. As an example let us consider the fact that the sum $0+1+2+ \ldots+n$ is $n(n+1)/2$. The three steps are: Base case: consider the series $0+1$, the sum is $1$, and the formula is $1(2)/2$.

CONTINUE READING

We look at metaprogramming in Julia. We illustrate parse and eval using the problem of determining a minimal model for a given propositional formula. The computation of minimal models is of interest in answer set programming, as they are used to define stable models 1. The problem of finding a minimal model is NP-complete, whereas the problem of finding a stable model for a given set of propositional statements is $\Sigma_{2}^{P}$ complete.

CONTINUE READING

Let us implement in julia 0.6.0 a binary search tree to store integers. Each node is either of type Nil or of type bst, as declared below. Type Nil is used a null pointer. We use type union MayBe to hold either a Nil() or a bst. At the start the tree is empty so it is initialized to Nil(). Removing the type declaration from the data element should be sufficient to store datatypes for which a comparator is implemented.

CONTINUE READING

Numbers are all In this post, we examine two examples set out in the classic paper by Turing. The first problem is to report the $n^{th}$ binary digit of 1⁄3. The second problem is to report the $n^{th}$ binary digit of $\sqrt{2}$. The 1936 paper On computable numbers, with an application to the Entscheidungsproble describes two machines to perform the tasks. In this post, we give in Haskell two programs for the same.

CONTINUE READING

In this post, we implement in Haskell, the augmenting path method to find a maximum matching in a bipartite graph. We use function composition and recursion mostly. We obtain a simple implementation of an algorithm to compute maximum matching in a bipartite graph. As a side affect of this exercise, you should know about algorithms to compute terminal objects, and fix points in a category. Only a basic familiarity with Haskell is assumed here.

CONTINUE READING

AVL Trees are binary search trees with a balance condition. The balance condition ensures that the height of the tree is bounded. The two conditions satisfied by an AVL tree are: order property: the value stored at every node, is larger than any value stored in the left subtree, and is smaller than any value stored in the right subtree. balance property: at every node the difference in the height of the right and the left subtrees is at most 1.

CONTINUE READING

Let us implement Splay Trees in Julia which is, relatively new and popular, dynamically typed language with multiple dispatch. We model a node in the splay tree as an abstract data type. Each node contains a single integer data value and two references to the left and the right subtrees. The subtrees can be empty, as in the case of leaf nodes, and we model this by using the Nil type.

CONTINUE READING

An emulator for Register Machine Our goal is to implement an emulator for a register machine using flex and bison. In the process we will illustrate a function that assigns numbers to programs, the von Neumann machine, and explain how to write self modifying code. Recall that a register machine has an unlimited number of registers and the following three instructions. HALT, stops the machine INC r j, increments the contents of register r, and moves to instruction number j.

CONTINUE READING

The third conference on algorithms and discrete applied mathematics [CALDAM 2017] is being organized by the Department of Mathematics, BITS Pilani K.K. Birla Goa Campus from February 16 to 18, 2017. Invited Speakers at CALDAM 2017 are Sumit Ganguly, IIT Kanpur Martin C. Golumbic, University of Haifa Günter Rote, Freie Universitaet, Berlin Ola Svensson, EPFL Lausanne The Program Committee Co-Chairs are N. S. Narayanaswamy, IIT Madras and Daya Gaur.

CONTINUE READING