A sequence of essential operations necessary for producing quality software.

True of False:

According to the waterfall model you're supposed to design all of your algorithms before coding.

True of False:

According to the waterfall model You need to write test cases before coding

True or False:

According to the waterfall model you should use prototype implementation to refine your design

True or False:

According to the Unified mode you should design all of your algorithyms before coding.

True or False:

According to the unified model you should write all of your test cases before coding.

True or False:

According to the unified model you should use a prototype implementation to refine the design

True or False:

Compared to program verification, empirical testing handles larger programs.

True or False:

Compared to program verification, empirical testing always catches more errors.

True or False:

Compared to program verification, empirical testing ensures code is correct.

True or False:

Compared to program verification, empirical testing can be applied without examining code.

True or False:

Code coverage is a measure of code testing  

True or False:

Pre-conditions and post-conditions are used for empirical testing

Define abstraction

Providing a simple high-level view of an entity or activity.

Define encapsulation

Confining / hiding information so it can only be accessed through a defined interface.

Data is hidden inside objects and can only be accessed through its public methods.

What are class diagrams used for?

Describes the static structure of classes in a software system

   On average, what is the complexity of doing an insertion in a binary search tree?

O(log(n))

  On average, what is the complexity of doing a find in a binary search tree?

O(log(n))

       What is the worst-case complexity of doing a find in a binary search tree?

O(n)

  What can cause worst-case behavior in a binary search tree?

Unbalanced / degenerate binary trees

     What is a tree traversal?

Visiting all the nodes in a tree

   What is the difference between a depth-first and breadth-first traversal?

Depth-first traversal visits entire subtree first, breadth-first traversal visits nodes in order of their distance from the root

True or False:

Pre-order, in-order, and post-order are all  depth-first traversals

True or False:

Pre-order traversals are faster than post-order traversals

True or False:

Using “==” and .equals() always return the same result

True or False:

Variables of type Integer and int are both references

True or False:

Autoboxing creates an Integer object from an int

true or False:

Exceptions are used to capture run-time errors          

   What are two key properties of a heap?

Complete binary tree where value at node is smaller or equal (can also be larger or equal) to values in subtrees

  What operation(s) supported by binary search trees are not supported by heaps?

find largest key, find key with value k

   On average, what is the complexity of doing an insertion in a heap?

O(log(n))

On average, what is the complexity of doing a getSmallest( ) in a heap?

O(log(n))

     What is the worst-case complexity of doing a getSmallest( ) in a heap?

O(log(n))

1.      Name two things you can do with abstract classes that you cannot do with interfaces.

define variables, define methods

1.      When is the finalize() method invoked?

When the object is garbage collected

1.      Describe the Java Hash Code contract.

Two objects that are equal according to the equals method must have the same hashCode value

Does the default implementation of equals and hashCode in Java satisfy the Java Hash Code contact?  Explain briefly.

Yes, it does. equals compares object addresses and hashCode returns address object

What is the big-O for insertion and deletion operations for hashing if we were to have a perfect (extremely good) hashing function?

O(1)

1.      When is the following assignment valid?

ArrayList<Object> L = new ArrayList<String>();

Never

What is procedural abstraction?

Specifies what actions should be performed, hiding algorithms

1.      The method evaluate may throw an exception (IllegalArgumentException) according to the argument value provided.  Modify the following code fragment so the exception is handled by a catch clause in processInfo.  The catch clause will display the message “Invalid argument” using System.out.println.

      public void processInfo() {

                        int y = 20;

                        int result = evaluate(y);

                        System.out.println(result);

}

      public void processInfo() {

                  int y = 20;

                  try {

                              int result = evaluate(y);

                              System.out.println(result);

                  }

                  catch(IllegalArgumentException e) {

                              System.out.println("Invalid argument");

                  }

      }

1.      The method computeValue throws a checked exception (named MyException).  Modify the following code so we don’t have to handle it in the method generateResults.

      public static void main(String[] args) {

                                new ExampleChecked().generateResults();

                }

                public void generateResults() {

                                computeValue(10);

             }

public static void main(String[] args) throws MyException {

                      new ExampleCheckedImp().generateResults();

          }

          public void generateResults() throws MyException {

                      computeValue(10);

          }

1.      (7 pts) Make the following class generic so that it can deal with an arbitrary class rather than only Strings.  Feel free to cross out parts of the following code.

public class Col        {

       private ArrayList<String> c;

public String get() {  return c.remove(0);   }

public void insert(String value) {   c.add(value);   }

}

public class Col<T>        {

            private ArrayList<T> c;

public T get() {  return c.remove(0);   }

public void insert(T value) {   c.add(value);   }

}

True or False:       Integration tests are applied after unit tests                                           

What is the algorithmic complexity of the following in terms of BigO

for (int i=2; i<n/2; i++)

for (int k=2; k<i; k++)

(True or False)      All Java exceptions must be caught or declared                        

True or False: Using multiple threads can simplify the structure of a program                     

True or False: The Factory pattern is a structural design pattern                  

True or False: The State pattern describes how to save the state of the program

In MVC what does the model do?

In MVC what does Controller do?

Sort the following BigO notations of algorithmic complexity from least complexity to highest complexity

 O(nⁿ) , O(n!) ,O(kⁿ) , O(n^k) ,

O(n^k) , O(kⁿ), O(n!), O(nⁿ) 

Bubble Sort

What is the AVG case complexity?

What is the worst case complexity?

In place?

Can be Stable?

AVG case complexity : O(n²)

Worst case complexity: O(n2)

In Place? YES

Can be Stable? YES

Selection Sort

Average Case Complexity?

Worst Case Complexity?

In Place?

Can be stable?

Average Case Complexity: O(n2)

Worst Case Complexity: O(n2)

In Place: YES

Can be stable: YES

Tree Sort

Average Case Complexity?

Worst Case Complexity?

In Place?

Can be stable?

Average Case Complexity: O(n log(n))

Worst Case Complexity? O(n2)

In Place: NO

Can be stable: NO

Heap Sort

Average Case Complexity?

Worst Case Complexity?

In Place?

Can be stable?

Average Case Complexity: O(n log(n))

Worst Case Complexity? O(n log(n))

In Place? NO

Can be stable? NO

Quick Sort

Average Case Complexity?

Worst Case Complexity?

In Place?

Can be stable?

Average Case Complexity: O(n log(n))

Worst Case Complexity: O(n2)

In Place: YES

Can be stable: NO

Merge Sort

Average Case Complexity?

Worst Case Complexity?

In Place?

Can be stable?

Average Case Complexity: O(n log(n))

Worst Case Complexity: O(n log(n))

In Place: No

Can be stable: YES

1.Chain of Responsibility - A way of passing a request between a chain of objects
2.Command - Encapsulate a command request as an object
3.Interpreter - A way to include language elements in a program
4.Iterator - Sequentially access the elements of a collection
5.Mediator - Defines simplified communication between classes
6.Memento - Capture and restore an object's internal state

7.Observer - A way of notifying change to a number of classes
8.State - Alter an object's behavior when its state changes
9. Strategy - Encapsulates an algorithm inside a class
10.Template Method - Defer the exact steps of an algorithm to a subclass
11.Visitor - Defines a new operation to a class without changing class

Name two representations used for the implementation of a graph (don’t name any that use Sets).

(True or False)A Java object can be assigned two locks. 

(True or False)A program with data races will produce different results each time it is run

A copy of an object with the same value in each field

(True or False)The default clone method creates a shallow copy of the object. 

Why do programmers use design patterns?

Benefit from design of experienced programmers

(True or False)Actions may be abstracted to reduce complexity

(True or False) Asymptotic complexity measures # steps used by algorithm

(True or False) Java inner classes support encapsulation

True

(True or False)Anonymous inner classes are useful for classes used in only one place

(True or False)Java exceptions are used to represent unexpected and/or rare conditions

(True or False)All Java exceptions must be caught or declared