Algorithms & Complexity

Algorithms & Complexity

1. Growth rate & efficiency

   • Efficiency
     • Resources
       • Time
       • Space
       • Fn of input size
         • Average/worst case
           • Best/Amortised
         • Empirical
         • Theoretical
   • Running time dependencies
     • 1. Complexity
       • 2. Input
         • 3. Memory architecture
           • 4. Language/Compiler/OS
     • Estimate time consumption
       • Run time: FORMULA
         • Basic operation
           • Cost, C
           • Input size, n
             • No of times operation performed, g(n)
   • Growth rate comparisons
     • Ignore: constants, small n
     • GRAPH
     • Bounds of complexity
       • Big-Oh
         • Upper bound
           • GRAPH
       • Big-Omega
         • Lower bound
           • GRAPH
       • Big-Theta
         • Precise bound
           • GRAPH

2. Algorithms

   • Unambiguous instructions
     • Finite i/o
       • Solves family of instances
   • Problem solving steps
     • 1. Understand
       • 2. Computational means
         • 3. Method
           • 4. Data structure & algo design
             • 5. Check correctness
               • 6. Evaluate analytically
                 • 7. Code
                   • 8. Empirical evaluation
   • Euclid's Algo
     • GCD
       • Modulus
   • Data structures
     • Stack
       • Queue
         • Priority queue
           • Tree
             • Graph
         • FIFO
       • LIFO
     • Abstract data types
     • Array
       • Pros/Cons
     • Linked list
       • Node
         • Pointer
           • Y.val/Y.next
     • Iterative
       • Recursive
   • Pseudocode
     • Assignment <-
       • Comment //
   • Bits
     • Bytes
       • 8 bits
     • MSB, LSB
     • Number to binary
       • Quotient, Remainder
     • 0 1

Imágenes y archivos del mapa