Math 252
Discrete Mathematics for Computer Science
Spring 2019
[Webwork] [From Class] [Calendar] [Test Info] [Homework]
Test Information
Information about tests will be posted here shortly before each test.
Black out date requests
You can request that we not have a test on a particular day by filling out this form. I can’t promise to meet all requests, but I’ll do what I can to work with the data.
Grading Scales
Here are the grading scales used for each of our tests and the final.
| Grade | test 1 | test 2 | test 3 |
|---|---|---|---|
| A | 69 - 83 | 70 - 86 | 48 - 58 |
| B | 57 - 69 | 60 - 70 | 38 - 48 |
| C | 45 - 57 | 50 - 60 | 29 - 38 |
| D | 33 - 45 | 40 - 50 | 20 - 29 |
Test 1
Date: Wed, March 6
Material Covered: Graphs (Rosen chapter 10.1-10.5, 10.7) and Counting (Rosen 6.1-6.5)
Topics
Graphs: modeling with graphs (what do edges and vertices represent?); types of graphs(directed, undirected, self-loops, etc., etc.); graph terminology (examples: vertex, edge, adjacent, degree, bipartite, path, connected, connected component); graph representations (adjacency matrix, incidence matrix, edge list, adjacency list); graph isomorphism; graph invariants; Euler paths and circuits; Hamilton paths and circuits; planar graphs; Euler’s formula; Kuratowski’s Theorem
Counting: bijection principle (no double counting, no skipping); multiplication principle; addition principle; subtraction principle; division principle; inclusion-exclusion; pigeonhole principle; permutations and combinations; binomial coefficients.
Test 2
Date: Wed, April 3
Material Covered: Counting and Probability (Rosen 6 and 7)
Topics
Counting: Bijection principle (no double counting, no skipping); multiplication principle; addition principle; division principle; inclusion-exclusion; permutations and combinations; binomial coefficients; inclusion-exclusion.
Probability: Definition of finite probability and applications involving counting problems; empirical vs theoretical probability; 3 probability axioms; complement rule; equally likely rule; union rule; conditional probability; indepedence; Bayes probability (e.g., false positives and false negatives); probability trees; random variables; expected value of a random variable.
Note: Counting topics will largely arise in the context of probability calculations.
Test 3
Date: Friday, May 3
Material Covered: Languages, Grammars, and Automata (Rosen 13.1 – 13.4)
Topics
Grammars: components of a grammar (terminals, nonterminals, start symbol, production rules, etc.), derivations, language generated by a grammar, types of grammars (regular, context sensitive, context free).
Automata: components of an automaton (input alphabet, states, start state, final states, transition funciton), DFA, NFA, language recognized by an automaton, building up a complex automaton from component automata.
Regular expressions: notation, 3 base cases and three operations, language represented by a regular expression.
Regular languages: Equivalence of regular expressions, regular grammars, DFAs, and NFAs. (You should know how to do all of the conversions we have learned.) Showing languages are not regular (Pumping Lemma).
Final Exam
Date/Time: 1:30 on Wednseday, May 15 or 9am on Thursday, May 16. (Please come to the time you have indicated so I have enough exam papers.)
Material Covered: The exam will cover topics from the entire semester. In addition to the topics listed above for each test, the following topics are also included:
- Python regular expressions (at the level of the slides we used and the regular expression game).
- Turing Computation: Definition of Turing machine, tracing Turing machines, designing Turing machines, Turing computable languages, all regular languages are Turing computable, Halting Problem.
An example question that could have been on test 3:
We learned an algorithm for converting any DFA into a regular expression. This problem asks you a few questions about that algorithm.
- In the first phase of the algorithm, we must modify the automaton to make sure it satisfies some properties that are necessary for the algorithm to work correctly. What are those properties?
- Demonstrate how to do the first phase using the DFA below.
- In the second phase, states are ``ripped out" of a GNFA until only two states remain. Using that process, show what happens when state \(a\) is ripped out of the GNFA shown below. (You don’t have to complete the process, just do this one step.)
