Archive for the ‘Discrete Structures’ Category

Overlay Journal – Discrete Analysis

Saturday, March 5th, 2016

The arXiv overlay journal Discrete Analysis has launched by Christian Lawson-Perfect.

From the post:

Discrete Analysis, a new open-access journal for articles which are “analytical in flavour but that also have an impact on the study of discrete structures”, launched this week. What’s interesting about it is that it’s an arXiv overlay journal founded by, among others, Timothy Gowers.

What that means is that you don’t get articles from Discrete Analysis – it just arranges peer review of papers held on the arXiv, cutting out almost all of the expensive parts of traditional journal publishing. I wasn’t really prepared for how shallow that makes the journal’s website – there’s a front page, and when you click on an article you’re shown a brief editorial comment with a link to the corresponding arXiv page, and that’s it.

But that’s all it needs to do – the opinion of Gowers and co. is that the only real value that journals add to the papers they publish is the seal of approval gained by peer review, so that’s the only thing they’re doing. Maths papers tend not to benefit from the typesetting services traditional publishers provide (or, more often than you’d like, are actively hampered by it).

One way the journal is adding value beyond a “yes, this is worth adding to the list of papers we approve of” is by providing an “editorial introduction” to accompany each article. These are brief notes, written by members of the editorial board, which introduce the topics discussed in the paper and provide some context, to help you decide if you want to read the paper. That’s a good idea, and it makes browsing through the articles – and this is something unheard of on the internet – quite pleasurable.

It’s not difficult to imagine “editorial introductions” with underlying mini-topic maps that could be explored on their own or that as you reach the “edge” of a particular topic map, it “unfolds” to reveal more associations/topics.

Not unlike a traditional street map for New York which you can unfold to find general areas but can then fold it up to focus more tightly on a particular area.

I hesitate to say “zoom” because in the application I have seen (important qualification), “zoom” uniformly reduces your field of view.

A more nuanced notion of “zoom,” for a topic map and perhaps for other maps as well, would be to hold portions of the current view stationary, say a starting point on an interstate highway and to “zoom” only a portion of the current view to show a detailed street map. That would enable the user to see a particular location while maintaining its larger context.

Pointers to applications that “zoom” but also maintain different levels of “zoom” in the same view? Given the fascination with “hairy” presentations of graphs that would have to be real winner.

Dimpl: An Efficient and Expressive DSL for Discrete Mathematics

Sunday, February 28th, 2016

Dimpl: An Efficient and Expressive DSL for Discrete Mathematics by Ronit Jha.


This paper describes the language DIMPL, a domain-specific language (DSL) for discrete mathematics. Based on Haskell, DIMPL carries all the advantages of a purely functional programming language. Besides containing a comprehensive library of types and efficient functions covering the areas of logic, set theory, combinatorics, graph theory, number theory and algebra, the DSL also has a notation akin to one used in these fields of study. This paper also demonstrates the benefits of DIMPL by comparing it with C, Fortran, MATLAB and Python &emdash; languages that are commonly used in mathematical programming.

From the comparison, solving simultaneous linear equations:


Much more is promised in the future for DIMPL:

Future versions of DIMPL will have an extended library comprising of modules for lattices, groups, rings, monoids and other discrete structures. They will also contain additional functions for the existing modules such as Graph and Tree. Moreover, incorporating Haskell’s support for pure parallelism and explicit concurrency in the library functions could significantly improve the efficiency of some functions on multi-core machines.

Can you guess the one thing that Ronit left out of his paper?

You guessed it!

Discrete Mathematics Programming Language – A Domain-Specific Language for Discrete Mathematics.

The Github URL for the repository. 😉

You should check out his homepage as well.

I have only touched the edges of this paper but it looks important.


I first saw this in a tweet by José A. Alonso

Discrete Structures (University of Washington 2008)

Monday, February 25th, 2013

I found the following material following a link in Christophe Lalanne’s A bag of tweets / February 2013 on “Common Mistakes in Discrete Mathematics.”

Clearly organized around a text but it wasn’t clear which text was being used.

Backing up the URI, I found the homepage for: CSE 321: Discrete Structures 2008, which listed the textbook as Rosen, Discrete Mathematics and Its Applications, McGraw-Hill, 6th Edition. (BTW, there is a 7th edition, Discrete Mathematics and Its Applications).

I also found links for:


Lecture Slides

Recorded Lectures

Post-Section Notes (note and a problem correction)

and, the origin of my inquiry:

Common Mistakes in Discrete Mathematics

In this section of the Guide we list many common mistakes that people studying discrete mathematics sometimes make. The list is organized chapter by chapter, based on when they first occur, but sometimes mistakes made early in the course perpetuate in later chapters. Also, some of these mistakes are remnants of misconceptions from high school mathematics (such as the impulse to assume that every operation distributes over every other operation).

In most cases we describe the mistake, give a concrete example, and then offer advice about how to avoid it. Note that additional advice about common mistakes in given, implicitly or explicitly, in the solutions to the odd-numbered exercises, which constitute the bulk of this Guide.

If 2008 sounds a bit old, you’re right. There is an update that requires a separate post. See: UW Courses in Computer Science and Engineering.