AlgorithmsDefinition  unambiguous procedure executed in a finite number of steps  What makes a good algorithm?  Correctness, Speed, Space, Simplicity  Speed:  time it takes to solve problem  Space:  amount of memory required  Simplicity:  easy to understand, easy to implement, easy to debug, modify, update 
Running TimeDefinition  measurement of the speed of an algorithm  Dependent variables:  size of input & content of input  Best Case:  time on the easiest input of fixed size  meaningless  Average Case:  time on average input  good measure, hard to calculate  Worst Case:  time on most difficult input  good for safety critical systems, easy to estimate 
Proofs by Induction (Examples)
Loop InvariantsDefinition  loop property that holds before and after every iteration of a loop.  Steps:  1. Initialization  If it is true prior to the iteration of the loop  2. Maintenance  If it is true before an iteration of the loop, it remains true before the next iteration  3. Termination  When the loop terminates, the invariant gives us a useful property that helps show the algorithm is correct 
QuickSortDivide:  choose an element of the array for pivot   divide into 3 subgroups; those smaller, those larger and those equal to pivot  Conquer  recursively sort each group  Combine  concatenate the 3 lists 
QuickSortAlgorithm partition(A, start, stop)
Input: An array A, indices start and stop.
Output: Returns an index j and rearranges the elements of A
such that for all i<j, A[i] ! A[j] and
for all k>i, A[k] " A[j].
pivot # A[stop]
left # start
right # stop  1
while left ! right do
while left ! right and A[left] ! pivot) do left # left + 1
while (left ! right and A[right] " pivot) do right # right 1
if (left < right ) then exchange A[left] $ A[right]
exchange A[stop] $ A[left]
return left

Time Complexities:
• Worse case:
– Already sorted array (either increasing or decreasing)
– T(n) = T(n1) + c n + d
– T(n) is O(n2)
• Average case: If the array is in random order, the
pivot splits the array in roughly equal parts, so the
average running time is O(n log n)
• Advantage over mergeSort:
– constant hidden in O(n log n) are smaller for quickSort.
Thus it is faster by a constant factor
– QuickSort is easy to do “inplace”
In Place SortingDefinition:  Uses only a constant amount of memory in addition of that used to store the input  Importance:  Great for large data sets that take up large amounts of memory  Examples:  Selection Sort, Insertion Sort (Only moving elements around the array)  MergeSort:  Not in place: new array required 
  Object Orientated ProgrammingDefinition:  User defined types to complement primitive types   Called a class  Contains:  Data & methods  Static members:  members shared by all objects of the class 
Recursion ProgrammingDefinition  using methods that call themselves  Structure:  base case  a simple occurrence that can be answered directly  recursive case  A more complex occurrence of the problem that cannot be directly answered, but can instead be described in terms of smaller occurrences of the same problem. 
Divide & ConquerDivide  the problem into sub problems that are similar to the original but smaller in size  Conquer  the subproblems by solving them recursively. If they are small enough, solve them in a straightforward manner  Combine  the solutions to create a solution to the original problem 
BIG O Definitionf(n) & g(n) are two non negative functions defined on the natural numbers N  f(n) is O(g(n)) if and only if:  there exists an integer n0 and a real number c such that Ɐn>= n0 f(n) <= c * g(n)   N.B. The constant c must not depend on n 
Big O RecurrenceSum of a^{i from 0 to n = (a}(n+1) 1 )/(a1)
Limitations of ArraysSize has to be known in advance  memory required may be larger than number of elements  inserting or deleting an element takes up to O(n) 
ADT: QueuesFIFO(First in first out)  Any first come first serve service  Operations  enqueue()  add to rear   dequeue()  removes object at front   front()  returns object at front   size()  returns number of objects O(n)   isEmpty()  returns true if empty 
Double Ended Queues(deque): Allows for insertions and removals from front and back
 By adding reference to previous node  removals occur in O(1)
ATD: StacksDef:  Operations allowed at only one end of the list (top)   LIFO: (Last in first out)  Operations:  push()  inserts element at top   pop()  removes object at top   top()  returns top element without removing it   size()  returns number of elements   isEmpty()  returns True if empty  Applications  page visited history in web browser   JVM  keeps track of chain of active elements (allows for rec)  Performance:  space used: O(n)   operations: O(1)  Limitations  max size must be defined prior   pushing to a full stack causes implementation specific error 
  BinarySearchBinarySearch(A[0..N1], value) {
low = 0
high = N  1
while (low <= high) {
mid = (low + high) / 2
if (A[mid] > value)
high = mid  1
else if (A[mid] < value)
low = mid + 1
else
return mid
}
return not_found // value would be inserted at index "low"
}

Invariants:
value > A[i] for all i < low value < A[i] for all i > high
Worst case performance: O(log n)
Best case performance: O(1)
Average case performance: O(log n)
BinarySearch (Recursive)int bsearch(int[] A, int i, int j, int x) {
if (i<j) {
int e = [(i+j)/2];
if (A[e] > x) {
return bsearch(A,i,e1);
} else if (A[e] < x) {
return bsearch(A,e+1,j);
} else {
return e;
}
} else { return 1; }
}

Time Complexity: log(base2)(n)
Insertion Sort (Iterative)For i ← 1 to length(A)  1
j ← i
while j > 0 and A[j1] > A[j]
swap A[j] and A[j1]
j ← j  1
end while
end for

Time complexity: O(n^{2})
  MergethensortAlgorithm ListIntersection (A,m, B,n)
Input: Same as before
Output: Same as before
inter ← 0
Array C[m+n];
for i ← 0 to m1 do C[i] ← A[i];
for i ← 0 to n1 do C[ i+m ] ← B[i];
C ← sort( C, m+n );
ptr ← 0
while ( ptr < m+n1 ) do {
if ( C[ptr] = C[ptr+1] ) then {
inter ← inter+1
ptr ← ptr+2
}
else ptr ← ptr+1
}
return inter

Time Complexity: (m+n) * (log(m+n)) + m + n 1
MergeSort (Recursive)MergeSort (A, p, r) // sort A[p..r] by divide & conquer
if p < r
then q ← ⎣(p+r)/2⎦
MergeSort (A, p, q)
MergeSort (A, q+1, r)
Merge (A, p, q, r)

Time Complexity: 2T(n/2) + k • n + c’
Primitive Operationsassignment  calling method  returning from method  arithmetic  comparisons of primitive types  conditional  indexing into array  following object reference 
Assume each primitive operation holds the same value = 1 primitive operation

Created By
Metadata
Favourited By
Comments
No comments yet. Add yours below!
Add a Comment