CompSci 100e Program Design & Analysis IIFall 2007 Forbes Written Assignment #1Due Friday, October 5 in classBig-Oh1. Suppose T1(n) ∈ O(f(n)) and T2(n) ∈ O(f(n)). Answer whether the following are true orfalse and give justification. A justification for being true is a simple mathematical proof,while you can prove something to be false by giving a specific counterexample. You shoulduse the definition of big-Oh in both cases.(a) T1(n) + T2(n) ∈ O(f(n)(b) T1(n) − T2(n) ∈ O(f(n)(c) T1(n)/T2(n) ∈ O(1)(d) T1(n) ∈ O(T2(n))12. By doubling the size of an array used to store an ArrayList, we pay constant amortized timefor each add operation. Suppose that allocating a ArrayList containing M elements takesM/2 + 10 time units, copying M elements from one ArrayList to another takes M timeunits, and a push takes 1 time unit plus the amount of time (if any) required to increase thesize of the ArrayList.(a) If the size of the ArrayList increases by 100 (that is, 100 more elements, not 100 timesas many), how long will N add operations take?(b) If the size of the ArrayList doubles each time the stack fills up, how long with N addoperations take?(c) If the size of the ArrayList increases by a factor of 1.5 each time, how long will N addstake?3. Extra Credit: Show (log n)K∈ O(n) for any K.CompSci 100e, Fall 2007, Written Assignment #1 2Linked ListsIn all these problems assume that the inner class Node exists as shown below. You’ll writestatic methods in a class LinkProblems for your solutions. You cannot use instance variables,all variables must be local to the static methods you write.public class LinkProblems{public static class Node{String info;Node next;Node(String s, Node link) {info = s;next = link;}}// your methods here}4. Write the method fruitCounter whose header follows. Method fruitCounter returns a countof the number of nodes whose info field has a value for which a static method isFruit (seebelow) returns true.public static boolean isFruit(String s){// code not shown}For example, assuming that ”apple”, ”orange”, and ”pear” are fruits (isFruit returns true)and ”bear”, ”coyote”, and ”fox” are not fruits, and list is represented by:("apple", "bear", "apple", "orange", "coyote", "fox", "orange", "pear")the call fruitCounter(list) should evaluate to 5 since there are five fruits.CompSci 100e, Fall 2007, Written Assignment #1 3Write two versions, one iterative and one recursive./*** @return the number of nodes whose info field is a fruit* as determined by method isFruit*/public static int fruitCounter(Node list)CompSci 100e, Fall 2007, Written Assignment #1 45. Occurs Check(a) Write a method hasDuplicates whose header follows. The method returns true if param-eter list has any duplicates (words occurring more than once) and false otherwise. Forexample, for the list( "apple", "guava", "cherry")hasDuplicates should return false, but it would return true for the list below since"guava" appears twice.( "apple", "guava", "cherry", "guava")In writing hasDuplicates you must call the method countOccurrences shown below andyour method must be either a recursive function with no loop or a function with one loop.Either version can include calls to countOccurrences. You cannot use any ArrayList,Set, etc. objects in your code./*** @return the number of occurrences of s in list*/public static int countOccurrences(Node list, String s) {if (list == null) return 0;int count = 0;if (list.info.equals(s)) count = 1;return count + countOcurrences(list.next,s);}/*** @return true if and only if list has duplicates**/public static boolean hasDuplicates(Node list) {CompSci 100e, Fall 2007, Written Assignment #1 5hasDuplicates continued(b) What is the complexity (using big-Oh) of the solution you wrote to hasDuplicatesand why?(c) Describe how to write a more efficient solution to the hasDuplicates method using, forexample, a TreeSet or a HashSet instead of calling countOccurrences. Be sure toindicate what the complexity of your solution is and why.CompSci 100e, Fall 2007, Written Assignment #1 66. Extra credit: Write a method that determines whether a list has any cycles in it usingconstant extra space.The prototype for the function is:/*** Returns true if and only if list has no cycles, that is no* node appears multiple time in the list* Amount of space allocatd is constant, i.e. not proportional to the* size of the list* @param list that should not be changed* @return true if and only if list is circular*/public static boolean isCircular(Node list)7. The following problems use the class TermNode below to represent a single term of a polyno-mial. For example 3x100can be represented by TermNode(3,100,null); and 7x50+ 2x5+ 8is represented byTermNode poly = new TermNode(7,50, new TermNode(2,5, new TermNode(8,0,null)));Here’s the class definition.public static class TermNode{int coeff;int power;TermNode next;TermNode(int co, int po, TermNode follow) {coeff = co;power = po;next = follow;}}CompSci 100e, Fall 2007, Written Assignment #1 7(a) Write a method makePolyNomial that takes a polynomial expressed in array form inwhich every term is explicitly stored (including those with zero-coefficients) and returnsa polynomial expressed in linked list form (list of TermNodes) in which just terms withnon-zero coefficients are stored. For example, given a array of [3, 0, 0, 2, 5], your functionshould return the list ( (3, 4), (2, 1), (5,0) ) since both represent 3x4+ 2x + 5.Here we assume the 5 in the array has index 0 and the 3 has index 4, so the array isshown with the zero-index on the right (but your method doesn’t have a right or a left,just an array with a length and int coefficients)./*** Returns a list of TermNodes representingy poly,* the elements in poly are in sorted order by power/exponent* with largest exponent first, no zero-coefficent terms in list returned.*/public static TermNode makePolyNomial(int[] poly)(b) Write a method addPolyNomial that takes two polynomials expressed as lists of TermNodes,and returns a new polynomial representing the sum of the two parameters. The param-eters should not be altered as a result of calling addPolynomial, a new polynomial iscreated and returned.For example, (3x4+ 2x + 4) + (2x2− 4x − 9) = (3x4+ 2x2− 2x − 5)((3,4),(2,1),(4,0)) + ((2,2),(-4,1),(-9,0)) =( (3,4),(2,2),(-2,1),(-5,0) )// pre: elements in p1 and p2 are sorted by power, largest to smallest// (standard form for this problem)// post: returns polynomial/list of
View Full Document
Unlocking...