GoConqr has a new look! Let us know what you think.

Sign up free

Flashcards

COSC241

Tom Weatherall English 55 cards

Cards in this deck (55)

  1. 1Simple Loop from 0 - nO(n)
  2. 2Nested Loop of the Same typeO(n^2)
  3. 3Selection SortO(n^2)
  4. 4Insertion SortO(n^2)
  5. 5Quick SortO(n^2)
  6. 6Divide & Conquer AlgosO(nlogn)
  7. 7Merge SortO(nlogn)
  8. 8Heap SortO(nlogn)
  9. 9sqrt(n), logn, 1, n^2, nlogn, n^3, 2^n1, logn, sqrt(n), n, nlogn, n^2, n^3, 2^n
  10. 10What is an interface?a collection of abstract methods and constants
  11. 11What is an algorithm?a description of a series of basic steps that achieve some specified result
  12. 12References as links-a java reference, refers to a memory location in which complete data for an object is stored
    -a reference to an object of the same type is often called a link
  13. 13What is a linked list?-a sequence of nodes connected by links
  14. 14Static data structure?-structure is fixed at the time it is created and cannot be changed
  15. 15Dynamic data structure?structure can change
  16. 16True Random numbers?generated by observation of some unpredictable physical process
  17. 17What is a collection?-an object that gathers and organises other objects
    -defines the way in which those elements can be accessed and managed
    -specifies the way in which the user may interact with the collection
  18. 18ADT?an abstract data type is a data type whose intended use is specified by its interface
  19. 19Data structure?the collection of programming structures (methods, data fields) used to implement an ADT
  20. 20Queue ADTa queue is an abstract data type that represents item processing in a first in first out manner
  21. 21Divide & Conquer?-Pre: break the problem apart into two or more smaller problems
    -Rec: solve the problems recursively
    -Post: combine those solutions into a solution of the original problem
  22. 22Heaps?-a heap is a tree where the values stored are comparable which satisfies certain additional restrictions
    -the value stored at a node is always greater than or equal to the value stored at any of its children
    -each node has at most two children
  23. 23Priority Queue?-each element is added with an associated priority
    -when an element is removed it is the highest element with the highest priority
  24. 24What is recursion?the repeated application of a recursive procedure or definition
  25. 25Formal f(n) = O(g(n))If for some constant A f(n) is less than or equal to Ag(n)
  26. 26Linear Search of Arrayif nothing is know about the array we have to look at each element until we find the right one
    -gives O(n)
  27. 27Binary Search of Array?-Check the midpoint – this either finds the value or gives us a new range to search in which is only half the size.
    -Implement recursively.
  28. 28Selection Sort- Find the smallest item in the list. Swap it with the first item.
    - Find the smallest item in the remainder of the list, swap it with the first item of the remainder.
    - Repeat until finished.
  29. 29Insertion Sort-Process the array one element at a time.
    -Insert each new element into its correct position among the previously processed elements.
  30. 30Quick Sort-Choose one of your data items called the pivot.
    -Split the remaining data into the items smaller than the pivot and the items larger than (or equal to) the pivot.
    -Put all the small items before the pivot and all the large items after the pivot.
    - Sort those two groups individually
  31. 31Merge Sort-Split array down to sub-arrays of two
    -sort the sub-arrays
    -merge the array
    - one way to speed up to algo is to delegate to insertion sort when right - left is less than some pre-set threshold
  32. 32Heap Sort-Organize the elements of the array into a heap structure.
    - Exchange the first (largest) element, and the last element.
    - Restore the heap structure (except for the final element).
    - Repeat last two steps until finished.
  33. 33Why are random numbers importantUsed in; game playing; simulation and testing; security; cryptography and communication protocols
  34. 34Psuedo-Randomnumbers are generated as a sequence
    by a specific deterministic mathematical algorithm called a pseudo-random number generator
  35. 35Shuffling an Array- Exchange the last card with some earlier item or itself, then
    - exchange the second last card with some earlier card or itself, then
    - exchange the third last item with some earlier item or itself
    -Keep Going
  36. 36Dealing a handshuffle the array, and then use the first, or last, k (if we do this right, then we don’t need to complete the shuffle - we can stop when the required elements are in place).
  37. 37Advantages of ADTs?The data structure that implements an ADT can be changed without changing the interface, and therefore in a way that does not affect any client programs
  38. 38StackA LIFO collection
  39. 39Queuean abstract data type that represents item
    processing in a first in, first out manner
  40. 40Similarities between stack and queue?-Same basic operations
    -Stack is LIFO
    -Queue is FIFO
  41. 41Significance of Generic Typesuseful, indicating in a class that “you could have objects of any type here” but where that type might be used in e.g., method parameters or returns
  42. 42Issues with multiple linking?-hard to get to work properly
    -difficult to add and remove nodes
  43. 43Divide and Conquer algo complexityTotal work done is (work per layer O(n)) times (number of layers O(logn))
    and is O(n log n)
  44. 44Why remove recursion?- When a method call is made, the complete state of the current method must be stored (since it might all be needed) and then restored when the called method exits.
    - Insertion sort becomes very quick in small data sets
  45. 45What is a heap?A heap is a tree where the values stored are comparable which satisfies certain additional restrictions
  46. 46Characteristics of a Heap- value stored at a node is always greater than or equal to the value stored at any of its children
    - each node has at most two children
    - it is a complete tree
  47. 47Operations a Heap supports- Adding an item,
    - Returning the maximum value in the heap,
    - Removing the maximum value from the heap
  48. 48Adding an item to a heap- Place the item to be added in the first vacant leaf position.
    - Let it float up the branch towards the root so long as it is larger than its parent
  49. 49Removing the maximum- maximum is always at the root of the heap
    - Replace the root value with the value of the last leaf
    -Then to re-establish the heap property exchange the root and the larger of its children (and do this recursively downwards)
  50. 50Priority Queue- each element is added with an associated priority
    -When an element is removed, it is the element with highest priority
  51. 51Double recursion callsThe double recursive call creates an exponential blow up in the number of actual method calls
  52. 52How to better Insertion Sort◮ When the time comes to insert the element from position i the previous elements are sorted and those greater than a[i] need to be moved forward.
    ◮ So, read backwards from position i, moving elements forward until the necessary hole is created into which we
    can place the value a[i] (which we need to store in advance since it will be written over in the first step).
  53. 53Characteristic that makes divide and conquer litThe sub-problems should be a constant fraction smaller
    than the main problem and the work required to create and
    combine them should be linear
  54. 54Weakness of Quick Sort- if the data is already sorted the sub-problems are of size 0 and n − 1
    - then you have to recurse through those
  55. 55What do generic types allow us to do?define a class so that it stores, operates on, and manages objects whose type is not specified until the class is instantiated

Information

Description
Flashcards on COSC241, created by Tom Weatherall on 28/05/2019.
Created by
Tom Weatherall
Views
1
Rating

Feedback

What is it about?

What do you think of the new look?

How do you like it?