First NameLast NameQuiz #02CSC 172 (Data Structures & Algorithms)Spring 2019Feb 3 - 9Time: 20 minutesProblem 1 (2 pts)Write all the subsets of the following sets:1. {3}Ans: ∅, {3}2. {6, 11}Ans: ∅, {6}, {11}, {6, 11}3. {2, 5, 9}Ans: ∅, {2}, {5}, {9}, {2, 5}, {2, 9}, {5, 9}, {2, 5, 9}4. {6, 8, 10, 11}Ans: ∅, {6}, {8}, {10}, {11}, {6, 8}, {6, 10}, {6, 11}, {8, 10}, {8,11}, {10, 11}, {6, 8, 10}, {6, 8, 11}, {6, 10, 11}, {8, 10, 11}, {6,8, 10, 11}Problem 2 (2 pts)Given the sets A={2, 3, 7, 12}, B = {7, 8, 10, 12} and C = {a, b} writethe result of the following set operations:1. A ∩ B = {7, 12}2. A − B = {2, 3}3. A ∪ B = {2, 3, 7, 8, 10, 12}4. A × C = {(2, a), (2, b), (3, a), (3, b), (7, a), (7, b), (12, a), (12, b)}Page 1 of 3Problem 3 (3 pts)For the following program fragment express the order running time asa function of n.sum = 0;for( i = 0; i < n; i++ )for( j = 0; j < n * n; j++ )sum++;Ans: The order of the running time is cubic in nProblem 4 (3 pts)Prove by mathematical induction that the following equality holds forall n ∈ N (all natural numbers)nXk=02k = n2+ nProof1. P (0) is0Xk=02k = 02+ 0and it holds trivially.2. (I.H.) Assume P (n) holds, sonXk=02k = n2+ nP (n + 1) isn+1Xk=02k =nXk=02k + 2(n + 1)Page 2 of 3Because of I.H. we getn+1Xk=02k = n2+ n + 2(n + 1) = (n + 1)2+ (n + 1)and this completes our proof.Page 3 of