Software Engineering Flashcards
Big o notation for 000.5n^3
n^3 we ignore all smaller terms, do some big O exampels
BIG 0 order
2^N>n^3>N^2logn>N^2>NlogN>n>1(constant)
Big O, O(x+Y)
the greater of x or y
Big) (XY)
OxOy
Bubble sort
start at index o
compare with item next to you. if its less than you, swap,
incriment.
repeat whole list until there are no swaps
total passes for bubble sort of n length
n(n-1)/2
bubble sort time
best O(n)
avg n^2
worst n^2
Insertion sort
assume first item is sorted.
place the next item in the correct spot for the sorted section.
increase the sorted seciton
total passes for insertion sort
n-1
insertion sort time
best n
worst n^2
avg n^2
selection sort
The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.
seleciton sort time
n^2 all
merge sort
Find the middle point to divide the array into two halves:
middle m = (l+r)/2
2. Call mergeSort for first half:
Call mergeSort(arr, l, m)
3. Call mergeSort for second half:
Call mergeSort(arr, m+1, r)
4. Merge the two halves sorted in step 2 and 3:
Call merge(arr, l, m, r)
merge sort timing
nlogn for all
Pivot sort
Pick a “pivot”
- Divide into less-than & greater-than pivot
- Sort each side recursively
Binary search
Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you’ve narrowed down the possible locations to just one
benefits of linked lists
no needed size, dynamic, timing is all On but o1 for insert at end
GO OVER CREATION AND ALGORITHM STUFF
adding data to stack
Go over stack stuff
push and pop affect stuff on top only
enqueue
getting into the queue
dequeue
gettingout of the querye, have been served
peek
The peek() method of Queue Interface returns the element at the front the container. It does not deletes the element in the container.
queue follows
FIFO
in order tree traversal
visit left subtree, then root then right
pre order tree traversal
visit current node, then left, then right
post order tree traversal
traverse left, then right then root.
BFS
used for traversing a graphs by visiting all unvisited nodes adjacent to start. then repeating for the adjacent nodes in same order
DFS
visiting one adjacent node and then the next as deep as possible and then backtracking until there is anothe optioon, look at sol on guide
Rigiid
software hard to change
fragile
software prone to breaking in multiple places upon change
portible
software that can be used in dif environments
immobile
software that is difficult to re-use
static software testing
verification through code review, walkthroughs and inspecitons
glass box/white box testing
detailed investigation of the internals of the software. everything is transparent
black box testinng
tester only cares about outcomes and inputs, no access to code itself is needed
unit testing
dyunamicallyu executing unids of code to verify individual performance
waterfall mdoel
linear, predetermiend phases and milestones. googhle it
