Information about tests will be posted here shortly before each test.
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.
Here are the grading scales used for each of our tests and the final. These scales will give some idea how you are doing, but the actual test scores are used to compute grades at the end of the term.
| Grade | test 1 | test 2 | test 3 | final |
|---|---|---|---|---|
| A | 60 - 67 | 74 - 84 | 61 - 72 | 126 - 144 |
| B | 51 - 60 | 62 - 74 | 50 - 61 | 106 - 126 |
| C | 42 - 51 | 50 - 62 | 40 - 50 | 86 - 106 |
| D | 33 - 42 | 36 - 50 | 30 - 40 | 65 - 86 |
Date: Wed, Feb 9
Material Covered: Graphs (Rosen 10.1-10.5, 10.7) and Counting (Rosen 6.1-6.3)
The test will be administered in our classroom (NH 259). You will have 50 minutes for the test (we need to clear the room for the next class). If you are unable to take the test in the classroom, contact me and we will make other arrangements.
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; homeomorphic graphs and subdivisions; proving a graph is not planar without using Kuratowski’s Theorem (like we did for \(K_{5}\) and \(K_{3,3,}\)); proving a graph is not planar using Kuratowski’s Theorem.
Counting: bijection principle (no double counting, no skipping); multiplication principle; addition principle; subtraction principle; inclusion-exclusion; division principle; pigeonhole principle; permutations and combinations; binomial coefficients.
Date: Monday, March 14
Material Covered: Counting and Probability (Rosen 6 and 7)
Counting: Bijection principle (no double counting, no skipping); multiplication principle; addition principle; division principle; inclusion-exclusion; (permutations and combinations); binomial coefficients; “donut” problems.
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; multiplication rule; independence; Bayes probability (e.g., false positives and false negatives); probability trees (optional); random variables; expected value of a random variable; linearity of expected value; Binomial distributions.
Date: Wed, April 13
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 function), DFA, NFA, language recognized by an automaton, building up a complex automaton from component automata; .
Regular expressions: Notation, three 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 the following conversions: DFA \(\to\) NFA; NFA \(\to\) DFA; regular expression \(\to\) NFA; regular grammar \(\to\) NFA; NFA \(\to\) regular grammar; DFA/NFA \(\to\) regular expression.
Basically, you should know all the arrows on this diagram:
\[ \Large \begin{array}{ccccccc} \mathrm{DFA} & \longleftrightarrow & \mathrm{NFA} & \longrightarrow & \lambda\mathrm{-NFA} & \longrightarrow & \mathrm{GNFA} \\ && \downarrow \uparrow & \nwarrow & & \swarrow \\ & & \mathrm{regular}& & \mathrm{regular} \\ & & \mathrm{grammar}& & \mathrm{expression} \end{array} \]
Turing Machines: Definition of Turing machine, tracing Turing machines, designing Turing machines, Turing computable languages, all regular languages are Turing computable.
Note:
Date/Time: 1:30 pm on Wednesday, April 27 or 9 am on Thursday, April 28.
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).
re.search(), re.findAll(), re.sub(), etc. and be able to figure out what they return.The Pumping Lemma and showing that a language is not regular.
Turing Computation: This was on the list for test 3, but didn’t actually end up on the test. Don’t forget about this topic just because it wasn’t on that test.
I’m currently planning to offer a review session noon-1:15 on Tuesday.
As you prepare for the final exam, you can post questions here. Add your initials after the question. If you see a question that you would also like to ask, add your initials. If you later figure it out on your own, you can delete your initials.
I can’t promise to answer every question posted, but I may be able to answer some in the document and may use others at the review session. I’ll likely prioritize questions that several people have tagged with their initials.
Here are soem things you may find useful as your prepare for the final.
Go back over your three tests to make sure you (a) remember how to do what you were able to then and (b) figure out how to do the things you could not do then.
Go through the topics lists for each test (above) and mark the ones you espcialy need to review. Cross them off the list once your review is complete.
Use the homework problems as practice. You might focus especially on the ones in square brackets, especially the one in the review questions and supplemental exercises at the end of the chapters.
Create review sheets that help you organize the material in a way that works for you.
Use the final exam question document to record questions.
Come to the review session.