UMass Lowell Faculty Word Search

 We have another month before the semester gets started, so here is a word search puzzle you can do while you relax in your back yard or the beach. Most of the names are the last names of UMass Lowell Math Faculty and Staff. A few individuals had names too long for the puzzle app to handle, so their first names are used instead. Also, a few of the names are spelled right to left or bottom to top.

Version 3.8 of Applied Discrete Structures is now available!

All forms of Applied Discrete Structures - Version 3.8 are available.  As always, the web and pdf versions are free.  The print copies increased in price due to increases in paper costs passed on by Lulu.  The full version is now $41.00.  I'm not so concerned since very few students buy it.

I didn't keep track of the changes in the new version, but here is a list some of the changes/additions that I recall:

• Exercises in Section 7.1 were rearranged and augmented
• A new exercise in Section 8.2 reviewing quantifiers in the context of sequences.
• A few operations tables were added in Section 11.4 - Modular Arithmetic, including one multiplicative group.
• An exercise similar to one of our final exam questions this spring was added to section 13.1 on posets and lattices.
• A new example was added to the section on algebraic coding (15.5) with a follow-up exercise.

If course there were a few minor typos, but not nearly as many as in previous years!  

UML OERscars - 2021

 The UMass Lowell chapter of MASSPIRG is active in promoting the use of OER materials for students.  I fully agree that it's worth a try for any course.   I'm happy to have been recognized by them at this year's inaugural  OERscars awards ceremony for Applied Discrete Structures. The good news for UML students is that there were faculty from every college recognized for developing and/or using OER materials for their courses. Congratulations to all OERscar winners! 

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.