search
Differences
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) | ||
