Foundations of Discrete Mathematics

COT 2104

Summer 2007

Homework 3

NOTE: This homework will be collected in three stages. The corresponding deadline appears before each set of questions. The final grade of this homework will covered the results of the three stages.

Deadline: 07/10/07 (at the beginning of class)

  1. Multiple personality disorder (MPD) is a condition in which different personalities exist within one person and at various times control that person’s behavior. In a recent survey of people with MPD, it was reported that “98% had been emotionally abused, 89% had been physically abused, and most had experienced both types of abuse.” Make this statement more precise.
  1. The owner of a corner store stocks popsicles, gum, and candy bars. After school one day, he is swamped by influx of 15 school children. They are in and out of his store in minutes. Later, the clerk reports that ten children purchased popsicles, seven purchased gum, twelve purchased candy bars. Five purchased popsicles and gum, six purchased popsicles and candy bars, and two purchased gum and candy bars. The owner is very upset. Why?
  2. A building supplies store carries metal, wood, and plastic moldings. Metal and wood molding comes in two different colors. Plastic molding comes in six different colors.
  1. How many choices of molding does this store offer?
  2. If each kind and each color of molding comes in four different lengths, how many choices does the consumer have in the purchase of one piece of molding?
  1. Thirty buses are to be used to transport 2000 refugees from Gander to St. John’s, Newfoundland. Each bus has 80 seats. Assume one seat per passenger.
  1. Prove that one of the buses will carry at least 67 passengers.
  2. Prove that one of the buses will have at least 14 empty seats.

Deadline: 07/17/07 (at the beginning of class)

  1. Determine which characteristics of an algorithm the following procedures have and which they lack.
  1. procedure divide(n: positive integer)
  2. while n ≥ 0
  3. begin
  4. m = 1/n
  5. n = n – 1
  1. procedure chose(a, b: integers)
  2. x = either a or b
  1. Describe an algorithm which given n real numbers, a1, a2… an outputs the number of ai, which lie in the range 85-90, inclusive.
  1. Solve the polynomial f(x) and each value of x using Horner’s algorithm.
  1. f(n) = 3x2 + 1 ; x = 5
  2. f(n) = 2x3 – 4x2 – 7; x = 3
  1. To establish a big-Oh relationship find the witnesses c and k such that |f(x)| ≤ c|g(x)| when ever x > k. Determine whether each of these functions is O(x).
  1. f(x) = 5x + 3
  2. f(x) = éx/2ù
  1. Determine whether each of these functions is O(x2).
  1. f(x) = 17x + 11
  2. f(x) = x2 + 1000
  3. f(x) = ë x û é x ù
  1. Use the definition of big-Oh given in class to show that f = O(g) in each of the following cases of functions f, g: N → R
  2. f(n) = 2n2 + 3n + 1, g(n) = n2 + 1

Deadline: before or by 07/31/07 at the beginning of the Final Test

  1. Draw graph models stating the type of graph used, to represent airline routines where every day there are four flights from Boston to Newark, two flights from Newark to Boston, three flights from Newark to Miami, two flights from Miami to Newark, one flight from Newark to Detroit, two flights from Detroit to Washington, two flights Washington to Newark, and one flight from Washington to Miami, with
  1. an edge between vertices representing cities for each flight that operates between them (in either direction).
  2. an edge from a vertex representing a city where a flight start to the vertex representing the city where it ends.
  1. Determine whether the graph shown is a simple graph, a multigraph (and not a simple graph), a pseudograph (and not a multigraph), a directed graph, or a directed multigraph (and not a directed graph).
  1. The intersection graph of a collection of sets A1, a2, …, An is the graph that has a vertex for each of these sets and has an edge connecting the vertices representing two sets if these sets have a nonempty intersection. Construct the intersection graph of these collections of sets.
  1. A1 = {x| x < 0}, A2 = {x| -1 < x < 0}, A3 = {x| 0 < x < 1}, A4={x | -1 < x < 1}, A5= {x | x > -1}, A6 = R
  1. Find the number of vertices, the number of edges, and the degree of each vertex in the given undirected graph. Identify all isolated vertices. If the graph is directed multigraph find the in-degree and out-degree of each vertex.
  1. Represent the adjacency matrix of the following graphs
  2. Determine whether the given pair of graph is isomorphic
  1. Does each of these lists of vertices form a path in the following graph? Which paths are simple? Which are circuits? What are the lengths of those that are path?
  2. a, e, b, c, b
  3. e, b, a, d, b, e
  1. Determine whether the given graph has an Euler circuit. Construct such a circuit when one exits. If no Euler circuit exists, determine whether the graph has an Euler path and construct such a path if one exists.
  1. Find the length of a shortest path between a and z in the given weighted graph.