##### Differences

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

 cs-236:exams [2016/11/03 13:13]egm cs-236:exams [2017/11/14 14:30] (current)brob144 [Midterm 2 Review Topics] Both sides previous revision Previous revision 2017/11/14 14:30 brob144 [Midterm 2 Review Topics] 2016/12/08 12:58 egm [Final Exam Review] 2016/12/07 10:35 egm [Final Exam Review] 2016/12/06 21:28 egm [Final Exam Review] 2016/12/06 21:28 egm [Midterm 1 Review Topics] 2016/12/06 21:27 egm [Final Exam Review] 2016/11/03 14:03 egm [Midterm 2 Review Topics] 2016/11/03 13:17 egm [Midterm 2 Review Topics] 2016/11/03 13:13 egm 2016/10/06 13:43 egm [Midterm 1 Review Topics] 2016/10/06 13:13 egm [Midterm 1 Review Topics] 2016/10/06 12:50 egm [Midterm 1 Review Topics] 2015/11/06 17:18 egm [Midterm 2 Review Topics] 2015/11/06 17:17 egm [Midterm 2 Review Topics] 2015/10/09 09:07 egm 2015/09/01 07:10 egm 2015/09/01 04:32 cgc [Final Exam Review] 2015/09/01 04:31 cgc [Midterm 2 Review Topics] 2015/09/01 04:30 cgc [Midterm 1 Review Topics for Sections 003 and 004] 2015/09/01 04:27 cgc [Midterm 2 Review Topics for Sections 003 and 004] 2015/09/01 04:27 cgc [Final Exam Review for Sections 003 and 004] 2015/04/14 07:37 egm [Final Exam Review for Sections 003 and 004] 2015/04/14 07:36 egm [Final Exam Review for Sections 003 and 004] 2015/04/14 07:36 egm [Final Exam Review for Sections 003 and 004] 2015/03/17 15:27 egm [Midterm 2 Review Topics for Sections 003 and 004] 2015/03/11 15:08 egm [Midterm 2 Review Topics for Sections 003 and 004] 2015/02/05 17:48 egm [Midterm 1 Review Topics for Sections 003 and 004] 2015/01/06 10:28 egm created Next revision Previous revision 2017/11/14 14:30 brob144 [Midterm 2 Review Topics] 2016/12/08 12:58 egm [Final Exam Review] 2016/12/07 10:35 egm [Final Exam Review] 2016/12/06 21:28 egm [Final Exam Review] 2016/12/06 21:28 egm [Midterm 1 Review Topics] 2016/12/06 21:27 egm [Final Exam Review] 2016/11/03 14:03 egm [Midterm 2 Review Topics] 2016/11/03 13:17 egm [Midterm 2 Review Topics] 2016/11/03 13:13 egm 2016/10/06 13:43 egm [Midterm 1 Review Topics] 2016/10/06 13:13 egm [Midterm 1 Review Topics] 2016/10/06 12:50 egm [Midterm 1 Review Topics] 2015/11/06 17:18 egm [Midterm 2 Review Topics] 2015/11/06 17:17 egm [Midterm 2 Review Topics] 2015/10/09 09:07 egm 2015/09/01 07:10 egm 2015/09/01 04:32 cgc [Final Exam Review] 2015/09/01 04:31 cgc [Midterm 2 Review Topics] 2015/09/01 04:30 cgc [Midterm 1 Review Topics for Sections 003 and 004] 2015/09/01 04:27 cgc [Midterm 2 Review Topics for Sections 003 and 004] 2015/09/01 04:27 cgc [Final Exam Review for Sections 003 and 004] 2015/04/14 07:37 egm [Final Exam Review for Sections 003 and 004] 2015/04/14 07:36 egm [Final Exam Review for Sections 003 and 004] 2015/04/14 07:36 egm [Final Exam Review for Sections 003 and 004] 2015/03/17 15:27 egm [Midterm 2 Review Topics for Sections 003 and 004] 2015/03/11 15:08 egm [Midterm 2 Review Topics for Sections 003 and 004] 2015/02/05 17:48 egm [Midterm 1 Review Topics for Sections 003 and 004] 2015/01/06 10:28 egm created Line 3: Line 3: * Basic operations on sets including union, intersection,​ complement, set-difference (set-minus),​ etc. Use these operations to define new sets with specific characteristics. [[Homework 1]]. Sections 2.1-2.3 in the book. * Basic operations on sets including union, intersection,​ complement, set-difference (set-minus),​ etc. Use these operations to define new sets with specific characteristics. [[Homework 1]]. Sections 2.1-2.3 in the book. - * Define set-difference in terms of union, intersection,​ and complement. Concatenate sets of strings. Compute the power set for a given set.  Determine if a function is one-to-one, onto, or bijective. [[Homework 1]]. Sections 2.1-2.3 in the book. * Define set-difference in terms of union, intersection,​ and complement. Concatenate sets of strings. Compute the power set for a given set.  Determine if a function is one-to-one, onto, or bijective. [[Homework 1]]. Sections 2.1-2.3 in the book. - * Write regular expressions to define sets with specific characteristics. Working knowledge of concatenation,​ union, and Kleene star where working knowledge means you can define sets using those operations. [[Homework 2]]. Section 13.4. * Write regular expressions to define sets with specific characteristics. Working knowledge of concatenation,​ union, and Kleene star where working knowledge means you can define sets using those operations. [[Homework 2]]. Section 13.4. - * Design deterministic finite state automaton (DFA) to recognize sets defined by regular expressions. [[Homework 2]]. Section 13.3. Good practice is to first write a regular expression for a language and then construct the DFA to recognize that language. You do not need to show edges to a reject state; rather, assume that any edge not shown means the automaton can no longer read any more input so that state it stops in determines if it accepts or rejects. ​ * Design deterministic finite state automaton (DFA) to recognize sets defined by regular expressions. [[Homework 2]]. Section 13.3. Good practice is to first write a regular expression for a language and then construct the DFA to recognize that language. You do not need to show edges to a reject state; rather, assume that any edge not shown means the automaton can no longer read any more input so that state it stops in determines if it accepts or rejects. ​ - * Write a grammar from an English specification. [[Homework 3]]. Section 13.1. * Write a grammar from an English specification. [[Homework 3]]. Section 13.1. - * Show a right-most derivation and parse tree for a grammar given an input string. [[Homework 3]] is good practice. See the [[Lectures | lecture notes]] related to parsing too. * Show a right-most derivation and parse tree for a grammar given an input string. [[Homework 3]] is good practice. See the [[Lectures | lecture notes]] related to parsing too. - * Left factor a grammar. [[Homework 3]] and [[Homework 4]] are good practice. See the [[Lectures | lecture notes]] related to parsing too. * Left factor a grammar. [[Homework 3]] and [[Homework 4]] are good practice. See the [[Lectures | lecture notes]] related to parsing too. - * Remove left-recursion from a given grammar. [[Homework 4]] is good practice. * Remove left-recursion from a given grammar. [[Homework 4]] is good practice. - * Construct an LL(1) parse table for a given grammar. ​ [[Homework 4]] is good practice. See the [[Lectures | lecture notes]] related to parsing too. Review your your lecture notes from class as we have worked 3 examples now. * Construct an LL(1) parse table for a given grammar. ​ [[Homework 4]] is good practice. See the [[Lectures | 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 either as an evolving tree as done in class or a table. [[Homework 3]] and [[Homework 4]] are good practice. See the [[Lectures | lecture notes]] related to parsing too. * 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 either as an evolving tree as done in class or a table. [[Homework 3]] and [[Homework 4]] are good practice. See the [[Lectures | lecture notes]] related to parsing too. - The textbook has many exercises that can be used for practice; it has answers to all the odd problems to check work. Instructors and TAs will be happy to give feedback on problems you work if you would like.  Best of luck. The textbook has many exercises that can be used for practice; it has answers to all the odd problems to check work. Instructors and TAs will be happy to give feedback on problems you work if you would like.  Best of luck. ==Midterm 2 Review Topics== ==Midterm 2 Review Topics== - Runs in testing center Monday, November 7, through ​Monday, November 9. November 9 is a late day that costs $5. '''​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 10 problems covering the following topics: + Runs in testing center Monday, November 7, through ​Wednesday, November 9. November 9 is a late day that costs$5. '''​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 10 problems covering the following topics: * Show an expression is a tautology or that two expressions are logically equivalent using truth table and '''​without using truth tables.'''​ ([[Homework 5]]) * Show an expression is a tautology or that two expressions are logically equivalent using truth table and '''​without using truth tables.'''​ ([[Homework 5]]) * Apply DeMorgan'​s law to negate expressions with quantifiers. Write equivalent expressions for quantifiers using disjunction,​ conjunction,​ and negation. Show two expressions with quantifiers are equivalent or not equivalent via counter example. ([[Homework 5]]) * Apply DeMorgan'​s law to negate expressions with quantifiers. Write equivalent expressions for quantifiers using disjunction,​ conjunction,​ and negation. Show two expressions with quantifiers are equivalent or not equivalent via counter example. ([[Homework 5]]) * Express English statements using multiple nested quantifiers. Apply De Morgan'​s law to negate expressions with multiple nested quantifiers. ([[Homework 6]]) * Express English statements using multiple nested quantifiers. Apply De Morgan'​s law to negate expressions with multiple nested quantifiers. ([[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. ([[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. ([[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. ([[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 36: Line 26: * Write a Datalog query in terms of relational algebra (select, project, and rename). Write a Datalog rule in terms of relational algebra (select, project, rename, natural join, and general set operations). ([[Relational-database]]) * Write a Datalog query in terms of relational algebra (select, project, and rename). Write a Datalog rule in terms of relational algebra (select, project, rename, natural join, and general set operations). ([[Relational-database]]) - 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. + 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 ​14, 2015, and closes December ​18, 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. It is expected 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 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 and input string + * Show a derivation given a simple grammar and an input string * Remove left-recursion from a simple grammar * Remove left-recursion from a simple grammar * Build an LL(1) parse table for a 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 * 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) * 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 + * Figure out the grammar defined ​by code implementing an LL(1) top-down parser ​and describe the language with a regular expression - * Solve queries on a given Datalog program using resolution + * Solve queries on a given Datalog program using resolution, De Morgan'​s law, and logical equivalences - * Compute the power-set for a given set + * Use relational algebra to interpret a Datalog program and answer queries - * Draw Hasse diagrams from partial orders + * Compute the power-set for a given set and draw a Hasse diagram for a given relational operator - * Do a topological sort of a partial-order + * Draw Hasse diagrams from partial orders ​using the divides-by operator + * Compute least-upper-bounds and greatest-lower-bounds on a partial order + * Identify when a partial order is a lattice * 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 (with its length) ​between two nodes in a graph + * 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 minimum spanning ​trees with its cost + * 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 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 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 ​all that you have learned this semester + * Enjoy an unexpected opportunity to demonstrate ​deeper understanding of a choice topic from the course - * Smugly chuckle before leaving 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)