1. A friend of yours wants you to design a database system to run her photo finishing business. Business operation: A customer drops or mails in one or more rolls of film. A clerk records that basic data on the customer and the film. The rolls are assigned a number, sorted, and run through the processor. Processing varies slightly depending on the type of film, film speed, and processing options. Your friend wants to keep track of which clerk performed the processing and match the names with any complaints that might arise. She also wants to offer a frequent-user program to reward the active customers. Create an entity-relationship diagram for this company. Identify the classes, their methods and attributes and relationships among the classes using a simple and clear class diagram. Answer: Classes: Customer, FilmRoll, Clerk, FreqCustomer extends Customer, (Database/Table recording details) Show the class diagram containing all these classes with relevant methods and relevant data. 2. You are required to build a BinarySearchTreeNode from a given BinaryTreeNode class. To do this: Define BinarySearchTreeNode as a sub class of BinaryTreeNode. Include the constructors. Add Serialization capability to BinarySearchTreeNode. Add a method to this sub class that inserts values into the BinarySearchTreeNode according to binary search tree property. Write a Java code segment that instantiates a BinaryTreeSearchNode with some initial data values (you don't have to show the values), inserts a specific value into it and removes the left-most leaf from it. Answer: See Lab6 answer given in class for a question and answer similar to this. Lab6 is available on everest at ~bina/cse116/fall2000/lab/lab6.inst 3. Given below are (i) CD collection class and (ii) a main program (class) that tests the CD collection class. \begin{enumerate} \item (2 points )Add another private data field {\bf totalTime} to the CD\_Collection class. This field stores the cumulative duration of play of all the CDs in the collection. \item (2 points) Update the header and the definition of method {\bf add\_cd} to include a new parameter {\bf cdTime}, and to add the new parameter to the {\bf totalTime}. Note that {\bf add\_cd} adds only one CD at a time. \item (4 points) Update all the calls to the method {\bf add\_cd} so that it reflects the change in the call format of the method (add\_cd). \item (4 points) Add another method {\bf avgTime} that computes and returns the average playing time for all the CDs in the collection. \item (3 points) Call the {\bf avgTime} from the main program and print out the result it returns with a suitable message. \end{enumerate} \begin{verbatim} class Tunes { public static void main( String[] args) { CD_Collection music; music = new CD_Collection(); music.add_cd (10.99); music.add_cd (39.34); music.print(); music.add_cd(20.82); music.print(); } } ////////////////////////////////// public class CD_Collection { private int num_cds; private double value_cds; public CD_Collection () { num_cds = 0; value_cds = 0.0; } public void add_cd (double value) { num_cds = num_cds + 1; value_cds = value_cds + value; } public void print() { System.out.println("*******************"); System.out.println("Number of CDs " + num_cds); System.out.println("Average cost per CD" + average_cost()); } private double average_cost(){ return value_cds/num_cds; } } \end{verbatim} Answer: Cut and paste the program and run it and check out your answers. 4. Determine the growth rate function (both exact expression and BigO notation) for each of the functions given below. Write convincing explanation for each of the answers. Show all the steps. a) for (i = 1; i <= N ; i++) for (j = 1; j <= 2; j++) for (k = 1; k <= N; k++) x = x + 1; answer: Assignment statement is executed N*2*N times. time is: N*2*N*a (where a is time taken for assignment) = 2N*N*a 2a*N*N for large values of N it is O(N-squared) b) for ( i =1; i <= N; i++) { j = N; while ( j > 1 ) j = j/2; } answer: j =N is executed N times. j= j/2 is executed N*log N total = N + N*logN for large N, this O(N*logN) 5. \item Draw the diagram of a tree that represents the expression given below: \\ $ A + B - C / A * D - F $ \\ \item Obtain the postfix and prefix expressions equivalent to the above. \item A scientist thinks of a new traversal scheme reverse\_prefix which is similar to prefix except that right sub\_tree is traversed before left sub\_tree. Give the reverse prefix expression of the above. Where do you this this expression form will be useful? \end{enumerate} answer: Tree will have the operators as internal nodes and operands as leafs. Tree diagran was given in class. Postfix expression: AB+CA/D*-F- Prefix: --+AB*/CADF reverse prefix : -F-*D/AC+BA 7. Write a recursive recognition algorithm (function/method) for the grammar given below: = A | B | A B | empty public boolean isL (String s) { // base cases if (s.length() == 0) return true; else if (s.length() == 1) { if ((s.charAt(0) =="A") || (s.charAt(0) =="B") return true; else return false; } // recursive steps else // assert: length > 1 if (s.charAt(0) == "A" && s.charAt(lenght()-1) == "B") isL(s.subString(1,s.length()-2)); // if you are here then you did not satisfy the base case // or recursive step return false; } 8. {\bf Show all the intermediate trees} \begin{enumerate} \item Insert the list \{ 4,15,5,22,18,16,45,53,30 \} {\bf in the order given into a max-heap}. Draw a complete binary tree and then heap it. \item Add 24 and show the updated {\bf heap}. \item Then, remove the root and show the reheaped tree. \end{enumerate} See class notes. 9. Write a recognizer determines if a given string is valid string in the language specified by the syntax diagram given below. (Write a recursive method that takes in as parameter a string and returns true if it is a valid string in the language specified, else returns false.) Also describe language in English. \begin{verbatim} = empty | = A..Z = 0..9 Answer: Similar to the question above. 10. Given a complete binary tree with 6746 nodes and with contiguous representation A[1] to A[6745]. \begin{enumerate} \item What is the height of this tree? answer: 14 ceiling(log 6745) \item How many internal nodes are there in the tree? Internal nodes are the non-leaf nodes. leaf nodes : 3373 internal nodes: 3372 \item Where is the parent of node A[461] located? 230 \item Where are the children of node at A[461] located? left child : 922 right child : 923 \question{25}{Object-oriented Design and Analysis} You have been asked to design a software simulator for a glider. Your group looked at the detailed specification and came up with the information listed below. \begin{enumerate} \item This simulator is for a glider with wings and rudder only. \item The glider has position, orientation, velocity and rotational rate. All these are computed using the forces on its surfaces. \item The glider has two {\bf types of surfaces}: rudder and wings. Wings provide lift while the rudder is used to steer. \item Each surface has area, orientation, mass, and center of gravity. \item Rudder has a deflection angle also. \item Force on each surface is computed using its attributes. \item For the glider, translation acceleration and rotational acceleration are computed using the forces computed above. \item The accelerations computed would be numerically integrated to update its (gliders) position, orientation, velocity and rotational rate. This completes the simulation. \end{enumerate} \begin{enumerate} \item Identify the classes and sub classes. Name them. \item Draw a class diagram with the their names, attributes and methods. \item Show the relationship among them using suitable arrows and lines. \end{enumerate} classes: Glider, Wing, Rudder, Surface Glider Wing extends Surface Rudder extends Surface Surface ====== =================== ===================== ======= Wing[2] deflectionAngle area Rudder computeTransVel computeRotVel orientation position mass orientation centerOfgravity rototationalVel velocity computeForce