[prev] 180 [next]

Summary

  • Big-Oh notation
  • Asymptotic analysis of algorithms
  • Examples of algorithms with logarithmic, linear, polynomial, exponential complexity
  • Linked lists vs. arrays
  • Pointers
  • Memory management
    • malloc()
      • aim: allocate some memory for a data object
        • the location of the memory block within heap is random
        • the initial contents of the memory block are random
      • if successful, returns a pointer to the start of the block
      • if insufficient space in heap, returns NULL
    • free()
      • releases a block of memory allocated by malloc()
      • argument must be the address of a previously dynamically allocated object
  • Dynamic data structures

  • Suggested reading:
    • big-Oh notation … Sedgewick, Ch. 2.1-2.4, 2.6
    • pointers … Moffat, Ch. 6.6-6.7
    • dynamic structures … Moffat, Ch. 10.1-10.2
    • linked lists, stacks, queues … Sedgewick, Ch. 3.3-3.5, 4.4, 4.6