(1)
Definition: The degree of a vertex in an undirected graph is the
number of edges incident to it.
Theorem: Σ degree(v) is even across all verticies v.
Prove this using induction on the number of edges in the graph.
induction approach hint
(2)
Prove the following using constructive induction to determine
what a, b, and c must be:
n
Σ i2i = an2n + b2n + c
i=1
CI solution example
(3)
Given the following undirected graph, determine whether or not there
is a path through it which will use each and every edge exactly once.
V = {A,B,C,D,E,F,G,H,I,J}
e = {(A,B),(A,D),(B,C),(B,D),(B,E),(C,E),(C,F),(D,E),(E,F),
(A,H),(B,I),(I,J),(E,H)}
(4)
Draw the following undirected graph and trace performing a BFS on
that graph starting from A to find the shortest distance to every
other vertex from that one. Label the nodes with their distances as you go.
V = {A,B,C,D,E,F}
E = {(A,B),(A,D),(B,C),(C,E),(C,F),(D,E),(E,B),(E,F)}
trace approach suggestion
(5)
Draw a graph representing the prerequisite structure for the 100,200,300
level CMSC courses, changing co-requisites into prerequisites. Then, trace
a DFS of that graph with timing information. Finally, use that timing
information to present the valid order of classes that your particular
DFS generated.
(6) Consider the following challenge:
You have a Boolean expression that has to conform to the resrtriction
that it can only use "and" "or" "not" operators in a form where it is
a "conjunction of paired disjunctions" and where the "not" operator is
only applied to variables.
Example: (a or b) and (b or c) and (!a or !c) and (d or !e)
The goal for this challenge is to design an algorithm that will just
determine whether or not there is a way to assign truth values to the
variables so that the expression will evaluate to true.
You are not being asked to write an algorithm to actually find
such a valid set of assignments if it exists (yet).
After you've thought about the problem for a while, if you aren't sure how
to start, here's a hint to turn this into a graph question.
After you've thought about finding a solution based on that graph representation
for a while, if you aren't quite sure how to advance, here's a hint of how to use
the graph.
(7)
There is a new wilderness adventure park that has been built in the middle
of the Pacific Ocean. They have constructed 1000 artificial islands. They
will also run zip lines (so uni-directional) between various pairs of the
islands. They also plan to release a menagerie of flesh-eating animals into
the waters around and between the islands.
The customer gives a list of n islands from which the company will pick the
drop point and the destination.
They will drop the customer by parachute onto one of the islands on their list,
and then give that customer a mission to end up at another of the islands at
random from their list, traveling only by zip line. Food and shelter on the
islands will be provided.
Their pricing policy is a bit unusual. The base cost is $10,000. However,
if you succeed at getting from your start point to your destination point,
they will discount your vacation price by 1/nth. So, if you choose 10 of
the islands and complete your mission, you only pay $1,000 for the vacation.
The VC funder is a little concerned about the profit model. She has asked you
to provide an efficient algorithm given a proposed set of zip lines to find all
of the island clusters that guarantee a discount, and also the largest possible
such cluster.
There isn't really a hint here, but when you are ready for the answer
here's the basic outline.
(8)
For this question, use the quantified definitions for Ω and Ο
formally prove that 4n2+16n-8 ∈ &Theta(n2).
Note that this will require a constructive proof of constants c and n0
but also note that the two sub-proofs are self-contained.
Ο and Ω example solutions