-
Notifications
You must be signed in to change notification settings - Fork 2
/
quiz_review.html
278 lines (278 loc) · 12 KB
/
quiz_review.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
<head>
<meta charset="utf-8" />
<meta name="generator" content="pandoc" />
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes" />
<title>CS3120 - Quiz Review Guides</title>
<style>
code{white-space: pre-wrap;}
span.smallcaps{font-variant: small-caps;}
div.columns{display: flex; gap: min(4vw, 1.5em);}
div.column{flex: auto; overflow-x: auto;}
div.hanging-indent{margin-left: 1.5em; text-indent: -1.5em;}
/* The extra [class] is a hack that increases specificity enough to
override a similar rule in reveal.js */
ul.task-list[class]{list-style: none;}
ul.task-list li input[type="checkbox"] {
font-size: inherit;
width: 0.8em;
margin: 0 0.8em 0.2em -1.6em;
vertical-align: middle;
}
.display.math{display: block; text-align: center; margin: 0.5rem auto;}
</style>
<link rel="stylesheet" href="../markdown.css" />
</head>
<body>
<h1 id="cs3120---quiz-review-guides">CS3120 - Quiz Review Guides</h1>
<p><a href="../index.html">Back to main page</a></p>
<h2 id="links-to-past-quizzes"><a name="links"></a>Links to past
quizzes</h2>
<p><a href="./sp24-quiz1.pdf">Spring 24 Quiz 1</a></p>
<p><a href="./sp24-quiz2.pdf">Spring 24 Quiz 2</a></p>
<p><a href="./QuizDay1.pdf">Fall 23 Quiz Day 1</a></p>
<p><a href="./QuizDay2.pdf">Fall 23 Quiz Day 2</a></p>
<p><a href="./f23-retakes.pdf">Fall 23 Final Retakes</a></p>
<p><a href="./f23-final.pdf">Fall 23 Final Quiz</a></p>
<h2
id="module-1-review-topics-and-example-questions"><a name="introduction"></a>Module
1 Review Topics and Example Questions</h2>
<p>Module 1 involved a high-level discussion of what computing really
means, as well as a review of proof techniques, cardinality, and other
related topics. This list is <strong>NOT EXHAUSTIVE</strong> and there
may be questions on the quiz that do not cleanly fall into any of the
categories below. Students should be able to do the following on an
assessment:</p>
<ul>
<li><p>Any problem from any of the homework assignments on this module,
including new problems that are similar but have slight
variations.</p></li>
<li><p>Discuss Input/Output of computers as Strings using formal
notation and interpretation simple descriptions of alpabets and sets of
strings. Example questions:</p>
<ul>
<li>If <span class="math inline"><em>Σ</em> = {0, 1}</span>, then what
do the following languages represent: <span
class="math inline"><em>Σ</em><sup>+</sup></span>, <span
class="math inline"><em>Σ</em><sup>2</sup> <em>U</em> <em>Σ</em><sup>3</sup></span>.</li>
<li>Write out a formal description of the following set (you may use set
operators union, concatenation, and star if you want to e.g., <span
class="math inline">{0, 1}<sup>*</sup> <em>U</em> {1}<sup>3</sup></span>):
The set of binary strings in which number of 0’s is exactly three times
the number of 1’s</li>
</ul></li>
<li><p>Understand and describe the properties of functions:</p>
<ul>
<li>Injective, Surjective, and Bijective</li>
<li>Give examples of functions with these properties</li>
<li>Given a function, explain which properties it has:
<ul>
<li>E.g., Consider the function <span
class="math inline">ℕ− > ℕ <em>f</em>(<em>x</em>) = <em>x</em><sup>2</sup></span>.
Is this function injective? surjective?</li>
</ul></li>
<li>Cardinality: Be able to count the number of elements in a set
<ul>
<li>E.g., How many elements are in the set of rational numbers in which
the denominator and numerator can only be 1, 2, or 3?</li>
</ul></li>
</ul></li>
<li><p>Create bijections between two sets to show they have equal
cardinality.</p>
<ul>
<li>Finite sets</li>
<li>Infinite sets</li>
<li>Argue that a provided bijection is injective and surjective
<ul>
<li>E.g., In class we saw a bijection from NxN to N. Argue, in words,
why this function is injective.</li>
</ul></li>
</ul></li>
<li><p>Understand and perform a proof by diagonalization to show that a
set is uncountably infinite.</p>
<ul>
<li>See example from class AND homework problem.</li>
</ul></li>
</ul>
<h2
id="module-2-review-topics-and-example-questions"><a name="introduction"></a>Module
2 Review Topics and Example Questions</h2>
<p>Module 2 involved the introduction of the DFA and NFA machines,
including the class of languages they recognize (regular languages). We
always introduced the regular expressions, a different way of describing
the same class of languages. This list is <strong>NOT
EXHAUSTIVE</strong> and there may be questions on the quiz that do not
cleanly fall into any of the categories below. Students should be able
to do the following on an assessment:</p>
<ul>
<li><p>Any problem from any of the homework assignments on this module,
including new problems that are similar but have slight
variations.</p></li>
<li><p>Understand and describe the difference between a function and a
language. Describe how these are effectively the same but are presented
in a different manner. Convert function descriptions into equivalent
languages descriptions:</p>
<ul>
<li>Describe the language equivalent of this function: This function
takes in strings containing 0, 1, and 2 and returns true if the sum of
the bits is odd, otherwise it returns false.</li>
</ul></li>
<li><p>Show an understanding of Deterministic Finite Automata, how they
work / operate. Be able to:</p>
<ul>
<li>Draw a DFA that recognizes a given language</li>
<li>Describe the language (as a regular expression) that is recognized
by a given DFA.</li>
<li>Step through the computation of a DFA on a given input.</li>
<li>Answer questions about the limitations of DFAs</li>
</ul></li>
<li><p>Show an understanding of the formal description / notation for a
DFA. Write out the description of a DFA using formal notation instead of
a picture (graph notation).</p></li>
<li><p>Show an understanding of the formal definition of a valid
computation on a DFA.</p></li>
<li><p>Do all of the above, but for an NFA</p>
<ul>
<li>Understand and describe non-determinism, its benefits and
limits</li>
<li>Design a simple NFA</li>
<li>Convert and NFA into an equivalent DFA</li>
<li>Explain / prove that NFA and DFAs are equivalent in computational
power.</li>
</ul></li>
<li><p>Show a proof of closure for regular languages under union,
concatenation, and star.</p>
<ul>
<li>Prove closure under a new operation (complement, intersection,
etc.)</li>
</ul></li>
<li><p>Read and write regular expressions as defined in this module.
Answer any of the previous types of questions using regular
expressions.</p></li>
<li><p>Explain the proof that regular expressions are equivalent to
DFA/NFA.</p>
<ul>
<li>Prove a language is regular by providing a regular expression for
it.</li>
</ul></li>
<li><p>Answer questions about the validity of the pumping lemma</p>
<ul>
<li>Use the pumping lemma to prove a language is not regular.</li>
</ul></li>
</ul>
<h2
id="module-3-review-topics-and-example-questions"><a name="introduction"></a>Module
3 Review Topics and Example Questions</h2>
<p>Module 3 was a shorter module that discussed context-free grammars,
push-down automata, and the pumping lemma for CFGs. This list is
<strong>NOT EXHAUSTIVE</strong> and there may be questions on the quiz
that do not cleanly fall into any of the categories below. Students
should be able to do the following on an assessment:</p>
<ul>
<li>Draw a simple pushdown automata for a simple CFG
<ul>
<li>Draw a pushdown automata for this language: <span
class="math inline">0<sup><em>n</em></sup>10<sup><em>n</em></sup></span></li>
</ul></li>
<li>Write out production rules for a simple grammar
<ul>
<li>Write out the Context-Free Grammar for the language <span
class="math inline">0<sup><em>n</em></sup>10<sup><em>n</em></sup></span></li>
</ul></li>
<li>Do the following for PDAs / CFGs:
<ul>
<li>Look at an example PDA and list the language it recognizes</li>
<li>Look at an example CFG and list the language it generates</li>
<li>Look at a PDA with a bug/issue and fix it</li>
<li>Look at a PDA and an example string and describe whether the PDA
accepts the string or not</li>
<li>Detect whether a given string is generated by a given context-free
grammar.</li>
</ul></li>
<li>Discuss the proof of equivalence between context-free grammars and
pushdown automata
<ul>
<li>How do we simulate a context-free grammar with a PDA?</li>
<li>How do we simulate a PDA with a context-free grammar?</li>
</ul></li>
<li>Use the pumping lemma to prove a non-CFG is indeed not context-free
<ul>
<li>Use the pumping lemma to show that <span
class="math inline"><em>a</em><sup><em>n</em></sup><em>b</em><sup><em>n</em></sup><em>c</em><sup><em>n</em></sup><em>d</em><sup><em>n</em></sup><em>e</em><sup><em>n</em></sup></span>
is not context-free</li>
</ul></li>
</ul>
<h2
id="module-4-review-topics-and-example-questions"><a name="introduction"></a>Module
4 Review Topics and Example Questions</h2>
<p>Module 4 introduced the Turing Machine and the notion of
decidability. We also discussed reductions, and some computational
classes (TM non-recognizable, etc.) This list is <strong>NOT
EXHAUSTIVE</strong> and there may be questions on the quiz that do not
cleanly fall into any of the categories below. Students should be able
to do the following on an assessment:</p>
<ul>
<li><p>Interpret a Turing Machine that is described or drawn in detail.
What strings does it accept? What strings does it not accept,
etc.</p></li>
<li><p>Write a TM (in high level prose) that recognizes a given
language</p></li>
<li><p>Describe non-deterministic turing machines accurately that solve
problems using non-determinism.</p></li>
<li><p>Discuss the difference between decidability and
recognizability.</p></li>
<li><p>Discuss the definition of complement, and why the complement
language can sometimes be harder to recognize than the language
itself.</p></li>
<li><p>Prove problems are undecidable through reduction.</p></li>
</ul>
<h2
id="module-5-review-topics-and-example-questions"><a name="introduction"></a>Module
5 Review Topics and Example Questions</h2>
<p>Module 5 took a closer look at different complexity classes within
the <strong>decidable functions</strong>. We started to look at time
complexity as you have seen it in past courses, and break down major
complexity classes that are important to understand as they seem to be
on the edge of our current computing capabilities. This list is
<strong>NOT EXHAUSTIVE</strong> and there may be questions on the quiz
that do not cleanly fall into any of the categories below. Students
should be able to do the following on an assessment:</p>
<ul>
<li><p>State the definition, in multiple ways if applicable, of the sets
P, NP, NP-Hard, NP-Complete. These definitions should be in relation to
Turing Machines and how Turing Machines solve problems.</p>
<ul>
<li>Example Question: What is the formal definition of NP-Hard? How does
this class relate to the set NP? Explain your answer.</li>
</ul></li>
<li><p>Understand the differences between function, decision, and
verification problems. Understand how solutions to one of these helps
(or does not help) in solving the others.</p>
<ul>
<li>Example Question: Suppose I have a decider for the decision version
of traveling salesperson. How can I use this decider to find the optimal
solution directly (the answer to the function problem, which is the
length of the shortest hamiltonian cycle in the graph)?</li>
</ul></li>
<li><p>Understand the relationship between DTMs and NTMs and how they
can or cannot solve problems in the different categories above in
different amounts of time. Proofs of interest include:</p>
<ul>
<li>If an NTM can solve a problem in polynomial time, a DTM can solve it
in exponential time.</li>
<li>Verification with a DTM is equivalent to solving decision problem
with an NTM.</li>
</ul></li>
<li><p>Understand and be able to explain the Cook-Levin Theorem and its
proof of correctness.</p></li>
<li><p>Be able to identify problems that are NP-Complete are prove they
are NP-Complete:</p>
<ul>
<li>Describe a verification algorithm for the problem.</li>
<li>Take a known NP-Complete problem and describe a reduction from this
known NPC problem.</li>
</ul></li>
</ul>
</body>
</html>