New - Probability Chapter!

Although we mention probabilities in the coding theory chapter of Appied Discrete Structures, we've alway relied on students' prior background. I've decided to add a short two-section chapter (link to draft) that introduces enough of the general theory to make the coding theory self-contained. I'm attaching a draft of the chapter. I haven't decided exactly where this content will be integrated into the whole book in next year's version. For now, I intend to link to it on https://discetemath.org in the near future.

Any comments would be welcome at kenneth_levasseur@uml.edu

Word Clouds of ADS Chapters

 I'm teaching the second semester of our Discrete Structures sequence and gave a quiz simply asking students to define group.  The results were not so good.  The emphasize how important it is to know this and other definitions, I decided to construct a word cloud of Chapter 11, which is an introduction to Algebraic Structures, mostly groups.   

My first attempt - just asking Mathematica to construct a word cloud of the text -  was not satisfactory since all the non-math words got in the way, although group was still prominent.  My solution was to take the index of the book and generate a list of the words in it.   Then I selected from the text only those words that appear in the index, keeping duplicates.  The result is pretty good.  I did the same for the chapter on graphs, Chapter 9.

Word Cloud for Chapter 11

Word Cloud for Chapter 9

One benefit of doing this is that I could catch words that should be in the index that are missing. One word I expected in the graph cloud was edge.  It was totally missing because I had neglected to include it in the index - something that I'm going to fix!

Applied Discrete Structures now available on LibreTexts!

Without having to ask me, the LibreTexts project has adopted Applied Discrete Structures (ADS) to their library!  Don't get me wrong - the point to making ADS an OER project is to make it available to as many instructors and students as possible at no cost. So I'm delighted that they've added the project.  

I was unfamiliar with LibreTexts until now. Understandable because its a relatively new project.  It started with Chemistry content but has since branched in to other sciences, mathematics, engineering and more.

For a good introduction to LibreTexts check out this video from LibreFest 2023

Applied Discrete Structures is still available in other form factors at https://discretemath.org

New: Applied Discrete Structures is on Runestone Acadamy

Applied Discrete Structures is now available on Runestone Academy. To access it, go to the Runestone Library Mathematics list. 

 At this point the book doesn’t have reading questions so the fully capabilities of Runestone are  not being fully utilized.  By 2024, I’m hoping to have added a pool of reading questions for most sections. This will allow students to test their reading comprehension in a low-stakes environment. Instructors can incentivize students’ reading by grading completion of reading assignments. Currently, a record is only kept of which sections of the book have been opened by each student. 

Applied Discrete Structures is still available in other form factors at https://discretemath.org

Version 3.10 of Applied Discrete Structures - May 2023

 The new version of Applied Discrete Structures has been released in all but the print version. The two most significant changes in this version are 

• Equivalence classes are now defined within the text (Section 6.3) as opposed to being introduced in an exercise.
• A glossary. Many of the words in this glossary are not formally defined in the book either because they are viewed as prerequisites to a course in discrete mathematics or are terms in computer science that some students may be unfamiliar with.

The usual minor typos have been corrected and a few exercises have been added or revised. 

The html and pdf versions are available now at https://discretemath.org.  

The print version will be available later this summer. It’s available roughly at cost, but prices have been inching up in recent years.  Last year the full version was $43+shipping.  Seems high to me, but still not as bad as many of the prices for books offered by publishers. As expected, sales have also dropped. No big deal - the print form factor exists mostly to qualify the book for a few OER listings that require it.

🔗

• 🔗

A new matrix multiplication record

In Chapter 5, we mentioned Strassen’s algorithm for matrix multiplication. Not many improvements have been made since 1969 when Strassen discovered how to multiply a \pair of 4 by 4 matrices with 49 multiplications - a reduction of 15 multiplications from the  basic definition. A further reduction by one multiplication was announced by two Austrian researchers at Johannes Kepler University Linz in October 2022. 

https://science.slashdot.org/story/22/10/13/2259214/deepmind-breaks-50-year-math-record-using-ai-new-record-falls-a-week-later?utm_source=rss1.0mainlinkanon&utm_medium=feed

Does learning about quantifiers help students understand limits?

 A recent thread on the MAA member web site discussed how limits should be taught in Calculus I/II. One comment was that students who take a discrete math course, where quantifiers are discussed, might better understand the definition of a limit.  What follows is a possible example that could be added to our section on quantifiers. Background:  I taught a calculus workshop for mostly middle school teachers several years ago and I recall the most spirited discussion being around the idea that $0.999…  = 1$.

Example: What does it mean that 0.999… = 1?  The ellipsis (…) implies that there are an infinite number of 9’s on the left of the equals sign.  After many years of struggling with what this means, mathematicians have come up with a universally accepted interpretation involving quantifiers.  It is that

$$(\forall \epsilon)_{\mathbb{R}^+} ((\exists N)_{\mathbb{P}})(n\geq N \Rightarrow  |1- 0.\underbrace{99..9}_{n\,9’s}| \lt \epsilon))$$

In calculus, the symbol $\epsilon$ is usually reserved for small positive real numbers. Let’s pick a value for $\epsilon$ and peel the universal quantifier off the statement above.  Let’s try  $\epsilon$ equal to $\frac{1}{2^{10}}=\frac{1}{1024}$.  In addition we note that $0.\underbrace{99..9}_{n\,9’s}=1-\frac{1}{10^n}$.  With our choice of $\epsilon$ we get 

$$ (\exists N)_{\mathbb{P}}(n\geq N \Rightarrow  |1- 0.\underbrace{99..9}_{n\,9’s}| \lt \frac{1}{1024}) $$

or

$$(\exists N)_{\mathbb{P}}(n\geq N \Rightarrow \frac{1}{10^n} \lt \frac{1}{1024}) $$

This last statement is true - one value of  $N$ that would work is $11$. You just have to convince yourself that any positive value of $\epsilon$, no matter how small, will produce a true statement.  If you see that, you’ve convinced yourself that $0.999…  = 1$!

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.

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.

Download the first draft of Part 1.

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.

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.

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.

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.

Appendix on Determinants

Determinator Comic:
from Courtney Gibbon's
 Brown Sharpie (CC: BY-NC-NA)

In our original 1980's text, we had an 11 page appendix on determinants.  That was probably overkill since our inclusion of matrix diagonalization isn't really mainstream discrete math, but back then the exact content of a discrete math course wasn't so well defined.   When I revived Applied Discrete Structures, I never got around to converting the determinant appendix.  We still have diagonalization in chapter 12 and for completeness I've put together a more compact appendix.  Right now, a draft is available as a pdf at http://discretemath.org.  

I haven't decided whether to integrate it into the text or just leave it as a supplement. I'm concerned that the full print version is getting a bit unwieldy.  I'm hoping to find a way to automatically exclude it from the print version but include it in the web version, where length isn't an issue. 

Disjoint Sets

Randall Munroe (XKCD) recently posted a funny example of  two disjoint sets.   I've used one of his webcomics, with permission, in Chapter 1 of Applied Discrete Structures, so I probably won't use this but wanted to acknowledge it.


Link to this comic on XKCD

New in Version 3.5 of Applied Discrete Structures

The latest version of Applied Discrete Structures (3.5) has a few differences from the previous version.  Here is a list of the most significant changes:

In exercises:

• replaced 2.4 exercises 5 and 6 with lattice paths exercises
• added exercise 6 to section 4.1
• added bakery exercise at end of section 5.1
• added exercise #11 to 11.4
• exercise change 11.7 new #5, old #5 moved to #10
• changed exercise 4 of 13.4

Also, there is a new section (12.6)  on  linear equations mod 2.

The Ternary Number System

Every integer is the sum of distinct signed powers of three. That this is true is nice non-elementary, yet accessible, induction proof.  It's not an exercise in Applied Discrete Structures, but could be given as a challenge to your students.  The code implements the ideas of the proof, so it serves as a hint (or a solution?)

Several years ago, I had a WebMathematica page that computed the ternary representation of an integer.   That page is no longer in existence, and I discovered that it several broken links to it were on sequence pages of The On-Line Encyclopedia of Integer Sequences, such as sequence A072998.  As a replacement, I created a SageMath interact (similar to a Wolfram Demonstration).

The SageMath interact converts integers from 1 to 1000 to the ternary number system. It is contained within a Sage Cell, so anyone can view and tinker with the code. Any suggestions for improving it are welcome!

New version (3.5), Custom versions

Version 3.5 of Applied Discrete Structures is now in full distribution in all three formats, html, pdf and print. The full 16 chapters with solutions to half of the exercises runs over 600 pages.  For those who use the html format, the length doesn’t matter much; however, for the print and even the pdf format it may be desirable to have only a subset the chapters or sections.  

I’ve been distributing the book in two parts, corresponding to content that is normally covered in our two semester sequence at  UMass Lowell (Chapters 1-10 in Part 1- Fundamentals; Chapters 11-16 in Part II- Algebraic Structures).  Not many people buy these print versions, but I prefer the lighter books.   I don’t use them all that frequently since I tend to use html in class, but still use them to record typos (finally getting less frequent!) and making notes for improvements. 

One of the nice things about PreTeXt is that it’s quite easy to create custom versions.  If anyone would like some subset of the book in any format, let me know and I’ll create it. The only glitch I foresee is that if a reference is made to a non-included part of the text, a broken link will appear. I think that can be handled minimal extra work. 

Significant Additions in Version 3.5

Section 2.4: new exercises 5  and 6 on lattice paths

Section 5.1: added exercise 8 motivating the definition of matrix multiplication 

Section 11.4: added exercise 11 on inverting a linear function. 

New section: 12.6 Linear Equations over the Integers Mod 2