## Saturday, January 23, 2021

### Binary Decision Diagrams

I've started to explore the feasibility of introducing Binary Decision Diagrams (BDD's) into the topics in the Applied Discrete Structure (ADS) sphere of influence.  Volume 4A of Knuth's Art of Computer Programming has extensive coverage of the topic and there are some neat examples that build on the topics we introduce in ADS.

Here is a very simple example of a BDD that identifies the majority bit value among three bits $b_1 b_2 b_3$.  We can think of any particular value as a case in a truth table with the output being the truth value for that case.  For example, the case $010$ would have a truth value of 0.   The whole truth table is a sequence of eight bits $00010111$, one for each case from $000$ to $111$.  The first half of the truth table corresponds with the case $b_1=0$ while the second corresponds with $b_1=1$.  Starting at the top of the figure below, the red edge is path followed in the $b_1=0$ case while the blue edge is followed in the $b_1=1$ case. In either case, the half of the truth table that is followed is again split depending on the value of $b_2$.    Notice that if $b_1=0$ and then $b_2=0$ we are left with the first quarter of our original truth table, $00$, which produces an output of $0$ no matter what value $b_3$ has so we immediately move to the bottom right vertex, corresponding to a majority value of $0$.   Another interesting situation is that if $b1=0$ and $b_2=1$, the remaining truth table is $01$, which is the same as if $b_1=1$ and $b_2=0$.  This is reflected in the fact that the two cases put us into the same node, where the value of $b_3$ decides the majority value.

Instead of a truth table with eight cases, we have a graph with only six vertices that "computes" the majority value.   This is a modest improvement, but for many more complex Boolean functions, the improvement can be significant.

Another example is to consider a graph with six vertices and ten edges. Suppose we wish to color the graph with three colors; i. e.  identify a valid coloring with no two adjacent vertices having the same color.  A boolean expression that determines whether a coloring is valid can be constructed using propositions of the form $p_{i,j}$ which represents whether vertex $i$ is colored with color $j$. For the case of six vertices and three colors, there are 18 propositions.  If the chromatic number of the graph is three or less, then there would be an assignment of values to these propositions that corresponds with a 3-coloring.  For one particular graph, a BDD for the coloring is below. Instead of a truth table with $2^{18}$ cases, we have a busy looking graph, but it has only 93 vertices.

For this graph we initially move from left to right.  The vertex in the middle corresponds with the assignment of value to the propositions that are not valid colorings for that particular graph. All but six of the assignments end up in that vertex. For examples this size and larger, the graph's embedding in the plane isn't all that useful, but there are data structures such as python dictionaries that can be used to represent the BDD.

This idea of using BDD's in a course is still just an idea.  It might be a good topic for a senior project too.

## Wednesday, February 26, 2020

### Active Applied Discrete Structures - Notes for a Flipped Class

This spring, I decided to take the plunge and attempt teaching our Discrete Structures I course in a flipped class format. I'm almost half way through the semester and it seems to going pretty well.  We had our first hour exam a while ago and grades were higher than in comparable exams from previous semesters. Also, students generally seem to be enjoying the format.

At this point, I've written up all the assignments that students are asked to do before each class meeting and the problems they work on in class.  They comprise 24 "chapters" - one for each class.

In the past, I've gotten requests for an instructor's manual for Applied Discrete Structures and have procrastinated on doing it, but this may be just as valuable.
 A TEAL classroom being set up at UML

We have a few new Technology Enhanced Active Learning  (TEAL) classrooms at UMass Lowell and I've been scheduled in them this year.  Having students in "pods" helps with  the flipped format, although the technology isn't really necessary.

## Monday, December 30, 2019

### Sage Cell Server has migrated to Python 3

I recently discovered that many of the SageMath cells in the web version of Applied Discrete Structures (ADS) were no longer working as they had in the past. Then I found out why.  Apparently, 2020 is the Y2K of the Python Universe.  ... and I was oblivious to it!

The Python 2 language, i.e. Python 2.7.x, is officially being discontinued on January 1, 2020 (first planned for 2015) after which security patches and other improvements will not be released for it.[29][30] With Python 2's end-of-life, only Python 3.5.x[31] and later will be supported.
Due to differences in the two versions of Python, there are two main impacts on the code on the current web version of ADS.

• "print expr" produces an error and needs to be replaced with "print(expr)"
• map produces an iterator instead of a list.  This is fixed by wrapping  list( ) around the map expression if the original output is as desired.  More about iterators.
• keys of a dictionary are are also an iterator and using list is the fix in this situation too.
Fortunately the PreTeXt project has my back and an automated system has been developed to identify all the problems.   I hope to have an updated web version ready for the spring semester.

## Wednesday, September 11, 2019

### Logic Design & Boolean Algebra

The original 1980's version of Applied Discrete Structures had a section on Logic Design, but when I reworked the book starting around 10 years ago, I didn't include that section.  The main reason was that I never could find a good application for drawing gate diagrams.  I still haven't found one that is exactly what I want, but Inkscape comes close. I was able to draw some basic diagrams. Although I'm still not perfectly satisfied with what I have, I think they are good for a draft.

So after a delay of several years, here is a draft version of Section 13.7 A Brief Introduction to Switching Theory and Logic Design.  I developed it as single-section PreTeXt book, so the numbering is 1.1.x instead of 13.7.x.   I intend to add this to the next version of Applied Discrete Structures, in spring 2020.

I'd be interested in whether many users would plan on covering this section in their courses.

## Friday, August 30, 2019

### Professor Al Doerr Memorial Scholarship Fund

One October 14, 2018, Prof. Al Doerr passed away. He was coauthor of Applied Discrete Structures He was on the faculty at UMass Lowell for 50 years. In his honor, the Mathematical Sciences Department has established an endowed scholarship fund in his name. If you or your students want to thank us for the book, you could donate even a few dollars to the Prof. Alan Doerr Scholarship Fund at http://www.uml.edu/give. All proceeds go to a scholarship endowment for our math majors.