My Midterm for Data Structures and Algorithsm

[Daddy]

Italics are my answers, red is the teacher's score out of 10 for each question or comment.  powerofone;

Name __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.

[The Hand That Fisted Everyone]

So you failed?

[Daddy]

So you failed?

I got a D.

[Wrench]

Study harder, V Man.

[The Hand That Fisted Everyone]

I got a D.

Wait, so how is the grading system?

[Daddy]

Study harder, V Man.

I got anything related to math or programming right.  

[Wrench]

I got anything related to math or programming right.  

What would doodthing do?

[ME##]

is that a wink i see there sir

[Kalahari Inkantation]

Pros: Not contigious in memory locations ;) ?

i absolutely lol'd

So you failed?

Failing means 64 or less here.

[superclucky]

i absolutely lol'd
Failing means 64 or less here.

Failing here is a 70 or less.

[ME##]

i absolutely lol'd
Failing means 64 or less here.

huh to fail here you need 59% or lower

[Kalahari Inkantation]

lol

[superclucky]

Lawl
My school is like, 40% spics and 30% black.

[Kalahari Inkantation]

oh

[guff]

I got anything related to math or programming right.  

no you didn't