1	The table below tells the time needed for a number of tasks and which tasks precede them. Make a PERT diagram, and determine the project time and critical path.

Task	Time	Preceding Tasks

______________________________

A	3	NONE

B	5	NONE

C	2	A

D	4	A, B

E	6	A, B

F	6	C, D, E

G	3	D, E

H	3	F, G

I	2	F, G

______________________________

2	Calculate:

a.	8!/5!

b.	9!/(3! 6!)

3	Let A = {1, 2}, B = {2, 3, 4}, C = {2}, D = {x: x is an odd positive integer}, and E = {3, 4}. Are each of the following true or false?

a.	C ( A

b.	B ( D

c.	|B| = 3

d.	( ( C

4	In Cincinnati, chili consists of spaghetti topped by any (or none) of meat sauce, cheese, chopped onions, and beans. In how many ways can chili be ordered?

5	For each of the following expressions, state whether or not it is a polynomial in x, and if so give its degree.

a.	2x + 3x1/2 + 4

b.	2x + 3x

6	Let A = {1, 2, 3, 4}, B = {1, 4, 5}, C = {3, 5, 6}, and the universal set U = {1, 2, 3, 4, 5, 6}.

a.	Determine the resulting set:

b.	Determine the resulting set:

c.	Draw a Venn diagram depicting the set:

7	Determine which of the reflexive, symmetric, and transitive properties are satisfied by the given relation R defined on set S, and state whether R is an equivalence relation on S.

a.	S = {1,2,3,4,5,6,7,8} and x R y means that x - y is odd

b.	S = {1,2,3,4,5,6,7,8} and x R y means that (4 - x( = (4 - y(

8	Perform the indicated operation in Zm. Write your answer in the form [r] with 0 ( r ( m

a.	[43] + [31] in Z22

b.	[11]8 in Z5

9	A hospital heart monitoring device uses two feet of paper per hour. If it is attached to a patient at 8 a.m. with a supply of paper 150 feet long, at what hour of the day will the device run out of paper?

10	For the following, determine a Hasse diagram for the partial order R on set S.

S = {1, 2, 3, 4} and R = {(1, 1), (2, 2), (3, 3), (4, 4), (2, 4), (3, 1)}

11	Identify the minimal and maximal elements of S with respect to the given partial order R.

S = the nonempty subsets of {1, 2, 3} and A R B if B ( A

12	Find the value of f(a).

a.

b.

c.

d.

13	In the following exercise Z denotes the set of integers. Determine if each function g is one-to-one, onto, or both.

a.

b.

14	Suppose that a number xn is computed recursively by

x1 = 2 and xn = 2xn-1 + 3 for n ( 2. Compute x1 through x5.

15	Prove the given statement by mathematical induction.

16	Evaluate the numbers.

a.	C(8, 3)

b.	C(13, 9)

c.	C(n, 1)

d.	P(n, r) / C(n, r)

17	What is a graph?

18	List the set of vertices and the set of edges for the graph below.

19	What is a connected graph? Give two examples.

20	What is a weighted graph? What are its applications?

21	List the vertices and directed edges for the directed graph below:

22	Construct the labeled directed graph for the adjacency matrix:

23	Find an Euler path for the following graph:

24	What is a tree? Is a PERT diagram always a tree? Explain.

25	For each of the following graphs, determine if each is a tree and explain your answer.

a.	b.

26	What is a spanning tree? Give an example.

27	Explain the breadth-first search spanning tree algorithm, and then apply it to the following graph:

28	Use Prim’s algorithm to find the minimal spanning tree for the graph in the previous problem.

29	How do you know if a graph is a binary tree?

30	Explain the preorder traversal algorithm.

31	Explain the binary search tree search algorithm.

32	Evaluate the following:

a.	C(7, 2)

b.	C(12, 7)

c.	(x + y)7

d.	the coefficient of x7y2 in the expansion of (2x - y)9

33	How many words must be chosen in order to assure that at least two begin with the same letter?

34	How many different 4-digit numbers can be formed using 5, 6, 7, 8 without repetition?

35	How many distributions of 14 different books are possible if Carlos is to receive 5 books, Jamie, 4 books and Robert, 2 books?

36	Define probability.

37	Determine the probability of the following:

a.	If three dice are rolled, that all will be odd

b.	If two coins are flipped, that they both will land the same

38	In a particular dormitory there are 350 college freshmen. Of these, 312 are taking an English course and 108 are taking a mathematics course. If 95 of these freshman are taking courses in both English and mathematics, how many are taking neither?

39	In the following sequences determine s5 if s0, s1, ... sn, ... is a sequence satisfying the given recurrence relation and initial condition.

a.	sn= -sn-1 - n2 for n >= 1, s0 = 3

b.	sn = 5sn-1 - 3sn-2 for n >= 2, s0 = -1, s1 = -2

40	An investor begins to save in 1990 with $500. Each year, the savings increases 10% over the year before, and then investor contributes another $100. Write a recurrence relation and initial conditions on the sn, the amount of savings n years after 1990. Use this relation to determine the amount saved by 1994.

41	Explain the method of iteration.

42	Use the method of iteration to find a formula expressing sn as a function of n for the given recurrence relation:

sn= -sn-1 + 10, s0 = -4

43	What are finite state machines? Is a computer a finite state machine? Explain.

44	Draw a transition diagram for the finite state machine with the given state table:

A	B	C
0	B	C	A
1	A	C	B

45	Draw a transition diagram for the finite state machine with the given state table below, with A being both the initial and accepting state.

A	B
x	B	A
y	A	A
z	B	B

46	Give the state table for the finite state machine with the given transition diagram:

47	In what state would the machine in the previous question end if it started in the initial state and was given the input string abaabb?

48	Draw the transition diagram for the finite state machine with output whose state and output tables is:

A	B	A	B
0	A	A	z	X
1	B	B	z	Y

A

E

F

B

C

D

c

b

d

a

g

e

f

ASSIGNMENT 1

V. Anton Spraul

2007-02-01

Eric Abt

ACCIS