Interdisciplinary Center Hertzelia, Notebook Number:
School of Computer Sciences, Student ID:
Introduction to Computer ScienceWinter 2003
Introduction to CS Final Exam
Dr. Ariel Shamir
English Version
You have 3 hours to answer the questions in the test. You are not allowed to use any study material, notebooks or papers. You are allowed, if you wish, to use an English dictionary.
The test has three parts. In the first part you must answer one small question. In the second part you must choose five out of eight small questions. Answer those questions on this form and submit it after you wrote your ID at the top, along with the test notebook. Please circle the number of the questions you are answering. Please note that question 1 is compulsory.
In the third part you are asked toanswer fourout of five questions,implementing some classes. Please use the notebook to write your implementation.
Section 1 (10 points)
Answer the following question. Do not use more space than the allocated lines for each answer.
1. What will be the return value of a call to f("abc")? Write a general description and explain the result of calling f() for any string s.
public static String f(String s) {
if (s == null || s.length() == 0)
return s;
char c = s.charAt(s.length()-1);
return c + (new Character(c).toString()) +
f(s.substring(0,s.length()-1)) + c;
}
Section 2 (40 points)
Choose and answer five questions from questions 2 to 9 (8 points each). Do not use more space than the allocated lines for each answer (Often you can use less!).Please circle the questions numbers you are answering.
2. Give a short definition or explanation (3 lines each) for the following terms
- Machine-code
- Byte-code
- Unicode
3.Write a method called sum() that receives an integer n and returns the sum of all integers from 0 to n. What is the largest number it can return? What is the smallest?
4. How many types in java are used to represent real numbers? How many numbers can each of them represent? Why is there a need for more than one type?
5. What is the difference between overloading methods and overriding methods in Java?
6. The memory image of a Java program while it is executing has three parts. Name those parts and describe their main use (three lines each).
7. Given the following definitions of A,B,C,D. Look at the definitions (a) to (d) of X, and determine if each of them is legal in Java. Explain why.
public class A {
// some code...
}
public class B {
// some code...
}
public interface C {
// some code...
}
public interface D {
// some code...
}
(a) public class X extends A, B {
// some code...
}
(b) public class X implements D, B {
// some code...
}
(c) public class Xextends A implements C{
// some code...
}
(d) public interfaceXimplements B{
// some code...
}
8. Consider the function f(n)= (2n-1)(3n+7)+n2. This function is an improvement by a factoronly in terms of complexity to which of the following (a)-(e)? Explain why!
(a)a(n) = n2 log(n)
(b)b(n) = 6n2+20n+9
(c)c(n) = 2+n
(d)d(n) = 3199999
(e)e(n) = (n-2)(10n+7)
9.Look at the following code and determine how many non-null elements and of what type will Vector v hold? Explain why! What will be printed out from the program and why?
import java.util.Vector;
public class Counting{
public static void main(String args[]) {
Vector v = new Vector();
for (int i = 0 ; i < 50 ; i++) {
v.add((i%7 == 0 ? null :
new Integer(i).toString()));
}
int count = 0;
countNonNull(v,count);
System.out.println(
"Vector v has " + count + " non-null elements");
}
public static void countNonNull(Vector v,int count) {
for (int i = 0 ; i < v.size() ; i++) {
if (v.get(i) != null)
count++;
}
}
}
Section 3 (max. 50 points)
Answer four out of the five questions 10-14 of the following question in your notebook.
Note that 10 & 11 are 15 points each and 12, 13, and 14 are only 10 points!!
There is no need to write Javadoc style documentation; however, you should add documentation in the usual places (head of functions, stages of algorithms etc.).
Read all sections of this question before answering. This will help you understand what is needed in all the implementation.
10. A Tuple class (15 points)
A tuple (or n-tuple) is a fixed size collection of elements. Pairs, triples, quadruples etc. are tuples. In a programming language, a tuple is a data object containing other objects as elements. These element objects may be of different types.
Here is the outline of the definition of the Tuple class:
/**
* A Tuple (or n-tuple) is a fixed size ordered
* collection of elements
*/
public abstract class Tuple implements Comparable {
}
The Comparable interface is defined in java.lang and includes a single method:
interface Comparable {
public int compareTo(Objecto);
}
The compareTo() method compares this object with the specified object o for order. It returns a either a negative integer, zero, or a positive integer if this object is less than, equal to, or greater than the specified object o (usually it returns -1,0 or 1).
10.1Looking at the definition of the class Tuple given in the next page answer – why is the class defined as an abstract class?
10.2Implement the Tuple class and all the methods of the Tuple class according to the interface in the following page.
Class Tuple Methods
Tuple
public Tuple(intsize)
A Tuple Constructor
Parameters:
size - The number elements in this tuple
Throws:
IllegalArgumentException - When size < 0
get
public Object get(inti)throws IndexOutOfBoundsException
Returns the element at index i
Throws:
IndexOutOfBoundsException - When i is outside the bounds of the Tuple
set
public void set(inti, Objectobj)
throwsIndexOutOfBoundsException
Stores obj at index i of the Tuple
Parameters:
i - The index
obj - The object reference
Throws:
IndexOutOfBoundsException - When i is outside the bounds of the Tuple
size
public int size()
Returns the size of the Tuple (number of elements)
toString
public String toString()
Returns a String representation of the Tuple. The String representation uses the '<' and '>' as openning and closing brackets, calls each element toString() method and separates elements with ','. For example in a Tuple of 3 ints we will have: <1,2,3>
Overrides:
toString in classObject
11. IntTuple & Float2Vec Classes (15 points)
In this section you should implement two concrete (non-abstract) sub-classes of Tuple class. If you implemented Tuple correctly it means you should not use any new data members in any of the two sub-classes!
11.1 IntTuple
IntTuple represents a tuple of integers. The comparison of two IntTuple objects having the same size (number of elements) should be done by lexicographic ordering. Here are some examplesof comparing two int tuples with size three:
<-2,3,4> <-5,99,8>
<10,3,4> <10,3,7>
<3,4,6> = <3,4,6>
Implement the class IntTuple as a subclass of Tuple according to the following interface:
public IntTuple(intsize)
An IntTuple Constructor
Parameters:
size - The size of the IntTuple
public IntTuple(int[]data)
An IntTuple Constructor
Parameters:
data - An array holding all the integers to be stored in the IntTuple.The size of IntTuple will be the length of the Array
public int compareTo(Objectother)throws ClassCastException
Implements the method of Comparable interface by lexicographic ordering (index 0 first) of the int elements of IntTuple.
Overrides:
compareTo in class Tuple
Throws:
ClassCastException - When other is not an IntTuple or when this and other are a different size IntTuples.
public void set(inti, intval) throws IndexOutOfBoundsException
Sets the value at position i to val
Parameters:
i - The position to set
val - The value to set
Throws:
IndexOutOfBoundsException - When i is outside the bounds of the Tuple
public int intValue(inti) throws IndexOutOfBoundsException
Returns the int value stored at position i
Throws:
IndexOutOfBoundsException - When i is outside the bounds of the Tuple
11.2Float2Vec
Float2Vec represents a tuple of 2 floats, which is used to represent a two-dimensional vector. The comparison of two Float2Vec objects should be done by comparing their length. The length of a two dimensional vector <x,y> is (x2 + y2) (i.e. square root of x2 + y2).
Note that all calculations on vectors are done with a precision of EPSILON (you can choose EPSILON to be 10-6). For example, two vectors whose difference in length is smaller than EPSILON are considered the same length.
Implement the class Float2Vec as a subclass of Tuple according to the following interface:
public static final float EPSILON
EPSILON is the precision used in all calculations using Float2Vec. Anything smaller than EPSILON is considered 0.
public Float2Vec(floatx, floaty)
A Float2Vec Constructor
Parameters:
x - The x coordinate of the vector
y - The y coordinate of the vector
public float getx()
Returns the x coordinate of the Vector
public float gety()
Returns the y coordinate of the Vector
public float length()
Returns the length of the Vector
public int compareTo(Objectother) throws ClassCastException
Implements the method of Comparable interface by comparing the length of this vector and the other vector.
Overrides:
compareTo in class Tuple
Throws:
ClassCastException - When other is not a Float2Vec
12. Sorting Tuples(10 points)
Write a method called sortTuples() that receives a java.util.Vector which is used to store any unkownTuple objects of the same kind (for example all elements will be Float2Vec or IntTuples of the same size) and sorts the elements in the vector.
You can use any ofjava.util.Vectormethods included in the attached appendix.
13.Tuple Combinations (10 points)
Assume you have n items in a Tuple, and you wish to choose k items out of them. If k=n then we have just one possible subset which is the whole Tuple. If k<=0 by convention we say there are 0 such subsets. However when 0< k < n there are many possible choices.
For example, if the Tuple is a,b,c,d and we want to choose 2 items we have all the following options: {a,b} {a,c} {a,d} {b,c} {b,d} {c,d}. Note that there is no significance to the order of the items for example the subsets {a,b} and {b,a} are considered the same.
Looking at this problem recursively, each item in the tuple can either be chosen or not chosen in each sub-set of k elements. If we chose the item, we still have (k-1) items to choose out of (n-1) items. If we did not choose the item we have k items to choose out of (n-1) items. Together we get:
Choices(k,n) = Choices(k-1,n-1) Choices(k,n-1)
Add a method to the Tupleclass called printCombinations() which receives an integer k, prints to System.out all possible combinations of k elements out of the elements in the Tuple,and returns the number of such combinations. This method should call a recursive private utility method that you will define in order to perform the task.
/**
* Prints to System.out all combinations of k elements from
* this Tuple. Returns the number of combinations printed
* (if n is the size of the Tuple it is like choosing k
* out of n).
* @returns The number of k combinations out of the Tuple
*/
public int printCombinations(int k) {
// your code
}
14. Using Tuples (10 points)
Assume you want to count the number of occurrences of each word in a given text. A simple way to solve this problem would be to scan the text for each word in the text and count the number of occurrences. However, to make the scan more efficient and in order not to scan the same word more than once, we would like to be able to remove from the text all words that were already scanned.
We insert all words of the text into a Vector of Strings allWords, now we need two operations: findOccurences(String word, Vector allWords) that finds the indexes of all occurrences of a given String word in a vector, and removeOccurences(IntTuple indexes, Vector allWords)that removes from the vector allWords a list of indexes. Here is an example of a possible implementation for such algorithm:
While (!allWords.isEmpty()) {
String word = allWords(String)allWords.firstElement();
IntTuple indexes = findOccurences(word,allWords);
System.out.println("Word " + word + " is found " +
indexes.size() + " times in the text");
removeOccurences(indexes,allWords);
}
Use the class IntTuple from question 11 and implement the following two methods so that they will work together correctly (for example in the above code):
/**
* Returns an IntTuple which includes all indexes of the String
* word in the Vector allWords sorted from the smallest index to
* the largest index.
*/
IntTuple findOccurences(String word, Vector allWords)
{
// your code
}
/**
* Removes all items in position of the sorted indexes from the
* Vector allWords.
*/
void removeOccurences(IntTuple indexes, Vector allWords)
{
// your code
}
Good Luck!