**This is an old revision of the document!**

## Midterm 1 Review Topics

The first midterm opens February 9, 2015, and closes February 13, 2015 in the testing center. There are no late days; just be sure you check the testing center scheduler and policies to be sure your plan for when you are taking the test will work. The exam questions are short answers similar to the homework and quizzes, and you will indicate your answers (and show your work) directly on the exam. The exam is double-sided so check both sides of the page. The exam is closed book and closed notes, and is expected to take anywhere from 1.5 to 3 hours depending on your confidence level. The exam has nine problems covering the following topics:

• Concatenate two sets, compute the cross products of sets, compute the power set for a given set, apply set operators to do computation (union, intersection, complement), determine if a function is one-to-one, onto, or bijective. You will want to know your special sets such are reals, integers, positive integers, etc. Homework 1 and Homework 2 are reflective of the problem. Sections 2.1-2.3 in the book cover the topic too.
• Design a finite state machine (FSM) from an English description. Show that machine as a graphical diagram and as a mathematical structure. Homework 2 has you do this design exercise, and we designed a machine in class to control my combination lock down in the locker room. Section 13.2 problems 7 or problem 8 are good examples of this problem.
• Write a regular expression for a language specification in English. Design a deterministic finite state automaton (DFA) that recognizes that same language and rejects words not belonging to the language. Homework 2 treats regular expressions and DFA. Section 13.3 problem 25 is a good practice problem. First write a regular expression for the language and then construct the DFA. You do not need to show edges to the reject state; rather, assume that any edge not shown for an input goes to the reject state.
• Design an automaton to recognize members of a regular expression.
• Write a grammar from an English specification.
• Show a right-most derivation and parse tree for a grammar given an input string. Homework 3 is good practice. See the lecture notes related to parsing too.
• Construct there LL(1) parse table for a given grammar. Homework 4 is good practice. See the lecture notes related to parsing too. Review your your lecture notes from class as we have worked 3 examples now.
• Given an LL(1) parse table, use the table to parse a given input string. Show each step of the parse with the evolution of the stack and input string. Please use the format from class and in the lecture notes. Homework 3 and {[Homework 4]] are good practice. See the lecture notes related to parsing too.

The textbook has many exercises for you to practice on. Instructors and TAs will be happy to give feedback on problems you work if you would like. Best of luck.

## Midterm 2 Review Topics

Runs in testing center Monday, March 16, through Friday, March 20. There are no late days; just be sure you check the testing center schedule and policies so your plan for the test is logically consistent. The exam questions are short answers as before and similar to the homework. You will indicate your answers (and show your work) directly on the exam. The exam is closed book and closed notes. It is expected to take at least 2 hours and up to 3 hours depending on your confidence level. The exam has ten problems covering the following topics:

• Show an expression is a tautology or that two expressions are logically equivalent (Homework 5)
• Write the propositional form of a statement in predicate calculus. Show that two expression are not logically equivalent by finding a counter example. (Homework 5)
• Express English statements using quantifies. Use inference rules to prove a conclusion valid or invalid form the English statements. (Homework 5)
• Express English statements using multiple-quantifiers. Apply De Morgan's law to negate expressions with multiple-quantifiers. (Homework 6)
• Find relevant conclusions from a list of statements using inference rules. Identify the inference rules to support a given argument. Be sure to be able to name each rule and how it is applied. (Homework 6)
• Given an argument over a set of premises, identify if the argument is correct or incorrect. Justify your answer with inference rules. (Homework 6)
• Answer a Datalog query by constructing a proof by contradiction using only resolution and universal or existential instantiation. Show the same proof automated as a search algorithm by drawing the search tree used in the algorithm. Instantiate variables in rules in an informed manner. You do not need to brute force try each possible value. (Homework 6)
• Identify relations that are reflexive, irreflexive, symmetric, antisymmetric, or transitive. (Homework 7)
• Evaluate relational algebra expressions on relations (Homework 7)
• Use relational algebra to write queries to get information from a set of relations (Homework 7 and project 3)

All of the problems on inference and derivatives will be scored on the presence of clearly labeled inference rules applied to any conclusion or premise. You will need to have a working knowledge of these rules and their names as they are not provided with the exam.

## Final Exam Review

The final opens April 17, 2015, and closes April 22, 2015 in the testing center. There are no late days; just be sure you check the testing center schedule and policies so your plan for the test is logically consistent. The exam questions include multiple guess and short answers, so it is a little different than before. You will indicate your answers (and show your work) directly on the exam except for the multiple guess section. The exam is closed book but one page of notes is allowed. I would expect it to take at least 2 hours and up to 4 hours depending on your confidence level. Although the exam is comprehensive, it spends most of its time key themes and the recent topics studied since the last midterm.

• Write regular expressions for simple patterns and identify strings that belong to the language defined by a regular expression
• Show a derivation given a simple grammar and and input string
• Remove left-recursion from a simple grammar
• Build an LL(1) parse table for a grammar
• Demonstrate LL(1) parsing on an input string for a given grammar
• Determine if a relation is reflexive, irreflexive, symmetric, antisymmetric, transitive
• Add pairs into a relation to make it reflexive or transitive (reflexive and transitive closure)
• Complete a proof by contradiction using nothing but logical equivalence, DeMorgan's law, and resolution
• Solve queries on a given Datalog program using resolution
• Compute the power-set for a given set
• Draw Hasse diagrams from partial orders
• Do a topological sort of a partial-order
• Algorithmically compute strongly connected components in arbitrary graphs
• Use Dijkstra's algorithm to compute the shortest path (with its length) between two nodes in a graph
• Use Prim's algorithm to compute minimum spanning trees with its cost
• Use Kruskal's algorithm to compute minimum spanning trees including the use of trees to represent disjoint sets (must know the union-rank operation for trees)
• Show on inductive proof for correctness on an integer formula
• Write a recursive algorithm to perform simple computation and prove the algorithm correct using induction
• Enjoy an unexpected opportunity to demonstrate all that you have learned this semester
• Smugly chuckle before leaving to give the impression that the exam was ridiculously easy (regardless of reality)