Shared Flashcard Set

Details

CMSC132
FINAL
118
Computer Science
Undergraduate 1
04/24/2012

Additional Computer Science Flashcards

 


 

Cards

Term
What is the main reason software projects fail?
Definition
Complexity of the projects
Term
What is the software lifecycle?
Definition


A sequence of essential operations necessary for producing quality software.

 

Term
What is the first phase of the software life cycle?
Definition
Problem Specification
Term

True of False:

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

Definition
True
Term

True of False:

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

Definition
False
Term

True or False:

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

Definition
False
Term

True or False:

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

Definition
False
Term

True or False:

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

Definition
False
Term

True or False:

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

Definition
True
Term

True or False:

Compared to program verification, empirical testing handles larger programs.

Definition
True
Term

True or False:

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

Definition
False
Term

True or False:

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

Definition
False.
Term

True or False:

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

Definition
True
Term

True or False:

Code coverage is a measure of code testing  

Definition
True
Term

True or False:

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

Definition
False
Term

Define abstraction

 

Definition

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

 

Term

 

Define encapsulation

 

Definition

 

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

 

Term
 Describe how object-oriented design supports encapsulation
Definition

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

 

Term

What are class diagrams used for?

Definition

Describes the static structure of classes in a software system

 

Term

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

 

Definition

O(log(n))

 

Term

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

 

Definition

O(log(n))

 

Term

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

 

Definition

O(n)

 

Term

 

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

 

Definition

 

Unbalanced / degenerate binary trees

 

Term

     What is a tree traversal?

 

Definition

Visiting all the nodes in a tree

 

Term

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

 

Definition

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

 

Term

True or False:

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

Definition
True
Term

True or False:

Pre-order traversals are faster than post-order traversals

Definition
False
Term

True or False:

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

Definition
False
Term

True or False:

Variables of type Integer and int are both references

Definition
False
Term

True or False:

Autoboxing creates an Integer object from an int

Definition
True
Term

true or False:

Exceptions are used to capture run-time errors          

Definition
True
Term

   What are two key properties of a heap?

 

Definition

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

 

Term

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

 

Definition

find largest key, find key with value k

 

Term

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

 

Definition

O(log(n))

 

Term

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

 

Definition

O(log(n))

 

Term

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

 

Definition

O(log(n))

 

Term

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

 

Definition

define variables, define methods

Term

1.      When is the finalize() method invoked?

 

Definition

When the object is garbage collected

Term

1.      Describe the Java Hash Code contract.

 

Definition

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

Term

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

Definition

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

 

Term

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

Definition

O(1)

Term

1.      When is the following assignment valid?

 

 

 

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

 

Definition

Never

Term

What is procedural abstraction?

Definition

Specifies what actions should be performed, hiding algorithms

Term

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);

 

   

 

}

 

Definition

      public void processInfo() {

 

                  int y = 20;

 

                  try {

 

                              int result = evaluate(y);

 

                              System.out.println(result);

 

                  }

 

                  catch(IllegalArgumentException e) {

 

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

 

                  }

 

      }

 

Term

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);

 

             }

 

 

 

Definition

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

 

                      new ExampleCheckedImp().generateResults();

 

          }

 

         

 

          public void generateResults() throws MyException {

 

                      computeValue(10);

 

          }

 

         

 

Term

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);   }

 

 

 

 

 

}

 

Definition

public class Col<T>        {

 

            private ArrayList<T> c;

 

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

 

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

 

}

 

 

 

 

 

 

 

Term

True or False:       Integration tests are applied after unit tests                                           

 

Definition
True
Term

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++)

 

Definition
O(n^2)
Term

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

 

Definition
False
Term

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

Definition
True
Term

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

Definition
False
Term

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

Definition
False
Term
What is Data Abstraction?
Definition
•Specify data objects for problem
•Hide representation
Term
What is a Checked Exception?
Definition
exceptions that must be caught or declared in a program
Term
What is an unchecked exception?
Definition
Serious errors that a typical program should not have to handle
Term

In MVC what does the model do?

 

Definition
•Should perform actual work
•Should be independent of the GUI
•But can provide access methods
Term

In MVC what does Controller do?

 

Definition
•Lets user control what work the program is doing
•Design of controller depends on model
Term
In MVC what does the View do?
Definition
•Lets user see what the program is doing
•Should not display what controller thinks is happening (base display on model, not controller)
Term

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

 

 O(nn) , O(n!) ,O(kn) , O(nk) ,

Definition

 

 

O(nk) , O(kn), O(n!), O(nn

Term

Bubble Sort

What is the AVG case complexity?

What is the worst case complexity?

In place?

Can be Stable?

Definition

AVG case complexity : O(n2)

Worst case complexity: O(n2)

In Place? YES

Can be Stable? YES

 

 

Term

Selection Sort

Average Case Complexity?

Worst Case Complexity?

In Place?

Can be stable?

Definition

Average Case Complexity: O(n2)

Worst Case Complexity: O(n2)

In Place: YES

Can be stable: YES

Term

Tree Sort

Average Case Complexity?

Worst Case Complexity?

In Place?

Can be stable?

 

Definition

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

Worst Case Complexity? O(n2)

In Place: NO

Can be stable: NO

 

Term

Heap Sort

Average Case Complexity?

Worst Case Complexity?

In Place?

Can be stable?

 

Definition

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

 

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

 

In Place? NO

 

Can be stable? NO

 

 

 

Term

Quick Sort

Average Case Complexity?

 

Worst Case Complexity?

 

In Place?

 

Can be stable?

 

 

 

Definition

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

 

Worst Case Complexity: O(n2)

 

In Place: YES

 

Can be stable: NO

 

 

 

Term

Merge Sort

Average Case Complexity?

Worst Case Complexity?

In Place?

Can be stable?

 

 

Definition

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

 

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

 

In Place: No

 

Can be stable: YES

 

 

 

Term
What does it mean for a Sorting Algorithim to be stable?
Definition
The relative order of EQUAL keys are unchanged
Term
How does Bubble sort work?
Definition
•Iteratively sweep through shrinking portions of list
•Swap element x with its right neighbor if x is larger
Term
How does Selection Sort work?
Definition
1.Iteratively sweep through shrinking portions of list
2.Select smallest element found in each sweep
3.Swap smallest element with front of current list
Term
How do you Tree Sort?
Definition
•Insert elements in binary search tree
•List elements using inorder traversal
Term
How do you heap sort?
Definition
1.Insert elements in heap
2.Remove smallest element in heap, repeat
3.List elements in order of removal from heap
Term
How do you quick sort?
Definition
1.Select pivot value (near median of list)
2.Partition elements (into 2 lists) using pivot value
3.Recursively sort both resulting lists
4.Concatenate resulting lists
5.For efficiency pivot needs to partition list evenly
Term
How do you Merge Sort?
Definition
1.Partition list of elements into 2 lists
2.Recursively sort both lists
3.Given 2 sorted lists, merge into 1 sorted list
•Examine head of both lists
•Move smaller to end of new list
Term
If a heap is represented as an Array, what is the parent of element at i-position in the array?
Definition
floor of (i-1)/2
Term
If a heap is represented as an Array, what is the position of the left child of the element at i-position in the array?
Definition
(2 x i) +1
Term
If a heap is represented as an Array, what is the position of the right child of the element at i-position in the array?
Definition
(2 x i) + 2
Term
Why do we want to study the software development process?
Definition
•Software development problems
•Why software projects fail
•Impact of software failures
•How to develop better software
Term
What does Software engineering require?
Definition
•Preparation before writing code
•Follow-up work after coding is complete
Term
What are the components of the software lifecycle?
Definition
1.Problem specification
2.Program design
3.Algorithms and data structures
4.Coding and debugging
5.Testing and verification
6.Documentation and support
7.Maintenance
Term
What are the advantages with using the Waterfall model?
Definition
•Simple
•Predictable results
•Software follows specifications
•Reasonable for small projects
Term
What are the problems associated with the Waterfall model?
Definition
•May need to return to previous step
•Steps may be more integrated
•Steps may occur at same time
•Unworkable for large projects
Term
What are the phases of the Unified model?
Definition
•Inception
•Elaboration
•Construction
•Transition
Term
What is clear box testing?
Definition
•Allowed to examine code
•Attempt to improve thoroughness of tests
Term
What is Black Box testing?
Definition
•No knowledge of code
•Treat program as “black box”
•Test behavior in response to inputs
Term
What are the THREE types of design patterns?
Definition
•Creational
•Deal with the best way to create objects
•Structural
•Ways to bring together groups of objects
•Behavioral
•Ways for objects to communicate & interact
Term
What are the 5 Creational design patterns?
Definition
1.Abstract Factory- Creates an instance of several families of classes
2.Builder - Separates object construction from its representation
3.Factory Method - Creates an instance of several derived classes
4.Prototype - A fully initialized instance to be copied or cloned
5.Singleton - A class of which only a single instance can exist
Term
What are the 7 types of Structural Design Patterns?
Definition
1.Adapter - Match interfaces of different classes
2.Bridge - Separates an object’s interface from its implementation
3.Composite - A tree structure of simple and composite objects
4.Decorator - Add responsibilities to objects dynamically
5.Façade - Single class that represents an entire subsystem
6.Flyweight - Fine-grained instance used for efficient sharing
7.Proxy - Object representing another object
Term
What are the 11 types of Behavioral Design patterns?
Definition

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

Term

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

Definition
•Adjacency matrix
•2D array of neighbors
•Adjacency list
•List of neighbors
•Adjacency set / map
•Set / map of neighbors
Term

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

Definition
False
Term

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

Definition
False
Term
What is a shallow copy?
Definition

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

Term

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

Definition
True
Term

Why do programmers use design patterns?

Definition

Benefit from design of experienced programmers

 

Term

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

 

Definition
True
Term

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

Definition
True
Term

(True or False) Java inner classes support encapsulation

Definition

True

 

Term

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

Definition
True
Term

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

Definition
True
Term

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

Definition
False
Term
(True or False)The View must inform the Model when its state changes                 
Definition
False
Term
(True or False) The Model must inform the View when its state changes
Definition
True
Term
What is an Initialization Block?
Definition
Block of code used to initialize static & instance variables for class
Term
Define Static initialization block
Definition
Code executed when class loaded
Term
Define Initialization block
Definition
•Code executed when each object created
• (at beginning of call to constructor)
Term
What are the advantages of an Array?
Definition
•Can efficiently access element at any position (O(1))
•Efficient use of space (space just to hold reference to each element)
Term
What are the disdadvantages of an Array?
Definition
•Expensive to grow / shrink array
•Can amortize cost (grow / shrink in spurts)
•Expensive to insert / remove elements in middle (O(n))
•Tricky to insert / remove elements at both ends
Term
Advantages of a LinkedList
Definition
•Can efficiently insert / remove elements anywhere
Term
Disadvantages of a LinkedList
Definition
•Cannot efficiently access element at any position
•Need to traverse list to find element (O(n))
•Less efficient use of space
•1-2 additional references per element
Supporting users have an ad free experience!