Final

Question 1

Cyclomatic Complexity

Answer 1

Software metric used to measure complexity of a program

Question 2

Asymptotic Analysis

Answer 2

1 - Find the largest element in an ordered list

Log(N) - we can discard some portion of the space repeatedly, ex: binary search

N - process each element some constant number of times (ex: find the largest number in an unordered list

N Log(N) - break the problem up into sub problems and recombine the solution, ex: sorting

N^2 - naive implementation to find the closest set of points in an unordered list

2^N - try every single combination and see if it is right

Question 3

NP problem

Answer 3

a problem for which it’s quick to check if an answer is correct.

Question 4

NP-hard problem

Answer 4

a problem such that, if you have a strategy to solve it, you can quickly apply that strategy to any problem in NP.

Question 5

NP-complete problem

Answer 5

a problem that is both NP and NP-hard.

Question 6

Design pattern

Answer 6

proven solution to a recurrent problem in a context

Question 7

Why study design patterns?

Answer 7

-Reuse existing, high quality solutions to commonly recurring problems
-Establish common terminology to improve communications within teams
-Improve modifiability and maintainability of code
-Adoption of improved object oriented design strategies

Question 8

OO Design Principles

Answer 8

Encapsulation
Information Hiding
Object Reuse

Question 9

OO Design Principles - Encapsulation

Answer 9

-Bundling of data with operations that operate on that data.
-It’s a language facility / construct.
-It’s not specific to just OO programming.

Question 10

OO Design Principles - Information Hiding

Answer 10

-Strives to shielf client modules from the internal works of a module.
-Creator stressed hiding “difficult design decisions or design decisions which are likely to change”
-Encapsulation facilitates but does not guarantee information hiding

Rules: don’t expose data, don’t expose the diff between stored and derived data (ex: use an accessor method named speed() or getspeed() rather than calculateSpeed() to return an attribute called speed of an object
Don’t expose a class’ internal structure or implementation details of a class

Question 11

OO Design Principles - Object Reuse

Answer 11

Class inheritance-reuse by sub-classing/extending/inheriting. Often referred to as white-box reuse

Object composition-new functionality is obtained by creating an object composed of other objects, black-box reuse

The generalization class (superclass) explicitly captures the common attributes and methods
The specialization class (subclass) extends the implementation with additional attributes and methods

Question 12

Disadvantages of Reuse with Inheritance

Answer 12

-Breaks encapsulation since it exposes a subclass to implementation details of its superclass
-“Whte-box reuse” since internal details of superclasses are often visible to subclasses
-Subclasses may have to be changed if the implementation of the superclass changes

Question 13

Reuse with Composition

Answer 13

**re-do thie one closer to final
New functionality is obtained by delegating functionality to one of the objects being composed
Object composition is defined dynamically at run time through objects acquiring references to other objects

Question 14

Design - Module Cohesion

Answer 14

Degree of relatedness/similarity between elements within a module. It is an intra-module measure.

Levels of Cohesion:
Functional: the perform a single specific funtion
Clustered, Sequential, Communicational, Procedural, Temporal, Logical, Coincidental.

Modules with high cohesion tend to be more maintanable and reusable.

Question 15

Design - Module Coupling

Answer 15

degree of dependence between two or more modules.

Types:
Data: all communications between modules is through data element arguments
Stamp: communication includes a data structure arguments (some fields are not needed)
Control: an argument from a module can control the flow of the other for example a flag
External: they reference an externally declared data element
Common: they reference an externally declared data structure
Content: one references the contents of the other

Question 16

Describing design patterns

Answer 16

Intent: design issue being addressed
Structure: A graphical rep in UML of the classes in the pattern
Participants: Classes participating in the pattern and their responsbilites
Collaborations: How participants collaborate to carry out their responsibilites
Consequences: Trade-offs and results of using the pattern
Implementation: Techniques, hints, or pitfalls to be aware of when implementing as well as sample code

Question 17

Catalog of Design Patterns

Answer 17

Creational-Abstract the instantiation process, define classes to handle object creation

Structural-concerned with how classes and objects are composed to form larger structures. Describe ways to compose objects to realize new functionality

Behavioral-Concerned with algorithms, flow of control, and assignment of responsibilities between objects. Describe how a group of objects cooperate to perform a task

Question 18

Singleton Pattern

Answer 18

Category: CREATIONAL

Intent: Ensure a class only has one instance, and provide a global point of access to it

Prob Addressed: Ensuring that a class is instantiated only once, and that the resulting object is readily accessible

Solution: Make the class itself responsible for instantiation and knowing whether it has been instantiated

Implementation: Add a private static member of the class that refers to the desired object (initially, it is null). Add a public static method that instantiates this class if this member is null. Sets the constructor’s visibility to private so that nobody can directly instantiate this class (except a child class if protected) and bypass the static constructor mechanism (i.e the public static method)

Consequences: Controlled access to sole instance, easily adapted to permit a fixed number of instances greater than one

Question 19

Example of Singleton Code

Answer 19

public class Singleton {
private static Singleton instance = null;

private Singleton() {}

public static Singleton getInstance(){
     if(instance == null)
          instance = new Singleton();
     
      return instance; 
 } }

Question 20

Facade Pattern

Answer 20

Category: STRUCTURAL

Intent: Provide a unified interface to a set of interfaces in a subsystem. Facade defines a unified higher level interface that makes the subsystems easier to use

Problem Addressed: Using design patterns often leads to a complex system of many small components which may be daunting for the casual user. It would be nice if there were a way to provide a simple interface for the basic functionality that is needed most often.

Solution: Create a Facade class that encapsulates the basic functionality of the system by bundling together common operations

Consequences- simplifies use of the system, shields users from subsystems components, limiting the number of objects that the user must deal with. Does not limit “power users”: serves as a convenience layer for general users without limiting access to subsystem components for those that desire or need more customizable uses

Can be applied with you do not need to use all the functionality of a complex system, you want to encapsulate or hide the original system, you want to extend the functionality of the original system.

Question 21

UML

Answer 21

UML is a language for visualizing, specifying, constructing, documenting the artifacts of a software system,

Question 22

Building blocks of UML

Answer 22

Things: these are first class citizens in a model (ex: class in a class diagram)

Relationships: the “things” together

Diagrams: graphical representations of interesting collections of things along with relationships

Two major kinds of diagrams - structure and behavior

Question 23

Structure UML Diagrams

Answer 23

show the static structure of the system and its parts at different abstraction and implementation levels and how the parts are related to each other (ex: class and object diagrams)

Question 24

Behavior UML Diagrams

Answer 24

show the dynamic behavior of objects and other things in a system (ex: use case diagram)