Due Dates: Oral presentations of material begin on 6 December.
Written descriptions of material presented due one week after presentation.
Topics: P and NP (Chapter 7).
An integral part of this class is understanding and presenting the problems
assigned as homework. Everyone is expected to do all the problems,
but we will take turns on who presents the problem solutions to the class
(every 2-3 weeks, depending on the number of students in the class). Within
a week of presenting a problem solution to the class, you must submit a written
description of it, via the Blackboard system. The written solutions
will be posted on the Blackboard website for the class, so, they can used
by everyone to study for the exams. Since it's hard to write
down answers that are concise and are easily readable by all, if you wish
to improve a grade on any problem, you may resubmit it for grading.
Undergraduate Problems
All students enrolled should complete the following:
- Is the following formula satisfiable?
(x ∨ ¬ x) ∧ (y ∨ ¬ y)
where ¬ x means "not x".
- Is the following formula satisfiable?
(x ∧ ¬ x) ∨ (y ∧ ¬ y)
where ¬ x means "not x".
- Is the following formula satisfiable?
(x ∨ y) ∧ (x ∨ ¬ y) ∧ (¬ x ∨ y) ∧ (¬ x ∨ ¬ y)
where ¬ x means "not x".
- Show that the class P is closed under union, concatenation, and complement.
- Analyze the algorithm given on p 145 (second edition, example 3.14) to show
that the language:
CONNECTED = { <G> | G is a connected undirected graph}
is in P.
- A triangle in an undirected graph is a 3-clique. Show that TRIANGLE ∈ P where
TRIANGLE = { <G> | G contains a triangle}
Graduate Problems
Students enrolled for graduate credit, should complete all the undergraduate problems, as well as:
- Show that ALLDFA is in P.
- Show that the class NP is closed under union and concatenation.