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
Adjacency Lists and Adjacency Matrices
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
Chapter 6 Logical
Adjacency
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