Software Engineering Flashcards
Abstract Class
Intentionally incomplete class definition; has some members declared ‘abstract’ and children must implement them; objects cannot be created
Encapsulation
Implementation should be completely separate from the interface
Child Class
A class that extends another class
Aggregation
has-a relationship; contained object can survive without the container
Immutable
A value that cannot be changed
Inheritence
Ability of a class to duplicate its parent’s members
Instance
An object that has been created from a class
Interface
Supplies definition for methods - kind of like a .h file
Composition
is-a relationship; contained object cannot survive without the container
Polymorphism
Allows a child class to be used anywhere a method requires the parent class
Private
Only the class itself can read/write
Protected
Only the class itself and children can read/write
Public
Anything can read/write
Uses-A
Relationship between objects that call methods and use member variables of other objects
Object Based vs Object Oriented
Object based has no inheritence
Association
One object uses another but does not own it
Virtual member
Expected to be implemented in subclasses
Function Overloading vs Overriding
Overloading has different parameters, Overriding has same signature but different implementation
Priority inversion
Medium priority task preempts a high priority task
Hash Table
Use a mathematical function to take the key and transform it to the domain of an array; resolve collisions by Chaining or OpenAddressing (use an array and fill in empties nearby)
Linked List
Elements chained together using pointers
Queue
Uses a linked list, FIFO
Stack
Uses a linked list, LIFO
Heap
Nearly complete binary tree where parent >= child; Heapify (maintain heap structure, O(lg n)); BuildHeap (creates heap from array, O(n)); HeapSort (sorts array in place, O(n lg n)); ExtractMax O(lg n); Insert O(lg n)
Binary Search Tree
Left Child < Parent <= Right Child
Red-Black Tree
Balanced Binary Search Tree uses colors
Graph
Set of vertices and edges (with possible directions and weights)
Bubble Sort
Iterate and swap pairs, iterate again on one less item, etc – O(n^2)
Selection Sort
Iterate and select the smallest, then second smallest, etc – O(n^2)
Insertion Sort
Cascade items successively into place - Best O(n) if already sorted; Worst O(n^2)
Merge Sort
Recursively split on a pivot then merge the arrays back up into sorted order - O(n lg n)
Heap Sort
Builds a heap then exchanges elements to push down O(n lg n) - NOT STABLE
Quicksort
Split into two arrays (greater than pivot, less than pivot) and recurse - worst case O(n^2), best case O(n lg n)
Counting Sort
Only for integers with known maximum; count the occurences of 1s, 2s, etc - O(n)
Radix Sort
Uses another stable sort on each digit - O(n)
Bucket Sort
Uses equal size buckets across [0, 1) - O(n)
Coffman Condition 1
Mutual exclusion - a resource can’t be shared
Coffman Condition 2
Resource holding - a process is holding one resource and is requesting more
Coffman Condition 3
No preemption - the process itself must release resources
Coffman Condition 4
Circular wait - the processes are waiting on each other to release resources
Dynamic Programming
Optimizing the solution based on the data - ex. Multiplying matrices in a different order
Breadth First Search
Finds the minimum distances from one source to all edges O(V+E)
Depth First Search
Marks up the graph
Pre/Post/In Order Traversal
Pre = N L R, In = L N R, Post = L R N
Topological Sort
Performs DFS to get order of dependencies
NP-Complete
Cannot be completed in polynomial time (exponential)
Memory segmentation
Data - initialized variables, BSS - uninitialized variables, Heap - area for dynamic allocation, Stack - function calls and automatic variables
Semaphore vs Mutex
Mutex same as binary semaphore. Mutex tracks the owner process that locked it
Rendezvous
Used in multi-threading to pause a thread until other threads reach a certain execution point
Race Condition
Output is dependent on the sequence or timing of threads
Interprocess Communication Methods
Shared memory, file system, pipe, socket
Singleton
Only one instance of a class exists
How inheritance looks on class diagram
Arrow from derived to base with solid line and unfilled head
Two-way association on class diagram
solid line with multiplicity on each side and member names on opposite sides
One-way association on class diagram
Skeleton arrow with solid line pointing to class that is known about
Aggregation on class diagram
Skeleton arrow container to contained with unfilled diamond on container
Composition on class diagram
Skeleton arrow container to contained with filled diamond on containter
