Italics are my answers, red is the teacher's score out of 10 for each question or comment. powerofone;
QuoteName __James Valente___ Section_01_ Date _10/16/08__
CS 260 Mid-term Exam I
1. Describe Stack ADT and its 4 basic operations.
Answer:
Uses Last In First Out to access items, allowing to only access the last inerseted item.
Push: Insert the top element
Pop: Remove the top element
Top: Find the top element
Length: Returns amount of nodes in a stack Useless – a proper one would be isEmpty.
9
2. Group the following into equivalent Big-O functions:
x2, x, x2 + x, x3 / (x + x2 – 1)
Answer:
Linear:
X
Quadratic:
X2, X2 + X
Cubic:
X3 / (x+x2 -1) Linear
8
I hope
3. An algorithm takes 1 MS for input size 100. How long will it take for input size 10000 (you can ignore the lower-order terms) if the running time is
a. linear
Answer:
N
100MS
b. O(N log N)
Answer:
N log N
20 Seconds 100 log 100
c. quadratic
Answer:
N2
10000 Seconds
d. cubic
Answer:
N3
1000000 Seconds
7
4. Order the following functions by growth rate:
N, √N, N1.5, N2, 2N, N log N, N2 log N
Answer:
√N,N, N log N, N1.5,N2, N2 log N, 2N
10
5. Justify the best possible
Big-O estimates for the 4 basic Stack operations described in the question 1.
Answer:
Logarithmic because they are faster. :0
All Stack operations are O(1)
0
6. What is ADT? Describe a standard Java approach of specifying ADT.
Answer:
ABSTRACT DATA TYPES Details = ?
YOU USE EXTENDS LIKE THIS:
class buffaloWings extends blueCheese
Interface
2
7. Define autoboxing/unboxing in Java 5.0 and provide a code sample that illustrates this feature.
Answer:
// List adapter for primitive int array
public static List<Integer> asList(final int[] a) {
return new AbstractList<Integer>() {
public Integer get(int i) { return a; }
// Throws NullPointerException if val == null
public Integer set(int i, Integer val) {
Integer oldVal = a;
a = val;
return oldVal;
}
public int size() { return a.length; }
};
}
It allows you to get around the fact that collections only hold references to objects, and not datatypes such as INT. Autoboxing … is not collection specific, it’s simply allows to implicitly convert between primitive data types and their wrapper classes.
9
8. Describe Java 5.0 generics and provide a sample class header using this feature.
Answer:
public class Pair<T, S>
{
public Pair(T f, S s)
{
first = f;
second = s;
}
Generics allow a type or method to operate on objects of various datatypes while providing compile-time type safety
10
9. Describe the circular array implementation of the Queue ADT.
Answer:
It uses the FIFO method and it allows you to remove elements from the array. This is not specific to the circular array
0
10. What is a delegation
pattern? Provide code skeleton to illustrate the delegation usage in Java.
Answer:
It allows a specific object to have a behavior by relying on another object. Method to method
Code skeleton = ?
:’(
4
11. Compare the pros and cons of the array based vs. linked list based implementations of the list ADT.
Answer:
ARRAY BASED
Pros: Faster and easier access
Cons: Fixed Size :| So what?
LINKED BASE
Pros: Not contigious in memory locations ;) ?
Cons: will not stop existing after use so garbage collection is needed. Same with arrays
4
12. Describe 3 reasons for using generic collections vs. Object (top level Java class) based collections.
Answer:
It is faster
It is neater
It requires less resources.
3
The grade is 66.
So you failed?
Study harder, V Man.
Quote from: Headless Horseman on October 19, 2008, 02:30:36 PM
Study harder, V Man.
I got anything related to math or programming right. baddood;
Quote from: Khadafi on October 19, 2008, 02:32:15 PM
I got anything related to math or programming right. baddood;
What would doodthing do?
is that a wink i see there sir
Quote from: KhadafiPros: Not contigious in memory locations ;) ?
i absolutely lol'd
Quote from: Sidney A. Stubbs on October 19, 2008, 02:26:21 PM
So you failed?
Failing means 64 or less here. baddood;
Quote from: TECTRON on October 19, 2008, 02:37:08 PM
i absolutely lol'd
Failing means 64 or less here. baddood;
Failing here is a 70 or less. :3
Quote from: TECTRON on October 19, 2008, 02:37:08 PM
i absolutely lol'd
Failing means 64 or less here. baddood;
huh to fail here you need 59% or lower
lol
Lawl
My school is like, 40% spics and 30% black.
oh
Quote from: Khadafi on October 19, 2008, 02:32:15 PM
I got anything related to math or programming right. baddood;
no you didn't doodthing;
Quote from: Khadafi on October 19, 2008, 03:21:21 PM
:(
a cubic divided by a quadratic is not cubic baddood;
Quote from: Commodore Guff on October 19, 2008, 03:29:02 PM
a cubic divided by a quadratic is not cubic baddood;
It was Big Oh notation, I thought it meant to ignore any term except the highest I didn't know you had to divide first. :(