IST 230, Fall 2000

Exam I, In-class Part (60 points)

Name

Instruction: Most of the following problems require only short answers. No elaborate supporting work is required.

Part 1 Basic Math (42 points)

Problem 1

Problem 2

Problem 3

Problem 4

Problem 5

Problem 6

Problem 7

Problem 8

Part 2 Applications (18 points)

Problem 9

Problem 10

Problem 11

Problem 12

Problem 13

Problem 14

Part 3 Extra Credit (5 points)

Problem 15

Problem16

Total

Part 1 Basic Math

  1. Given two sets and .

a)Find .

b)Find .

c)What is the set called?

d)What is ?

e)What is the set called?

f)What is ?

g)How many elements are there in the power set P(Y)?

h)How many 2-element subsets of Y are there?

  1. (0, 1, 1, 0, 1, 1) and (0, 1, 0, 1, 1, 0) are two binary vectors of length 6.

a)Which two subsets of do the vectors represent?

b)Calculate the sum of these two vectors using the binary addition.

  1. Give the edge list of the following directed graph. List the edges in lexicographic order.
  1. If a degree sequence of a graph is (1, 1, 1, 2, 2, 3, 4), what does the “Handshake Lemma” tell you about this graph?
  1. If a graph has the degree sequence (1, 0, 2, 1), is it connected?
  1. Draw an unlabeled tree with the degree sequence (1, 1, 1, 1, 3, 3).
  1. According to Cayley’s Theorem, how many labeled 5-node trees are there?
  1. . List all elements of the relation in lexicographic order.

Part 2 Applications

  1. Binary [7,4] Hamming codes are generated with the aid of a three-circle Venn diagram.

a)Draw the Venn diagram, label each region by number 1, 2, …, 7, respectively.

b)Encode the binary string 0110.

c)Decode 1011101. [If there is an error in the code, correct it!]

  1. The CD technology uses Eight-to-Fourteen Modulation to translate bytes into codewords. Codes burnt on CDs are binary strings having at least two zeros between any two ones. It also cannot have more than ten consecutive zeros.

a)Give one example of such a fourteen-bit codeword.

b)Let stands for the number of k-bits strings satisfying the requirement that there are at least two zeros between and two ones. This is a Fibonacci number-like sequence. For , .

, , , , , ,

Find

  1. In the discussion of public key encryption, what mathematical concepts are involved? Circle two of the following concepts.

Binary stringsFibonacci numbers

Large prime numbersModular arithmetic

PermutationsBinomial coefficients

  1. The mesh topology used in networks is based on which type of graphs?
  1. The star topology used in networks is based on which type of graphs?
  1. The unit used in multi-dimensional database is called a “cell.” Which of the following concepts are related to a cell? Circle two answers.

, , , , , , , 8-cube, 64-cube

Part 3 Extra Credit

  1. A Hamiltonian cycle of the 3-cube is marked as follows. Following the path starting at the node labeled 000, write up a non-standard Gray code.

111

110101011

100010001

000

  1. You have to take some socks out of a completely dark room. There are a dozen pairs of socks: Six pairs are white and six pairs are black. You can not tell which sock is which kind when you are in the room. You can take out the room as many socks as you want, as long as there is at least a pair of matching socks. What is the least number of socks you need to take out of the room? Answer and explain. [Hint: Use pigeon hole principle.]