This shows you the differences between two versions of the page.

Both sides previous revision Previous revision Next revision | Previous revision | ||

cs-236:exams [2016/12/06 21:28] egm [Final Exam Review] |
cs-236:exams [2017/11/14 14:30] (current) brob144 [Midterm 2 Review Topics] |
||
---|---|---|---|

Line 20: | Line 20: | ||

* Express English statements in propositional logic. Prove a conclusions from a set of propositions and predicates without using resolution. Prove a conclusion from a set of propositions and predicates using only resolution. '''Proofs should look like those done in class being in tabular form with clearly labeled inference rules.'''([[Homework 6]]) | * Express English statements in propositional logic. Prove a conclusions from a set of propositions and predicates without using resolution. Prove a conclusion from a set of propositions and predicates using only resolution. '''Proofs should look like those done in class being in tabular form with clearly labeled inference rules.'''([[Homework 6]]) | ||

* Express English statements in predicate calculus. Use inference rules to prove a conclusion valid or invalid from the predicate calculus statements statements. '''Proofs should look like those done in class being in tabular form with clearly labeled inference rules.'''([[Homework 6]]) | * Express English statements in predicate calculus. Use inference rules to prove a conclusion valid or invalid from the predicate calculus statements statements. '''Proofs should look like those done in class being in tabular form with clearly labeled inference rules.'''([[Homework 6]]) | ||

- | * Answer a Datalog query by constructing a proof by contradiction using only resolution and universal or existential instantiation. '''Proofs should look like those done in class being in tabular form with clearly labeled inference rules.''' ([[Homework 6]]) | + | * Answer a Datalog query by constructing a proof by contradiction using only resolution and universal instantiation/existential generalization. '''Proofs should look like those done in class being in tabular form with clearly labeled inference rules.''' ([[Homework 6]]) |

* Identify relations that are reflexive, irreflexive, symmetric, antisymmetric, or transitive. Add pairs to a relation to make it reflexive, symmetric, or transitive. ([[Homework 7]]) | * Identify relations that are reflexive, irreflexive, symmetric, antisymmetric, or transitive. Add pairs to a relation to make it reflexive, symmetric, or transitive. ([[Homework 7]]) | ||

* Evaluate relational algebra expressions on relations ([[Homework 7]] and [[Relational-database]]) | * Evaluate relational algebra expressions on relations ([[Homework 7]] and [[Relational-database]]) | ||

Line 28: | Line 28: | ||

For all of the problems related to inference, '''proofs should look like those done in class being in tabular form with clearly labeled inference rules that identify the involved statements.''' You will need to have a working knowledge of these rules and their names as they are not provided with the exam. '''You will also need to have a working knowledge of logical equivalences from chapter 1.''' | For all of the problems related to inference, '''proofs should look like those done in class being in tabular form with clearly labeled inference rules that identify the involved statements.''' You will need to have a working knowledge of these rules and their names as they are not provided with the exam. '''You will also need to have a working knowledge of logical equivalences from chapter 1.''' | ||

==Final Exam Review == | ==Final Exam Review == | ||

- | For sections 001 and 002, the final is at the scheduled time in class. For sections 003 and 004, the final opens December 10, 2016, and closes December 15, 2016 in the testing center. 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. It is expected to take at least 2.5 hours depending on your confidence level. Although the exam is comprehensive, it spends most of its time on key themes and the recent topics studied since the last midterm. | + | For sections 001 and 002, the final is at the scheduled time in class. For sections 003 and 004, the final opens December 10, 2016, and closes December 15, 2016 in the testing center. 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 (8.5x11). It is expected to take at least 2.5 hours depending on your confidence level. Although the exam is comprehensive, it spends most of its time on 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 | * 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 an input string | * Show a derivation given a simple grammar and an input string | ||

Line 44: | Line 44: | ||

* Algorithmically compute strongly connected components in arbitrary graphs | * Algorithmically compute strongly connected components in arbitrary graphs | ||

* Use Dijkstra's algorithm to compute the shortest path between two nodes in a graph including extra information to reconstruct the actual path that is the shortest path. | * Use Dijkstra's algorithm to compute the shortest path between two nodes in a graph including extra information to reconstruct the actual path that is the shortest path. | ||

- | * Use Prim's algorithm to compute a minimum spanning trees with its cost including extra information to reconstruct the actual tree. | + | * Use Prim's algorithm to compute a minimum spanning tree with its cost on a give graph including extra information to reconstruct the actual tree |

- | * 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 the trees) | + | * Use Kruskal's algorithm to a compute minimum spanning tree on a given graph including the use of trees to represent disjoint sets (must know the union-rank operation for the trees) |

* Show on inductive proof for correctness on an integer summation formula | * Show on inductive proof for correctness on an integer summation formula | ||

* Write a recursive algorithm to perform simple computation and prove the algorithm correct using induction | * Write a recursive algorithm to perform simple computation and prove the algorithm correct using induction | ||

* Enjoy an unexpected opportunity to demonstrate deeper understanding of a choice topic from the course | * Enjoy an unexpected opportunity to demonstrate deeper understanding of a choice topic from the course | ||

* Smugly chuckle before leaving the testing center to give the impression that the exam was ridiculously easy (regardless of reality) | * Smugly chuckle before leaving the testing center to give the impression that the exam was ridiculously easy (regardless of reality) |