Penn State School of Information Sciences and Technology

Discrete Math Teaching Resources

Resource Overview

Discrete mathematics is a fundamental building block for any program in Information Sciences and Technology. This web site provides a set of online resources for teaching and learning many of the concepts in discrete mathematics, particularly the most fundamental ones.

Topics covered include logic and boolean algebra, elementary number theory, direct proof techniques, sequences and induction, set theory, combinatorics and probability, functions and relations, grammars, languages and finite state machines, graphs, and trees.

The resources include static web pages we link to, some static pages we have built, some simple Java applets to illustate concepts, and some more complex Java applets that we link to.

If you have useful Java applets for teaching concepts in discrete math that you'd like to share, please send them our way. We'll thank you and put them up on this web site.

Please consult the following article for an overview of this site:
Mudgett, D. R., Freed, A. R., & Ritter, F. E. (2002). Web-based resources for teaching discrete mathematics to students of information sciences and technology. IEEE Learning Technology, 4(3). 9-10. lttf.ieee.org/learn_tech/issues/july2002/index.html#3

Who we are

Dr. Frank E. Ritter email: ritter{AT}ist.psu.edu

Dr. David R. Mudgett email: dmudgett1{AT}psu.edu

Development of this web site was partially sponsored by the Penn State Fund for Excellence in Learning and Teaching (FELT), project "Java-based Teaching of Mathematics in Information Sciences and Technology", supervised by Frank Ritter and David Mudgett. Andrew R. Freed helped develop it.

Last updated: 16 mar 2012

Suggested Texts

Discrete mathematics with applications. S.S. Epp, (1995), Brooks/Cole, ISBN 0-534-94446-9.
This is the text used in Penn State's discrete math course, IST 230. List of errata

Information Technology - Inside and Outside. D. Cyganski, J.A. Orr, R.F. Vaz, (2001), Prentice Hall, ISBN 0-13-011496-0 is an interesting book showing many applications of the mathematics in this course. It is available in the Penn State bookstore. Also available online at http://cwx.prenhall.com/bookbind/pubbooks/cyganski/

Discrete and Combinatorial Mathematics by R.P. Grimaldi, is another, longer, more detailed textbook.

Bebop to the Boolean Boogie, An Unconventional Guide to Electronics Fundamentals, Components & Processes, by Clive Maxfield, 1995, is an interesting alternative book on how material in this course relates to computers and electronics. Call #TK7868.D5M323 in the PSU Library.

Discrete Mathematical Structures. B. Kolman, R. Busby, S. Ross, 2000, Prentice Hall, ISBN 0-13-083143-3. - Also solution manual by S. Ross, and list of errata.

General Web Resources for Discrete Math 

Forum for Advancing Software Engineering Education      

Alexander Bogomolny's "Cut the Knot" web page - Lots of interesting math pages.

The Math Forum at Drexel University - Lots of links to math resources in many areas, including discrete math.

www.counterpane.com - A newsletter on cryptography that illustrates math occasionally.

MathWorld - A nice mathematics site from Wolfram Research.

courses.cs.vt.edu/~csonline/ - A nice site at Virginia Tech with useful computer science and math pages.

www.math.psu.edu/MathLists/Contents.html - The Penn State Math Department Search Engine.

web.math.fsu.edu/Science/math.html.- The Florida State WWW Mathematics Virtual Library.

Our site, http://acs.ist.psu.edu/discrete-math/index.html, including discrete math applets that we have created (These are also linked below)

Also see links in the next section and remember that your search engine can be a very powerful tool to find more math-related sites.

 

Example IST 230 Language Logic and Discrete Math Class Schedule

Here is an example Syllabus for IST 230 with the resources we have found and created referenced with respect to Epp's book, which we use.

- Here is the link to IST 230 Web Site (but you'll need class username/password to get in.)

Topic(s)

Section in Epp

Resource
Introduction

Math review
Review of basic college algebra
  - Review of algebra by Eric S. Key at UW-Milwaukee
- 99 = 100? algebra dilemma by Alexander Bogomolny
- Bad proof example - Your eyes will deceive you!
- The most common errors in college math from Vanderbilt
- Andy's Amazing Card Trick
Logical forms Epp 1.1 (start) - Truth table constructor by Brian S. Borowski at Seton Hall
- Circuit design software by LogicWorks
Logical Equivalence,
DeMorgan's laws,
Tautologies and Contradictions
Epp 1.1 (finish) Lab 1 - Introductory Lab

- Introductory lab, equipment checkout

- Logic gate demo from realapplets.com
Conditional statements, Arguments 1.2, 1.3 (partial)  
Quantified statements I 2.1 - Negation of quantified statements from ORNL
- Translation tips: How to convert English to
predicate logic from Earlham College
Digital Logic Circuits Lab
- Digital logic circuits.
1.4 Lab 2 - Digital Circuits

- Logic gates - "How Boolean Logic Works" from 'How Stuff Works' web site.
- Digital Logic Circuit Tutorial at www.play-hookey.com
- Boolean logic game - construct 0 through 15 with boolean logic (from 'Cut the Knot' pages)
- The Boolean logic game
Quantified statements II 2.2  
Quantified statements II

- Valid vs. invalid arguments
2.3  
Number Systems Lab
Application - Arithmetic bases, Binary, octal, decimal, hexadecimal numbers - modulo arithmetic - some number puzzles.
1.5 Lab 3 - Number Systems

- Number Systems Lab Links
- Number Systems Lab Notes

- Freeware Binary/Octal/Decimal/Hexadecimal Calculators
Direct proof I

Integers, primes, gcd, lcm, Euclidean algorithm, Unique Factorization, Fermat Factorization
3.1 - A 'proof' that 1 = 2

- gcd from math.com
- lcm from math.com
- Euclidean algorithm from wolfram.com
Direct Proof II 3.2  
Prime Factorization of Integers Lab   Lab 4 - Integer Factorization

- Integer ZoneApplet by Phillip Dorrell on Integers, Primes, Factorization

- Factorization Applet

- Big number calculator - A freeware applet to do calculations with numbers of arbitrary size, by Arnold Reinhold at http://world.std.com/~reinhold
Direct proof III 3.3  
Direct proof IV 3.4 - Finding inverses via Extended Euclidean Algorithm
- UPC codes from wolfram.com
- Hamming code for data transmission error checking [broken]
GCD Lab
Application - Euclid's GCD Algorithm
3.8 Lab 5 - Euclid's Algorithm

- GCD Lab Notes

- Some notes on compiling and running Java Programs

- The BlueJ Java IDE , A freeware Interactive Development Environment from Monash University in Australia

- Euclidean algorithm applet

- GCD calculator applet from University of Minnesota
Sequences 4.1 - Hamming and Fibonacci - links to resources [broken to be fixed]
Induction I 4.2 - Example proof from IST student Sean Leonard
- Lesson 1 from City University (London)
- Lesson 2 from City University (London)
- Lesson 3 from City University (London)
- Lesson 4 from City University (London)
- Example from Seton Hall University
Induction II 4.2-4.3  
Induction III 4.3  
Set theory I

Sets, Subsets, Binary strings
5.1 - Indiana Set Site: Infinite set discussion from Earlham College
- Basic Set Applet: Simple set theory
Set Theory II 5.2 + Empty Set (from 5.3)  
Counting and Probability Multiplication rule 6.1 + Motivation and Basic Ideas, 6.2 - random.org: True random number generator
- Noentropy.net: Non-random number generator [insert '1' here]
- Central limit theorem: statisical analysis by David M. Lane
- Blackjack Applet: learn about odds in Blackjack
Addition rule 6.3  
Cryptography Lab
Application - Coding, Encryption
 

Lab 6 - Cryptography

- RSA cryptography description [broken]

- Legal aspects of RSA by cyberlaw.com [broken]
- Intro to cryptography, brief history
[broken]
- Some elementary Cryptography applets [broken]

Combinations, relationship between combinations and permutations, Pascal's triangle, binomial theorem and coefficients Parts of
6.4-Combinations vs Permutations
6.6-Just Pascal's Triangle
6.7-Just Binomial Theorem
- Pascal's Triangle Applet

- Anagram generator: fun with sequences

- Diamond 16 Puzzle - Permutation of patterns
Application of counting and probability ideas    
Fitts Law Lab   Lab 7 - Fitts Law Experiment

- Log warmup exercises

- Introduction to Fitts law
- Our own Fitts Law Applet
- A different Fitts Law Applet from Virginia Tech

- A Linear Regression Applet from the University of Oregon to fit your data to different versions of Fitts Law

- Entropy and H introduction from [broken]
Functions I 7.1, 7.3  
Composition of Functions, Pigeonhole Principle 7.5, 7.4  
Strings, Languages, Recursion 5.1, pp. 239-241 ;8.1 Links are currently down, but we hope to see them again:

- Languages & grammars overview from Penn State
- Regular expressions
Finite State Automata 7.2  
Intro to graphs

Introductory graph/tree lab
11.1  Lab 8 - Application of Graphs and Trees

- Peter's Problem Applet - A problem closely related to trees
Paths and circuits, Eulerian cycles and circuits, Hamiltonian circuits 11.2 - Eulerian cycles - Intro from IST student Jim Keenan [broken]
- Eulerian circuits and Konigsberg Problem, from National University of Ireland, Maynooth [broken]
- More on Eulerian cycles, circuits, graphical view
- Connection with networks, network reliability from University of Montreal
- Connection with internet: Physics of the web from PhysicsWeb
- Semantic networks: Knowledge representation
- Use in search engines
Trees, spanning trees, Breadth first & depth first searches.

Traversals of binary trees
11.5, Begin 11.6 - Trees tutorial
Spanning trees and graph optimization. Finish 11.6 - Kruskal's algorithm by IST student Ryan McFadden [broken]
- Spanning trees: algorithms from UC Irvine

These applets from University of Patras, Greece demo both Prim's and Kruskal's minimum spanning tree algorithms:
- Prim's algorithm simulation
- Kruskal's algorithm simulation
Flow graphs, applications    
The Future    
Other Possible Topics:   - Finite state machines
- Nardi article on social networks
- BNF forms: syntactic descriptions of programming languages
- Compression algorithms
- Markov models analyze dependent random events
- Task modeling languages
- Predicate calculus for user modeling, a paper by Kobsa and Pohl, from the very useful CiteSeer site.