The midterm is short so it is unlikely that you will be asked anything
which is too different and requires a proof.
Here, I have identified some relevant exercises but which may be in
the wrong style.
The midterm questions will be in the same style as the assignment
questions (but a bit easier and with fewer questions).
You can always try to resolve some of the assignment questions (especially those you had difficulty with). You can also try to re-prove some of the lemmas and theorems seen in class.
Solving problems that you did not chose in assignment 1.
Prove using rules of inference anything in the table of equivalence
(replacing T by (not F)). It may be better to prove one
direction first and then the other.
Most of these are (too) easy (there will be some easy questions on the
midterm). The starred questions are the right difficulty but because
they are new, they would be (too) hard for the midterm (there will be
some (most likely one) hard question on the midterm).
Also a good number of these are in the wrong "style", although they
are on the correct topics (the midterm questions will be like the
I would also only try a random subset of these as some of them are too
repetitive (maybe just pick one in that case).
- Ch 9.2 (p.608-611) 34,35,36,37,38,45,46,47,48,49,54,55,56,57,58
- Ch 9.4 (p.629-633) 1,2,6,26,28,29,30,31,34,35,43 (a cut
vertex is a vertex whose removal disconnects the graph)
- Ch 9.5 (p.643-647) 1-11,13-15,30-43,26,44 (except Wn
which we haven't seen),46,47,48,56-64,65
- Ch 9.6 (p.55-657) 2-14,17
Some of these are too difficult. Some of these are the right
difficulty (but hard if they are new). They seem to more accurately
reflect the style of the assignment and midterm questions.
You can also try to prove some of the things in this book that we have
not proven (except for counting). Again, this is probably too hard for
- Ch 7.1 (p.129) 7.1.2,7.1.4
- Ch 7.2 (p.133) 7.2.5,7.2.6,7.2.7,7.2.8,7.2.9,7.2.10
- Ch 7.3 (p.138-140) 7.3.1,7.3.2,7.3.3,7.3.4,7.3.10,7.3.11,7.3.12,7.3.14
- Ch 8.1 (p.145) all
- Ch 8.2 (p.145) 8.2.2,8.2.3
- Ch 8.5 (p.155) 8.5.3, 8.5.4 (a leaf is a vertex of degree 1),8.5.10
- Ch 9.1 (p 160) 9.1.1
- Ch 9.2 (p.163) 9.2.3, 9.2.4, 9.2.5