CS 201 Exam
Wednesday, 6 February 2019
On your resubmission of this exam, please give answers for all the questions, including
the ones for which you got full credit last time. Also, provide brief justifications
where appropriate (e.g. not just "this is O(N)" but "this is O(N), because...").
- (5 points) Implement this method.
/**
* Prints to System.out all the even integers >= 0 and
* <= N, one per line, in increasing order.
*/
public static void countUpEvens(int N)
- (8 points) Please give short answers to these questions.
- What is the difference between a method marked private and one marked public?
- What is an instance variable? Give an example.
- What is the difference between a Java class and a Java interface?
- What would motivate someone to create an interface (e.g. List) instead of a class?
- (6 points) Consider the types
String[]
ArrayList<String>
LinkedList<String> (i.e. Java's built-in linked list class)
- Briefly list advantages and disadvantages of each of these types.
- For each of the three types, give one example of a situation in which
you would choose to use that type, and briefly explain why.
- (16 points) Consider the classes Thing and Tester at the end
of this exam. For each question below, start from the original
Thing.java and Tester.java and imagine
uncommenting only the specified section, compiling both Thing.java and Tester.java,
and running the specified "java" command.
Then say which of the following happens:
- There's a compile-time error. If so, explain the nature of the error.
- There's a run-time error. If so, explain the nature of the error.
- The code compiles and runs. If so, say what output the code produces.
Note: By "uncommenting", I mean that you should remove the
/* and */ comment markers that currently surround the
experiment in question, so that the code for that experiment gets compiled.
- What happens if you uncomment only EXPERIMENT 1, compile, and run "java Thing"?
- What happens if you uncomment only EXPERIMENT 2, compile, and run "java Tester"?
- What happens if you uncomment only EXPERIMENT 3, compile, and run "java Tester"?
- What happens if you uncomment only EXPERIMENT 4, compile, and run "java Tester"?
- (8 points) Suppose I have four implementations of a Stack interface:
- An ArrayList<String>, where the top of the stack is at the beginning (i.e. at index 0).
- An ArrayList<String>, where the top of the stack is at the end
(i.e. at index N - 1, where N is the number of items in the stack).
- A singly linked list with the top of the stack at the head of the list.
- A singly linked list with the top of the stack at the end of the list.
Consider the "public void push(String s)" method in each of these four implementations,
and denote by N the number String objects on the stack.
- Use Big-O notation to describe the running time of push for Case I.
- Use Big-O notation to describe the running time of push for Case II.
- Use Big-O notation to describe the running time of push for Case III.
- Use Big-O notation to describe the running time of push for Case IV.
- (8 points) Consider Cases III and IV from the previous problem. Assume that the linked list in
in each situation is represented by an instance variable named head, like so:
private class Node {
public String data;
public Node next;
};
private Node head;
- Implement public void push(String s) for Case III.
- Implement public String pop() for Case IV.
(4 points) Consider the following code, which counts how many pairs of strings
in the specified array are identical.
public int countMatchingPairs(String[] strings) {
int N = strings.length;
int count = 0;
for (int j = 1; j < N; j++) {
for (int k = 1; k < j; k++) {
if (strings[j].equals(strings[k])) {
count++;
}
}
}
return count;
}
- Use Big-O notation to describe the running time of this method in terms of N.
- Suppose countMatchingPairs takes approximately 4.0 seconds to run if N=100000. Approximately
how long does it take to run if N=400000?
Thing.java
public class Thing {
private int number;
public void setNumber(int number) {
this.number = number;
}
public int getNumber() {
return this.number;
}
public static void main(String[] args) {
// EXPERIMENT #1
/*
this.number = 45;
System.out.format("The number: %d\n", this.number);
*/
}
}
Tester.java
public class Tester {
public static void main(String[] args) {
// EXPERIMENT #2
/*
Thing t = new Thing();
t.age = 15;
t.name = "Elmo";
System.out.println(t.toString());
*/
// EXPERIMENT #3
/*
int a = 27;
int b = a;
b = 39;
System.out.format("ints: %d, %d\n", a, b);
Thing aa = new Thing();
aa.setNumber(27);
Thing bb = aa;
bb.setNumber(39);
System.out.format("Things: %d, %d\n", aa.getNumber(), bb.getNumber());
*/
// EXPERIMENT #4
/*
String[] animals = {"dog", "cat", "eland"};
int k = 0;
while (k < animals.length && !animals[k].equals("goat")) {
System.out.println("No goat: " + animals[k]);
k++;
}
k = 0;
while (!animals[k].equals("goat") && k < animals.length) {
System.out.println("No goat: " + animals[k]);
k++;
}
*/
}
}