|
General notes
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.
Logic
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.
Graph theory
Rosen's book
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
assignment questions).
- 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
I would also only try a random subset of these as some of them are too
repetitive (maybe just pick one in that case).
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
the midterm.
- 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
|