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/07 10:35] 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 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) |