CPSC 3115                Discrete Structures in Computer Science
Topics Covered                                                        Spring 2005

1.    Tuesday, January 11
Chapter 1    Introduction to Set Theory
Set Operators: Union, Intersection, Cartesian Product, etc.

2.    Thursday, January 13
Chapter 1    Set Elements vs. Singleton Sets
Power Sets
The Empty Set
Cartesian Product of {1, 2, ... N} with Itself
Formal Definition of a Graph
Examples of Directed and Undirected Graphs
The Adjacency Matrix of a Graph

3.    Tuesday, January 18
Chapter 1    Graph Isomorphism
The sets of graphs Γ(N) and Γ(N, M)
Open neighborhood of a vertex
Degree of a vertex
Some theorems on vertex degrees
Regular, pseudo-regular, and cubic graphs

4.    Thursday, January 20
Chapter 1    Codegree of two vertices
Subgraphs and spanning subgraphs.  Omit induced subgraphs.
Walks, paths, and cycles.
Shortest paths and geodesics
Connected graphs
Acyclic graphs and trees

5.    Tuesday, January 25
Return and review homework set 1

6.    Thursday, January 27
Chapter 1    Trees and Rooted Trees
Theorems on Trees (Presented without proofs)
Spanning Trees (Again)
Eccentricity of a Vertex, Radius and Diameter of a Graph
N-Partite Graphs, Complete Graphs, and Complete N-Partite Graphs
Sparse and Dense Graphs
Weighted Graphs

NOTE:    We shall not cover chapters 2 - 4 of the notes in this class.
Keep them for reference if you take CPSC 5115 (Algorithm Analysis and Design)

7.    Tuesday, February 1
Chapter 5    Basic Boolean Functions: AND, OR, NOT, XOR
Other gates: NAND and NOR
Truth Tables
Labeling Rows in Truth Tables
Proofs Using Truth Tables
Evaluating Boolean Expressions and Representing Them in Truth Tables
The Principle of Duality and Its Surprising Consequences
Mention of the Postulates and Theorems of Boolean Algebra

8.    Thursday, February 3
Chapter 5    More on Proofs in Boolean Algebra
Boolean Expressions: Variables, Terms, SOP and POS Expressions
Normal and Canonical Forms

9.    Tuesday, February 8
Equivalence of Truth Tables and Canonical Forms
S-list and Π-list Versions of Canonical Forms
Translation Between Canonical Forms
Karnaugh Maps for both SOP and POS

10.    Thursday, February 10
More examples of Karnaugh Maps
Applications to Simplifying C++ Logical Expressions

11.    Tuesday, February 15
Return and review homework set 2

12.    Thursday, February 17
Boolean Satisfiability and Its Relation to Minimization of Boolean Expressions

13.    Tuesday,  February 23
Review for Mid-Term Exam

14.    Thursday, February 24
Mid-Term Exam

15.    Tuesday, March 1
Return and review Mid-Term Exam

16.    Thursday, March 3
Introduction to Finite State Machines (FSM)
Sample Finite State Machines: Washing Machines, Traffic Lights, & Vending Machines
Terminology Used in Discussing FSM: State Diagrams and State Tables
Modulo-4 Up Counter

17,    Tuesday, March 8
More on Finite State Machines:
11011 Sequence Detector - With and Without Overlap
1010 Sequence Detector with Overlap
Modulo-4 Up-Down Counter

18.    Thursday, March 10
Finite Automata
Introduction to Mathematical Descriptions of Finite Automata

Tuesday, March 15
NO CLASS - ASSESSMENT DAY

19.    Thursday, March 17
Formal definition of Finite Automata: Moore Machines and Mealy Machines
Examples of Finite Automata: Moore Machines and Mealy Machines
Disadvantages of over-use of FA models in writing computer software

Tuesday, March 22
NO CLASS - SPRING BREAK

Thursday, March 24
NO CLASS - SPRING BREAK

20.    Tuesday, March 29
Applications of Finite Automata
Washing Machines & Traffic Lights
Life Cycle of an Internet Standard
Status of a Line Object in Object-Oriented Programming
Process status in a time-sharing Operating System
Parity Checker: Odd Parity Acceptor and Even Parity Acceptor
Modeling the Transmission Control Protocol (TCP) Handshakes

21.    Thursday, March 31
Finite automata and language recognizers
Strings, Words, Alphabets, and Languages

22.    Tuesday, April 5
Concatenation of languages & Kleene Closure
At this point, a bomb threat was announced, disrupting the class.
Nothing further was discussed today.

23.    Thursday, April 7
Grammars and Formal Languages
Miscellaneous gripes about the evolution of natural languages
An example of generative grammar rules: a subset of English
Syntax vs. semantics: "the silly cow writes convincingly"
Grammar generation vs. recognition - examples from English grammar

24.    Tuesday, April 12
Return and discuss homework set 4

25.    Thursday, April 14
Definitions: Vocabulary, Sentence, Terminal Symbols, and Non-terminal symbols
Another discussion of the subset of English
Productions: X ® Y and X ®  xY; what this means
Four grammar types: phrase structure, context sensitive, context free, and regular.

26.    Tuesday, April 19
Backus-Naur Form
Examples from the book "The Annotated C++ Reference Manual"
Sample grammars: definition of signed integer and signed real number

27.    Thursday, April 21
Grammars and Automata That Recognize Them
Pushdown Automata
Linearly Bounded Automata
Turing Machines
The Church-Turing Thesis and Why It Cannot Be Proved

28.    Tuesday, April 26
Chapter 3: Graph Connectivity and Networks
Standard measures of graph connectivity
Maximum vertex degree, minimum vertex degree
Number of components, vertex connectivity, edge connectivity
Cut vertices, bridges, and blocks
Relation of edge connectivity to minimum vertex degree
Cut vertices and distinct paths

29.    Thursday, April 28
Cut vertices and distinct paths (again)
Bridges and distinct paths
Bridges and cycles
R-Connectivity, Cut Sets, and Internally Disjoint Paths

30.    Tuesday, May 3
Last day of class - Review for Exam