[Solved] CS440 Homework 1 problem set

The first four problems check your familiarity with materials from CS 205, with problem 4 also touches on graphs, to be discussed briefly in class. The rest of the problems cover subjects of foundational importance to discrete search that will be covered in the next 1-2 lectures.

Problem 1Let the domain of x be {5,3,1,1,3}. Express using negations, disjunctions, and conjunctions, but without quantifiers, the proposition xP(x).

Problem 1 Negate the statements below so that negation symbols immediately precedes predicates (e.g., (P(x,y) Q(x,y)) is not considered correct)

(xy(P(x,y) Q(x,y))) (xyz(P(x,y) P(y,z))).

Problem 3 . Following the greatest common divisor algorithm, find gcd(123,46). Show your work.

Problem 4 Prove via induction that for an undirected simple graph with n vertices, there can be at most edges.

Problem 5Recall that the 8-puzzle problem has eight movable pieces and one empty swap space on a 33 game board. What is the size of the state space if 3 of the pieces are labeled and 5 are unlabeled? That is, the game pieces can be thought of as being labeled 1,2,3,,,,, (see the figure on the right). You only need to provide the formula; there is no need to compute the final number.

Problem 6 List all complete graphs and complete bipartite graphs that are planar. For each graph you list, provide a drawing showing that it is planar.

Problem 7 Give the smallest complete graph that is non-planar. Prove your claim.

[Hint: argue that edge crossings cannot be avoided somehow.]

Problem 8 . Consider a bar consisting of n numbered squares (see the figure on the right). You are to break the bar into smaller ones,

each of which must contain one or more complete numbered squares. (1) How many different bars can be obtained, including the original bar (10 points)? (2) How many possible ways are there for doing the division (5 points)? Extending the bar to be an n m bar formed by nm uniquely numbered squares. We are to obtain smaller rectangular bars consisting of adjacent squares. (3) How many different bars can be obtained, including the original bar (5 points)? [Hint: for the first question, think about one different bar at a time and how a unique bar may be obtained.]