Unformatted text preview:

CS 307 – Midterm 2 – Spring 2009 1 Exam Number: Points off 1 2 3 4 5 Total off Net Score CS 307 – Midterm 2 – Spring 2009 Name__________________________________________ UTEID login name _______________________________ TA's Name: Guhan Todd Xiuming (Circle One) Instructions: 1. Please turn off your cell phones and other electronic devices. 2. There are 5 questions on this test. 3. You have 2 hours to complete the test. 4. You may not use a calculator on the test. 5. When code is required, write Java code. 6. When writing methods, assume the preconditions of the method are met. Do not write code to check the preconditions. 7. In coding question you may add helper methods if you wish. 8. After completing the test please turn it in to one of the test proctors and show them your UTID. 1. (2 points each, 30 points total) Short answer. Place you answers on the attached answer sheet. • If the code contains a syntax error or other compile error, answer “compile error”. • If the code would result in a runtime error / exception answer “Runtime error”. • If the code results in an infinite loop answer “Infinite loop”. Recall that when asked for Big O your answer should be the most restrictive correct Big O function. For example Selection Sort has an average case Big O of O(N2), but per the formal definition of Big O it is correct to say Selection Sort also has a Big O of O(N3) or O(N4). I want the most restrictive correct Big O function. (Closest without going under.) A. What is the Big O of the following method? N = mat.length // pre: mat != null, mat is a square matrix public double methodA(double[][] mat){ int total = 0; for(int c = mat.length - 1; c >= 0; c--) for(int r = c; r >= 0; r--) total += mat[r][c]; return total; }CS 307 – Midterm 2 – Spring 2009 2 B. What is the worst case Big O of the following method? N = data.length public int methodB(int[] data){ int count = 0; for(int i = 0; i < data.length; i++){ if( data[i] % 2 == 0 ) count++; } for(int i = 1; i < data.length; i++){ if( data[i] % 10 == 0 ) count++; } return count; } C. What is the worst case Big O of the following method? N = data.length. The length method from the String class is O(1). public int methodC(String[] data){ int sum = 0; for(int i = 0; i * i < data.length; i++){ int temp = i * i; if( data[temp] != null ) sum += data[temp].length(); } return sum; } D. What is the worst case Big O of the following method? N = data.length. public boolean methodD(int[] data, int tgt){ int temp; boolean found = false; int index = 0; int limit = data.length - 4; while( index < limit && !found ){ temp = 0; for(int off = 0; off < 5; off++) temp += data[index + off]; found = temp == tgt; index++; } return found; } E. A method is O(2N). It takes 5 seconds for the method to complete when given a data set with 100 elements. What is the expected time for the method to complete when given a data set with 104 elements? F. A method is O(N2). It takes 1second for the method to complete when given a data set with 10,000 elements. What is the expected time for the method to complete when given a data set with 30,000 elements?CS 307 – Midterm 2 – Spring 2009 3 G. What is returned by the method call methodG(7)? public int methodG(int n){ if(n >= 10) return 3; else return (10 - n) + methodG(n + 1); } H. What is output by the method call methodH("UTCS")? The substring(int) method returns a substring that begins with the character at the specified index and extends to the end of the string. public void methodH(String s){ if( s.length() == 1 ) System.out.print(s); else{ System.out.print( s.charAt(0) ); methodH( s.substring(1) ); System.out.print( s.charAt( s.length() - 1 ) ); } } I. What is returned by the method call methodI(4)? public int methodI(int n){ if(n <= 0) return 2; else return n + methodI(n - 1) + methodI(n - 3); } J. What is the Big O of removing the element at position 0 from an array based list that already contains N elements? K. What is the Big O of removing the element at position 0 from a linked list that already contains N elements? L. The best case Big O of the insertion sort algorithm is O(N). Under what conditions does this best case occur? M. Given a sorted array of 4000 elements, about how many elements will the binary search algorithm examine when searching for a value that is not present in the array? Given your answer as an integer. Recall log21,000 ~= 10.CS 307 – Midterm 2 – Spring 2009 4 N. Briefly explain what operation on a linked list can be made more efficient by having an iterator for the linked list. O. Consider the following methods from the Java ArrayList class. Method Summary void add(E o) Appends the specified element to the end of this list. void add(int index, E element) Inserts the specified element at the specified position in this list. E get(int index) Returns the element at the specified position in this list. E remove(int index) Removes the element at the specified position in this list. Return the element that is removed from the list. E set(int index, E element) Replaces the element at the specified position in this list with the specified element. Returns the element that was previously at index. int size() Returns the number of elements in this list. What is output when method methodO is called? public void methodO(){ ArrayList<String> ls = new ArrayList<String>(); ls.add("M"); ls.add(0, "K"); ls.add("O"); ls.add(1, "I"); ls.add(ls.get(2)); ls.set(2, "GG"); for(String s : ls) System.out.print( s ); }CS 307 – Midterm 2 – Spring 2009 5 2. (Implementing Data Structures 20 points) In this question you will work with a type of list called a FrequencyList. The FrequencyList is very similar to the List class but it also tracks how often items are accessed via the get method. Every time an element of the list is accessed its frequency is incremented. You will write a method to


View Full Document

UT CS 307 - CS 307 – Midterm 2

Documents in this Course
Midterm 2

Midterm 2

15 pages

Midterm 1

Midterm 1

15 pages

Syllabus

Syllabus

24 pages

s

s

8 pages

Midterm 1

Midterm 1

14 pages

Midterm 2

Midterm 2

14 pages

Recursion

Recursion

14 pages

Midterm 1

Midterm 1

16 pages

Load more
Download CS 307 – Midterm 2
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view CS 307 – Midterm 2 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view CS 307 – Midterm 2 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?