Final Flashcards
Cyclomatic Complexity
Software metric used to measure complexity of a program
Asymptotic Analysis
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
NP problem
a problem for which it’s quick to check if an answer is correct.
NP-hard problem
a problem such that, if you have a strategy to solve it, you can quickly apply that strategy to any problem in NP.
NP-complete problem
a problem that is both NP and NP-hard.
Design pattern
proven solution to a recurrent problem in a context
Why study design patterns?
-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
OO Design Principles
Encapsulation
Information Hiding
Object Reuse
OO Design Principles - Encapsulation
-Bundling of data with operations that operate on that data.
-It’s a language facility / construct.
-It’s not specific to just OO programming.
OO Design Principles - Information Hiding
-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
OO Design Principles - Object Reuse
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
Disadvantages of Reuse with Inheritance
-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
Reuse with Composition
**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
Design - Module Cohesion
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.
Design - Module Coupling
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
Describing design patterns
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
Catalog of Design Patterns
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
Singleton Pattern
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
Example of Singleton Code
public class Singleton {
private static Singleton instance = null;
private Singleton() {}
public static Singleton getInstance(){
if(instance == null)
instance = new Singleton();
return instance;
} }
Facade Pattern
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.
UML
UML is a language for visualizing, specifying, constructing, documenting the artifacts of a software system,
Building blocks of UML
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
Structure UML Diagrams
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)
Behavior UML Diagrams
show the dynamic behavior of objects and other things in a system (ex: use case diagram)
