(5 points) (a) What is a spanning tree?

1.(10 points) Consider L= f{anbn } and the statement S=integer m. Write the statement of 7S (the negation of S). Hint:

(5 points) (b) Given an undirected, weighted graph in Figure 1, what is the minimum spanning tree (MST)?

(5 points) (c) Describe the sequence of adding edges to form the MST of the graph in Figure 1 using the greedy Kruskal's algorithm.

3.(8 points) Use the Euclidcan algorithm to find the greatest common divisor of 167,076 and 1,928,737.

4.(5 points) Five people occupy five seats. If five seats are arranged in a circle, bow many different ways can the five people select their seats?

5. (4 points) Let G = (V, E) be a graph. If V has twelve members, in which four members each has a degree of three, and the degree of each remaining member is five, how many members does E have?

6. (8 points) A class at a college consists of 19 students who sit at a circular table. The instructor wants each student to sit next to two different classmates cach day. For bow many days can they do this?

(a) T(n) = T(n-1) + 2n

(b) T(n) = 2T(n-1) +n

8. (8 points) Given a sequence of n integers A = (a1, a2,..., an), the longest increasing subsequence problem is to find a longest subsequencealk For example, (1,2,5,8) is a longest increasing subsequence of (4,1,7,5,2,5,8,4). Please use the dynamic programming technique to design an O(n2) time algorithm for solving the longest increasing subsequence problem. Please also justify your algorithm and its time complexity.