Monday, September 19, 2011

Thursday, September 8, 2011

Wednesday, August 17, 2011

Sage Notebooks

I just added the first in a series of Sage Notebooks related to Applied Discrete Structures in the wiki. I'm hoping this series might be developed by students in the coming year.

Saturday, August 6, 2011

Comparison of the greedy algorithm with the optimal solutions of the Marriage Problem

In Section 9.5, we introduce graph optimization problems, with an emphasis on the Traveling Salesman Problem and the Network Flow Problem. A the end we mention a few others, including the Minimum Matching Problem, also known as the Marriage Problem. I've just posted a demonstration of this problem, comparing the greedy algorithm with the optimal solution.

This is an example of a cdf file.

Tuesday, August 2, 2011

Fall 2011 version thanks to Automator and PDFpen

The first ten chapters are now bundled together into one pdf for the first time, including the solutions to odd-numbered exercises. The biggest improvement is that the pages are numbered from 1 to 309.

Thought I'd document the process for future reference. Here are the steps:

Procedure for creating one pdf for 92.321

1. Run Workflow "Build_OnePDF_321" using Automator. This pulls out the files in the right order and saves the combined files into a single pdf.
2. Open the resulting pdf in PDFpen
3. Run an Applescript I call "Number_Pages_KL_odd_even" that numbers the pages alternately on the bottom right and left.
4. Annotate front page with semester-specific information.

That's it. With the software executing the workflows, producing the final pdf takes only a few minutes, most of it in step 4.

Thursday, July 7, 2011

Updated first half of Graph Chapter

The first half of Chapter 9, on graph theory, has been updated, with material on degree sequences and more computer implementation notes.

Thursday, May 19, 2011

Thursday, April 7, 2011

Supplementary Exercises for Monoids and Automata

This is a small addition, just 11 additional problems at the end of Chapter 14, on languages. Personally, I haven't used this chapter much lately.

Saturday, March 12, 2011

Second half of Chapter 13: Boolean Algebras

The second half of the Boolean Algebra Chapter is available. We've had a hard time coming up with any program that will draw circuit diagrams so they need to be upgraded sometime.

Wednesday, February 23, 2011

Video: Cosets, an overview

This video is intended to be viewed before reading Section 15.2 of Applied Discrete Structures.

Video: Permutations, an overview

This video is meant to be viewed before reading Section 15.3 of Applied Discrete Structures.

Monday, January 24, 2011

Draft of Second half of Chapter 16 is available

The second half of Chapter 16, on field extensions and formal power series, is available. These two sections will be expanded in the near future to include more examples and theory.

Wednesday, January 12, 2011

Bulgarian Solitaire follow-up

I played Bulgarian Solitaire with math teachers at Lawrence High on January 11, 2011. What's Bulgarian Solitaire? See , although we used coins instead of cards.

Three follow-up items:

  • We didn't get a chance to discuss "Garden of Eden" configurations, but I wanted to point out how this is such a great name. A Garden of Eden position is one that can't be reached from any other configuration in the game. The name does such a good job of capturing the idea behind it!
  • Unlike positions that create one-cycles, which we discussed and seem to be rare, there seem to be lots of Gardens of Eden as you increase the number of coins/cards in the game. For example (2,2,2,2,.....) where there are at least four 2's is Garden of Eden. Do you see why?
  • Technology. You get some interesting macroscopic information about what happens when you change the number of coins by generating state graphs like the one you see above for 10 coins.

    I've prepared a Mathematica Notebook that has more images. They can be viewed using Mathematica or the free Mathematica Player application.

Draft of Chapter 14: Modoids and Automata

A draft of Chapter 14 is now available at

Thursday, January 6, 2011

Draft of Chapter 15

Chapter 15: Group Theory and Applications, is now available. It needs proofreading. Let me know if there are any typos or if you suggest any changes. Plans for the future include an additional section to this chapter that discusses CAS implementations of groups.