Discrete Math Fall 2013

Course Syllabus:

MAD 3107 is an introduction to concepts of discrete mathematics, as used by computer scientists.  

Topics include: symbolic logic and Boolean algebra, prepositional and predicate calculus, sets, 

functions, and relations, enumeration and counting principles, introduction to graphs, trees, 

spanning trees, shortest path and matching algorithms, finite state automata, and Turing machines.

Prerequisities:

MAC 2312 with a minimum grade of C.

Course text:

Discrete Mathematics,  5th edition, by Dossey, Otto, Spence, and Vanden Eynden, Addison-Wesley.

Class Resources:

Lecture 2 - Algorithms and their efficiency

Lecture 4 - Sets, operations, and relations

Lecture 5 - Partial Orderings and Functions

Lecture 9 - Graph Theory

Lecture 9 - Multigraphs and Euler Circuits

Lecture 10 - Distance in Graphs and Shortest Paths

Lecture 10 - Graph Colorings

Lecture 11 - Directed Graphs and Multigraphs

Lecture 12 - Properties of Trees

Lecture 12 - Spanning Trees

Lecture 13 - Depth-First Search

Lecture 13 - Rooted Trees

Lecture 14 - Binary trees and traversals

Lecture 14 - Optimal binary trees

Lecture 15 - Pascal's Triangle and the Binomial Theorem

Lecture 15 -Three Fundamental Principles

Lecture 16- Permutations and Combinations

Lecture 16 - Arrangements and Selections with Repetition

Lecture 17 - Probability

Lecture 18 - Inclusion-Exclusion

Lecture 18 - Recurrence Relations

Lecture 19 - The Method of Iteration

Lecture 20 -- Linear Difference Equations with Constant Coefficients

Lecture 21 -- Counting with Generating Functions

Lecture 22 -- The Algebra of Generating Functions

Lecture 23 -- Boolean Algebra and Logical Gates

Lecture 23 -- Creating Combinatorial Circuits

Lecture 23 -- Supplementary Material

Lecture 24 -- Karnaugh Maps

Homework Sets:

• Assignment 1C

• Assignment 2C

• Assignment 3C

• Assignment 4C  Assignment 4C Assignment 4C

• Assignment 5C  Assignment 5C Assignment 5C  

• Assignment 13C

• Assignment 14C  

• Assignment 15C

• Assignment 16C Assignment 16C 

• Assignment 20C Assignment 20C 

• Assignment 21C Assignment 21C Assignment 21C

• Assignment 22C 

• Induction Examples 

• A website discussing the combinatorics of relations

• Wikipedia page on combinatorial proofs

Review Assignments:

• Review for Exam 1

• Review for Exam 2

• Review for Exam 3

Some interesting research papers in related subjects:

• Roman Domination of Grids and Toroidal Grids 

• Weighted Domination of Grids

• Broadcasting Domination in Graphs

• Capturing a Drunk Robber on a Graph

• The Robber Strikes Back!

• Braess' Paradox in Wireless Networking

A tech article on Braess' Paradox in social networking:

• Braess' Paradox Infects Social Networks Too

Here are some fun computer projects that you can complete by logging onto Sagenb.org.  

Sage is free open source mathematical software based in the python language.  In the process, you will learn some basics about programming in python.

Fun Computer Projects:

• Chapter 1 Project 

Here is an interesting blog post on what it is like for mathematicians to learn math

• Powering Up