attached
UNIVERSITY OF CENTRAL FLORIDA COP 3502C – Computer Science 1 Dr. Andrew Steinberg Practice Problems for Exam 1 INSTRUCTIONS TO STUDENTS 1. The following content contains a variety of practice problems. 2. These set of practice problems is not to serve as the actual questions that will be asked exactly, but to give students an idea of types of questions related to the material. Students are solely responsible for studying all the material in the notes, quizzes, and recitations. 3. A formula page has been provided for you on next page as a reference for any formulas you may need to reference to for solving problems. Last Name: First Name: UCF ID: COP 3502C Formula Sheet This page contains formulas you could find useful during the review. 1. n∑ i=1 c = cn 2. n∑ i=1 i = n(n+ 1) 2 3. n∑ i=1 i2 = n(n+ 1)(2n+ 1) 6 4. n∑ i=1 i3 = n2(n+ 1)2 4 5. n∑ i=o xi = 1− xn+1 1− x 6. ∞∑ i=o xi = 1 1− x when |x| < 1="" 7.="" logb="" a="" −→="" bc="a" 8.="" loga="" a="" c="c" 9.="" logc="" ab="logc" a+="" logc="" b="" 10.="" logc="" a="" b="logc" a−="" logc="" b="" 11.="" logc="" a="" n="n" logc="" a="" 12.="" alog="" c="" b="blog" c="" a="" 13.="" logb="" n="logc" n="" logc="" b="" 2="" cop="" 3502c="" dynamic="" memory="" consider="" the="" following="" c="" code.="" typedef="" struct{="" int="" x;="" double="" y;="" char="" ltr;="" }record_t;="" record_t="" **="" createrecord="" ()="" {="" record_t="" **="" database="(record_t" **)="" malloc(sizeof(="" record_t="" *)="" *="" 1);="" if(database="=" null)="" return="" null;="" database="" [0]="(record_t" *)="" malloc(sizeof(record_t)="" *="" 1);="" if(database="" [0]="=" null)="" return="" null;="" printf("enter="" an="" integer:="" ");="" scanf("%d",="" database="" [0].x);="" printf("enter="" a="" double:="" ");="" scanf("%lf",="" database="" [0].y);="" printf("enter="" a="" character:="" ");="" scanf("="" %c",="" database="" [0].="" ltr);="" return="" database;="" }="" is="" there="" anything="" wrong="" with="" the="" code?="" 3="" cop="" 3502c="" algorithm="" design="" consider="" the="" following="" c="" code="" that="" performs="" a="" simple="" linear="" search.="" int="" search(int="" *="" nums="" ,="" int="" n,="" int="" i)="" {="" for="" (int="" x="0;" x="">< n;="" ++x)="" {="" if="" (arr[x]="=" i)="" return="" x;="" }="" return="" -1;="" }="" what="" is="" the="" worst="" case="" scenario?="" what="" about="" the="" best="" case="" scenario?="" order="" analysis="" arrange="" the="" following="" functions="" in="" ascending="" order="" of="" growth="" rate.="" that="" is,="" if="" function="" g(n)="" immediately="" follows="" f(n)="" in="" your="" list,="" then="" it="" should="" be="" the="" case="" that="" f(n)="O(g(n))" f1(n)="3n−" log="" n32.3="" f2(n)="√" n+="" 2nn="" f3(n)="3" n+4="" f4(n)="(" 3="" 4="" )n−9="" f5(n)="√√" n+="" 1="" 4="" cop="" 3502c="" consider="" the="" following="" code="" snippet="" in="" c.="" what="" is="" the="" overall="" running="" time="" in="" t="" (n)?="" int="" myfunction(int="" *="" arr="" ,="" n)="" {="" int="" a="2;" for(int="" i="1;" i=""><= 4;="" ++i)="" a="a" +="" 100;="" for(int="" i="1;" i="">< n;="" ++i)="" for(int="" j="1;" j="">< n="" *="" n;="" ++j)="" arr[i]="arr[i]" +="" a="" +="" j;="" int="" b="4;" for(int="" i="1;" i="">< n; ++i) b = b + arr[i]; return b * a; } 5 cop 3502c let arr1 and arr2 be two sorted arrays of the same length. design a user-defined function in c that runs in o(n) that finds two elements from arr1 and arr2 such that arr1[i]+arr2[j] = k. the parameters of the function are the two arrays, the length, and the value k. 6 cop 3502c summations write the closed form of the summation as a polynomial in n. 1. n∑ i=1 3i+ 3 2. n∑ i=1 2ni+ 8 7 cop 3502c recursion 1. write a recursive function in c called search that takes a sorted array of numbers, two indexes low and high of the array, and another integer called value. the function returns the location or value. the index returned must be between the indexes between low and high inclusive. if the value is not located between those two indexes, return -1. 8 cop 3502c 2. write a recursive user defined function definition in c called palin- dromer that has one string parameter called str and a second pa- rameter that holds an integer value called i which is the starting index of the string. the function will determine if the string in str is consid- ered a palindrome or not. if the string is a palindrome, the function returns 1. otherwise return 0. a string is said to be palindrome if it reads the same backward as forward. examples of palindrome strings, level, refer, aabaa, and abccba are a few of many examples of what is considered a palindrome. 9 cop 3502c recurrence relations solve the following recurrence using the iteration technique. t (n) = 4t (n 2 ) + n t (1) = 1 10 n;="" ++i)="" b="b" +="" arr[i];="" return="" b="" *="" a;="" }="" 5="" cop="" 3502c="" let="" arr1="" and="" arr2="" be="" two="" sorted="" arrays="" of="" the="" same="" length.="" design="" a="" user-defined="" function="" in="" c="" that="" runs="" in="" o(n)="" that="" finds="" two="" elements="" from="" arr1="" and="" arr2="" such="" that="" arr1[i]+arr2[j]="k." the="" parameters="" of="" the="" function="" are="" the="" two="" arrays,="" the="" length,="" and="" the="" value="" k.="" 6="" cop="" 3502c="" summations="" write="" the="" closed="" form="" of="" the="" summation="" as="" a="" polynomial="" in="" n.="" 1.="" n∑="" i="1" 3i+="" 3="" 2.="" n∑="" i="1" 2ni+="" 8="" 7="" cop="" 3502c="" recursion="" 1.="" write="" a="" recursive="" function="" in="" c="" called="" search="" that="" takes="" a="" sorted="" array="" of="" numbers,="" two="" indexes="" low="" and="" high="" of="" the="" array,="" and="" another="" integer="" called="" value.="" the="" function="" returns="" the="" location="" or="" value.="" the="" index="" returned="" must="" be="" between="" the="" indexes="" between="" low="" and="" high="" inclusive.="" if="" the="" value="" is="" not="" located="" between="" those="" two="" indexes,="" return="" -1.="" 8="" cop="" 3502c="" 2.="" write="" a="" recursive="" user="" defined="" function="" definition="" in="" c="" called="" palin-="" dromer="" that="" has="" one="" string="" parameter="" called="" str="" and="" a="" second="" pa-="" rameter="" that="" holds="" an="" integer="" value="" called="" i="" which="" is="" the="" starting="" index="" of="" the="" string.="" the="" function="" will="" determine="" if="" the="" string="" in="" str="" is="" consid-="" ered="" a="" palindrome="" or="" not.="" if="" the="" string="" is="" a="" palindrome,="" the="" function="" returns="" 1.="" otherwise="" return="" 0.="" a="" string="" is="" said="" to="" be="" palindrome="" if="" it="" reads="" the="" same="" backward="" as="" forward.="" examples="" of="" palindrome="" strings,="" level,="" refer,="" aabaa,="" and="" abccba="" are="" a="" few="" of="" many="" examples="" of="" what="" is="" considered="" a="" palindrome.="" 9="" cop="" 3502c="" recurrence="" relations="" solve="" the="" following="" recurrence="" using="" the="" iteration="" technique.="" t="" (n)="4T" (n="" 2="" )="" +="" n="" t="" (1)="1">