EECE 230 Final, Fall 2013

EECE 230 Introduction to Programming, Sections 7,8,10 Final Exam Feb 4, 2009 • The duration of this exam is 3 hours. • It consists of 4 problems. • The exam is open book. You can use also all the material on Moodle: lecture notes, programming assignments, and solutions, etc. You are NOT allowed to use the web (imail included). You are not allowed to use USB’s or files previously stored in your account. • If you violate the above rules or if you communicate with a person other than the exam proc- tors during the exam, you will immediately get zero and you will be referred to the appropriate disciplinary committee. • Active cell phones and any other unauthorized electronic devices are absolutely not allowed in the exam rooms. They should be turned off and put away. • Plan your time wisely. Do not spend too much time on any one problem. Read through all of them first and attack them in the order that allows you to make the most progress. • Submit your solutions each part in a separate file as indicated in the booklet. Include your name and ID number in each file. Submit the files online in a single zip file called yourLastName.yourFirstName.zip. • Good luck! 1 Problem 1 (25 points). Series Write a program, which given a nonnegative integer n and a real number x, prints the value of the series: fn(x) def = 1 − x 2 + x2 3 − x3 4 + . . . + (−1)n xn n + 1. Test your program on the following examples: x n fn(x) any 0 1 0.0 any (≥ 0) 1 2.0 3 -0.666 3.3 6 136.984 You are not allowed to use the cmath library and in particular you are not allowed to use the pow function. Submit your code in a file called Prob1.cpp. Include your name and ID number in the file. Problem 2 (35 points). Subset a) (25 points) Implement the function bool subset(int *A, int m,int *B, int n) which, given a length-m array A of integers and a length-n array B of integers, checks if each element of B is present in A (not necessarily with the same number of number of occurrences or in the same order). For instance, if A = ⟨2, 8, 3, 7, 5, 5⟩ and B = ⟨7, 2, 3, 7, 5, 2, 5, 2⟩, then each element of B is present in A. This is not true however for A = ⟨2, 8, 3, 7, 5, 5⟩ and B = ⟨7, 2, 3, 7, 6, 2, 5, 2⟩ since 6 is not an element of A. In this part you are asked to implement the function using two nested loops. b) (10 points) Write a more efficient implementation of the function in part (a). Instead of using two nested loops, use randomized quick sort [Problem 1 of PA 8] and binary search (you can download the code of those functions from moodle). Call your function fastSubset. Write a program to test your functions. Submit your code in a file called Prob2.cpp. Include your name and ID number in the file. Problem 3 (10 points + 5 bonus points). Recursive partition enumerator If n is a positive integer, a partition of n is an sequence of strictly positive integers ⟨a1, a2, . . . , ak⟩ sorted in non increasing order whose sum is equal to n, i.e., a1 ≥ a2 ≥ . . . ≥ ak ≥ 1 and a1+a2+. . .+ak = n. For instance ⟨3, 2, 1, 1⟩ is a partition of 7. Another partition of 7 is ⟨3, 3, 1⟩. Write a recursive function, which given an positive integer n, prints all partitions of n. Examples: • For n = 1, the function should print 1 2 • For n = 2, the function should print 2 1 1 • For n = 3, the function should print 3 2 1 1 1 1 • For n = 4, the function should print 4 3 1 2 2 2 1 1 1 1 1 1 • For n = 7, the function should print 7 6 1 5 2 5 1 1 4 3 4 2 1 4 1 1 1 3 3 1 3 2 2 3 2 1 1 3 1 1 1 1 2 2 2 1 2 2 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 Note that in addition to the integer n, the recursive function needs other input parameters. Look at the string enumerator problem in PA 8 (Part (a) of Problem 3) Your function should not take much more time than the output size. That is you are expected to avoid recursive branches which do not lead to valid partitions. Submit your code in a file called Prob3.cpp. Include your name and ID number in the file. Problem 4 (30 points). Classes: 2 × 2 matrices In this problem we are interested in 2 × 2 matrices with real entries. A 2 × 2 matrix � a b c d � is specified by the four real numbers a, b, c, d. If � a b c d � and � e f g h � are 2 × 2 matrices, their sum and product are define as follows � a b c d � + � e f g h � def = � a + e b + f c + g d + h � � a b c d � ∗ � e f g h � def = � ae + bg af + bh ce + dg cf + dh � . 3 If M = � a b c d � is a 2 × 2 matrix and v = � x y � is a 2 × 1 vector, the product of M and v is the 2 × 1 vector given by � a b c d � � x y � def = � ax + by cx + dy � . Finally the determinant of a matrix is the real number given by det � a b c d � def = ad − bc. Design a class matrix22 that defines a 2 × 2 matrix as an Abstract Data Type. Include the member functions: • a constructor which takes the four defining entries of the matrix as an input parameters • default constructor which sets all the four entries of the matrix to zeros. • print function which prints the matrix in the following format: a b c d • overload the binary operator + as a member function to perform the addition of two matrices as as defined above. • overload the binary operator ∗ as a member function to perform the multiplication of two matrices as as defined above. • overload the binary operator ∗ as a member function to perform the multiplication of a matrix and a vector as defined above. Use the simple vector class vector2 given in the test program below. • determinant member function det. Note the class matrix22 is much simpler than the general case of m × n matrices we did in class (the matrix class). You don’t need the implementation of that class in this problem. You are asked to implement matrix22 from scratch. Test your class using the following program: class vector2 { public: double x; double y; vector2() {x = 0;y=0;} vector2(double xValue,double yValue) {x = xValue;y=yValue;} void print() {cout<<endl<<" "<<x<<endl<<" "<<y<<endl;} }; // matrix22 class definition .... int main() { matrix22 M(1,2,3,4), N; cout<< "M:";M.print(); cout<< "N:";N.print(); cout<<"det(M) ="<<M.det(); cout<<endl; 4 N = M+M; cout<<"N:";N.print(); M = M*N; cout<<"M:";M.print(); vector2 v(1,2); cout<< "v:";v.print(); vector2 w = M*v; cout<<"w:";w.print(); cout<<endl; return 0; } // implementations of the functions of matrix22 .... You should get M: 1 2 3 4 N: 0 0 0 0 det(M) =-2 N: 2 4 6 8 M: 14 20 30 44 v: 1 2 w: 54 118 Submit your code in a file called Prob4.cpp. Include your name and ID number in the file. 5 EECE 230 Introduction to Programming, Sections 3 and 4 Final Exam January 26, 2010 • The duration of this exam is 3 hours. • It consists of 4 problems. • The exam is open book. You can use also all the material on Moodle: lecture notes, programming assignments, and solutions, etc. You are NOT allowed to use the web (imail included). You are not allowed to use USB’s or files previously stored in your account. • If you violate the above rules or if you communicate with a person other than the exam proc- tors during the exam, you will immediately get zero and you will be referred to the appropriate disciplinary committee. • Active cell phones and any other unauthorized electronic devices are absolutely not allowed in the exam rooms. They should be turned off and put away. • Plan your time wisely. Do not spend too much time on any one problem. Read through all of them first and attack them in the order that allows you to make the most progress. • Submit your solutions each part in a separate file as indicated in the booklet. Include your name and ID number in each file. Submit the files online in a single zip file called yourLastName.yourFirstName.zip. • Good luck! 1 Problem 1 (20 points). Print even followed by odd Write a program which, given a list of integers whose end is indicated by the sentinel −999, prints the even numbers in the input list followed by the odd numbers in the list. For example, if the input list is 1 10 2 3 -5 4 8 15 -3 -2 12 11 -999 then the program output should be Even numbers: 10 2 4 8 -2 12 Odd numbers: 1 3 -5 15 -3 11 Submit your code in a file called Prob1.cpp. Include your name and ID number in the file. Problem 2 (25 points). Product Write a function product which, given an array A[0 . . . n − 1] of integers, checks whether or not the array A contains two integers whose product is also present in the array A. The prototype of product is bool product(int A[], int n); The function returns TRUE if there exist induces i, j, and k, where 0 ≤ i, j, k ≤ n − 1, such that A[i] × A[j] = A[k]. Otherwise, the function returns FALSE. Examples: • If A = ⟨7, 10, 11, 2, −16, 5, 6, 13⟩, then the answer is TRUE since 2 × 5 = 10 is present in A. • If A = ⟨3, 2, 5, 8⟩, then the answer is FALSE since none of the following products are present in A: 3 × 3 = 9, 3 × 2 = 6, 3 × 5 = 15, 3 × 8 = 24, 2 × 2 = 4, 2 × 5 = 10, 2 × 8 = 16, 5 × 5 = 25, 5 × 8 = 40, 8 × 8 = 64. Write a program to test your function. A correct solution of this problem is worth at least 15 points. Faster solutions are worth more points. (Hint: The fast implementation uses binary search). Submit your code in a file called Prob2.cpp. Include your name and ID number in the file. Problem 3 (15 points). Subset Sum revisited Recall the Subset Sum problem in Quiz 1 [available on moodle]. In this problem you are asked to generalize from 3 numbers (8 in Part (b)) to an arbitrary number n of numbers specified by the user. That is, write a program which prompts the user to enter an integer n, a list of n numbers, and a target number t. You program is supposed to check whether or not the input list of numbers contains a subset whose sum is equal to the target number t. If such a subset exists, your are not asked to print it. Your program is only supposed to print “Subset found”. Otherwise, it should print “Subset not found”. That is, we are after a YES/NO answer. The solution of Part (b) in Quiz I [available on moodle] uses 8 nested loops. It cannot be generalized to solve the general n case since n is specified by the user and it is not possible to use n nested loops when n is not a constant. You are asked to solve this problem recursively. In fact, you are NOT allowed to use for or while loops in your recursive function. The only loop you need in the program is the loop which stores the input list of number in an array. You don’t have to worry about speed in this problem. Any correct solution is worth 15 points. Submit your code in a file called Prob3.cpp. Include your name and ID number in the file. 2 Problem 4 (40 points). Classes: quadratic polynomials In this problem, we are interested in quadratic polynomials, i.e., polynomials of degree 2. (You do NOT need the code Part (b) of Problem 3 of Programming Assignment 10, which deals with polynomials of arbitrary degree n and uses arrays to implement them. The degree-2 case is much simpler. You don’t need arrays in this problem and you are not allowed to use them (hence you cannot use the code of the solution of Part (b) of Problem 3 of PA 10)). A quadratic polynomial p(x) on the variable x is of the form p(x) = ax2 + bx + c, where a, b, c are reals numbers. Thus p is uniquely specified by the three parameters a, b, and c. Design a class quadraticPolynomial that defines a quadratic polynomial as an Abstract Data Type. Include the member functions: • a constructor which takes the values of a, b, and c as input parameters. • default constructor which sets a = b = c = 0. • evaluate function which given a real number v, returns the value of the polynomial on x = v, i.e., av2 + bv + c. • print function which prints the parameters of the polynomial in the following format: a*x^2 + b*x + c • realRoots function which finds the real roots of the polynomial. This function returns an integers and it takes two reference parameters x1 and x2 as explained below. Recall that the roots of p(x) = ax2+bx+c are the solutions of the equation p(x) = 0. This equation has real solutions if and only if Δ = b2 − 4ac ≥ 0. If a ̸= 0 and Δ ≥ 0, the roots are given by −b± √ Δ 2a . In this cases the function realRoots returns 2 and it sets the reference parameters x1 and x2 to the values of the two roots (we set them to the same value if Δ = 0). If a ̸= 0 and Δ < 0, realRoots returns 0. If a = 0 and b ̸= 0, the polynomial has only one root −c/b. In this cases the realRoots returns 1 and it sets the reference parameter x1 to the single root of the polynomial. If both a and b are zero, then the equation has either no solution if c ̸= 0 or infinitely many solutions if c = 0. In the first case realRoots returns 0, and in the second it returns 999. • isSquare function which returns TRUE if the polynomial is the square of a degree-1 polynomial and FALSE otherwise. • derivative function which returns the derivative of the polynomial, i.e., the polynomial given by 2ax + b = 0x2 + 2ax + b. • overload the binary operator + as a member function to perform the addition + of two polynomials, which is defined as follows. If p(x) = ax2 + bx + c and q(x) = a′x2 + b′x + c′, then p(x) + q(x) is the polynomial given by (a + a′)x2 + (b + b′)x + (c + c′). Test your class using the following program: int main() { quadraticPolynomial p(1,5,3),q(1,2,1), r; cout<<"p: ";p.print(); cout<<"q: ";q.print(); cout<<"r: ";r.print(); cout<<"p(2)="<<p.evaluate(2)<<endl; r = p+q; cout<<"p+q: ";r.print(); r = p.derivative(); 3 cout<<"derivative r of p: ";r.print(); double x1,x2; if(p.realRoots(x1,x2)==2) cout<<"roots of p : "<<x1<<","<<x2<<endl; if(q.realRoots(x1,x2)==2) cout<<"roots of q : "<<x1<<","<<x2<<endl; if(r.realRoots(x1,x2)==1) cout<<"root of r : "<<x1<<endl; if(q.isSquare()) cout<<"q is a square"; else cout<<"q is not a square"; cout<<endl; if(p.isSquare()) cout<<"p is a square"; else cout<<"p is not a square"; cout<<endl; return 0; } You should get p: 1*x^2 + 5*x + 3 q: 1*x^2 + 2*x + 1 r: 0*x^2 + 0*x + 0 p(2)=17 p+q: 2*x^2 + 7*x + 4 derivative r of p: 0*x^2 + 2*x + 5 roots of p : -0.697224,-4.30278 roots of q : -1,-1 root of r : -2.5 q is a square p is not a square Submit your code in a file called Prob4.cpp. Include your name and ID number in the file. 4 EECE 230 Introduction to Programming, Sections 3 and 4 Final Exam January 20, 2011 • The duration of this exam is 3 hours. • It consists of 4 problems. • The exam is open book. You can use also all the material on Moodle: lecture notes, programming assignments, and solutions, etc. You are NOT allowed to use the web (imail included). You are not allowed to use USB’s or files previously stored in your account. • If you violate the above rules or if you communicate with a person other than the exam proc- tors during the exam, you will immediately get zero and you will be referred to the appropriate disciplinary committee. • Active cell phones and any other unauthorized electronic devices are absolutely not allowed in the exam rooms. They should be turned off and put away. • Plan your time wisely. Do not spend too much time on any one problem. Read through all of them first and attack them in the order that allows you to make the most progress. • Submit your solutions each part in a separate file as indicated in the booklet. Include your name and ID number in each file. Submit the files online in a single zip file called yourLastName.yourFirstName.zip. • Good luck! 1 Problem 1 (20 points). Consecutive pair sum Write a program which takes as input: 1) a target number t, and 2) a list of integers whose end is indicated by the sentinel −999. Your program is supposed to find the number of consecutive pairs of numbers whose sum is equal to the target t. That is, if the list is a1, a2, . . . , am, −999, then your program should print the number of i’s such that ai + ai+1 = t. For example, if the target is 2 and the input list is 1 1 3 4 10 -8 10 100 15 -98 -999 then the program output should be 3 since 1 + 1 = 2, 10 − 8 = 2, and −8 + 10 = 2. Note that 100 − 98 does not count since 100 and −98 are not consecutive. Submit your code in a file called Prob1.cpp. Include your name and ID number in the file. Problem 2 (25 points). Equilateral triangles Recall the structure point we did in class: struct point { double x; double y; }; a) (5 points) Write the function dist which takes as input two points p and q and returns the Euclidean distance between p and q. Note that if (x1, y1) and (x2, y2) are two points, the Euclidean distance between them is given by � (x1 − x2)2 + (y1 − y2)2. b) (5 points) Three points p, q, and r determine a triangle. We call the triangle equilateral if dist(p, q) = dist(p, r) = dist(q, r). Write a boolean function isEquilateral which takes as input three points p, q, and r and checks whether or not the corresponding triangle is equilateral. c) (15 points) Write a function, which given a array of points A[0 . . . n − 1] and its size n, checks whether or not the array contains three distinct points which form an equilateral triangle. That is, your function should check whether or not there are indices i, j, and k such that the points A[i], A[j], and A[k] form an equilateral triangle. Call your function containsEquilateral. Write a program to test your functions. Submit your code in a file called Prob2.cpp. Include your name and ID number in the file. Problem 3 (25 points). Circle class Recall the structure point we did in class: struct point { double x; double y; }; 2 Using the structure point, design the class circle that defines a circle as an Abstract Data Type. In addition to the member variable center which is of type point, include the member variable radius (which is a real number). Make both center and radius public. Include the following functions: • default constructor • non-default constructor which takes 3 double-values: the radius and the x and y coordinates of center • print member function which displays the radius and the x and y coordinates of center • area member function which returns the area of the circle (i.e., π ∗ radius2) • translate member function which takes as input argument a point p and translates the center of the circle by p • contains member function which takes as input argument a point p and checks whether or not p is inside the circle Write a program to test all the above member functions. Submit your code in a file called Prob3.cpp. Include your name and ID number in the file. Problem 4 (30 points +10 bonus points). Longest Common Subsequence (LCS) problem A subsequence of a string S[0, . . . , N − 1] (with proper null termination, i.e., S[N] =′ \0′) is any sequence S[i1], S[i2], . . . , S[it], where 0 ≤ i1 < i2 < . . . < it ≤ N − 1. Example: “art” is a subsequence of “algorithms”. However “rat” is not subsequence of “algorithms” because we have to respect the order of characters. Thus, unlike substrings, subsequences need not consist of consecutive characters The Longest Common Subsequence (LCS) problem: Given two strings X[0 . . .m−1] and Y [0 . . . n−1], find the length of the longest subsequence common to both. The length of the LCS is a measure of similarity between X and Y . It is large for “similar” strings. This has application in comparing files or DNAs. Example: X: A B C B D A B Y: B D C A B A We have BCBA is a LCS of X and Y , BDA is common subsequence but not a LCS (BCBA is longer), BCAB is another LCS. The length of the longest common subsequence is 4. a) (20 points)(*) Write a function for the LCS problem: int LCS(char *X,char *Y); Given X and Y , LCS is supposed to return the length of the LCS of X and Y . Any correct function is worth full grade. Efficiency does not matter in this part. (Hint: recursion). b) (10 points+10 bonus points)(**) Write an efficient function for the LCS problem: int fastLCS(char *X,char *Y); The running time of your function should not be exponential in the length of X or Y . (Hint: Modify (a) ... avoid solving the same subproblem more than once). Write a program to test your functions. Submit your code in a file called Prob4.cpp. Include your name and ID number in the file. 3 EECE 230 Introduction to Programming, Sections 3 and 4 Final Exam January 17, 2012 • The duration of this exam is 3 hours. • It consists of 4 problems. • The exam is open moodle. You can use all the material on Moodle: lecture notes, programming assignments, and solutions, etc. You are NOT allowed to use the web (imail included). You are not allowed to use USB’s or files previously stored in your account. • If you violate the above rules or if you communicate with a person other than the exam proctors during the exam, you will immediately get zero and you will be referred to a disciplinary committee. • Active cell phones and any other unauthorized electronic devices are absolutely not allowed in the exam rooms. They should be turned off and put away. • Plan your time wisely. Do not spend too much time on any one problem. Read through all of them first and attack them in the order that allows you to make the most progress. • Submit your solutions each part in a separate file as indicated in the booklet. Include your name and ID number in each file. Submit the files online in a single zip file called abcMN.zip, where abcMN is your AUB user i.d., e.g., abc01.zip. • Good luck! 1 Problem 1 (30 points + 10 bonus points). Parenthesis check a) (12 points) Check if the numbers of left and right parenthesis are equal. Write a function bool parenthesisA(char *s) which given a C-string s checks if it has the same number of left “(” and right “)” parenthesis. Examples: – Each of the following strings have the same number of of left and right parenthesis: “a)(b”, “a(x)b”, “a(x)b)(” – None of the following strings have the same number of of left and right parenthesis: “a))b”, “a(x(b”, “a(x)b))” b) (13 points) Check if they march. Write a function bool parenthesisB(char *s) which given a C-string s checks if the “(” left and right “)” parenthesis match. Note that if there is match then the number of left parenthesis must be equal to the number of right parenthesis but the converse is not true. Examples: – The parenthesis in each of the following strings match: “a(x)b”, “a((x))(b)”, “((()()))()”. – The parenthesis in each of the following strings do not match: “a)(b”, “a(x)b)(”, “a))b”. c) (5 points + 10 bonus points) Parenthesis and braces. Write a function bool parenthesisAndBraces(char *s) which given a C-string s checks if the left and right parenthesis and the left and right braces match. Examples: – We have a match in each of the following strings: “a(aa)aa”, “aa(b(cd))e[ab]”, “([aa(b)c[(aaaaa)]r(d)])” – We don’t have a match in any of the following strings:” “a([b)]”, or “((aab)[d”, “e[()(])”. Write a program to test your functions. Use the above examples. Submit this problem in a file called Prob1.cpp. Include your name and ID number in the file. Problem 2 (20 points). Check if an integer appears three times Write a program which takes as input a list of integers whose end is indicated by the sentinel −999. Your program is supposed to check whether or not the list contains a number which appears at least three times. Examples: • If the input list is 1 1 7 4 10 -8 7 100 7 7 -98 -999 then the answer is YES since the number 7 appears 4 times. 2 • If the input list is 1 1 9 4 10 -8 7 100 7 9 -98 -999 then the answer is NO. Your program is supposed to give a YES/NO answer only. Faster programs are worth more points. Any correct solution of the problem is worth 15/20 points. Submit your code in a file called Prob2.cpp. Include your name and ID number in the file. Problem 3 (35 points + 10 bonus points). Classes: interval class a) (30 points) If a and b are real numbers, the interval [a, b] is the set of real numbers x such that a ≤ x ≤ b. We call a the lower bound of the interval [a, b] and b its upper bound. Note that [a, b] is nonempty only when a ≤ b. If a > b, the interval [a, b] is called the empty interval. Design a class interval that defines a interval as an Abstract Data Type (the member variables are a and b). Include the member functions: • Constructors: default (initialize to an empty-interval), and non-default. • The print member function. This function is supposed to print [a, b] if the interval is nonempty and “empty interval” if it is empty. • The membership function contains, which given a real number x, checks if x is inside the interval. • The function numberOfElements, which given an array A of real numbers and its size, returns the the number of real numbers in A inside the interval. Your are required to implement numberOfElements using the function contains. • The function intersectWith which takes as input argument another interval by reference. It is supposed to return an interval equal to the intersection of the two intervals. For instance, if I = [1.5, 3], J = [2.1, 4], and K is a third interval. Then K = I.intersectWith(J) is supposed to to set K to [2.1, 3]. Write a program to test your class. You are asked to test all the member functions of the class. b) (5 points + 10 bonus points) Write the (non-member) function void findUnion(interval A[], int n, interval B[], int & m) The function findUnion is supposed to to store in the array B a sequence of non-overlapping intervals whose union is equal to the union of the intervals in A. It is supposed to set m to the number of the intervals in B. Assume that memory is allocated to B before calling the function. For instance, say that A consists of the intervals [3.5, 4.5], [19, 22.3], [6, 9], [1, 4], [5.5, 7.6], and [2, 3]. Then the function findUnion is supposed to store [1, 4.5], [5.5, 9], [19, 22.3] in B and set m to 3. Test your function on the above example. Submit your solution of this problem in a file called Prob3.cpp. Include your name and ID in number the file. Problem 4 (15 points). Recursive Sequential Search Recall the search problem: 3 Searching problem. Given an array A[0 . . . n − 1] of integers and an integer x , check if x is an element of A and if so find its index. More specifically, if x is an element of A return an index i such that A[i] = x (any such i is ok), else return −1. We solved this problem in class using the sequential search algorithm. Your asked in this problem to write a recursive version of the sequential search algorithm. Call it recursiveSequentialSearch. The use of for or while loops is strictly prohibited in the recursiveSequentialearch. Note that recursive binary search is not applicable to this problem since A is not necessarily sorted. Write a program to test your function. Submit your code in a file called Prob4.cpp. Include your name and ID number in the file. 4