UTS 31251 Data Structures and Algorithms Subject Notes

Summary:

The Data Structures and Algorithms note covers various topics in computer science such as Algorithm, C/C++, Java, Strings, Arrays, Pointers, References, Classes, I/O, Destructors, Templates, Stacks, Queues, Vectors, Iterators, Algorithm Analysis, Divide and Conquer, Recursion, Master Theorem, Graphs, Traversing Graphs, Greedy Algorithms, Binary Trees, Heaps, Sorting Algorithms, Maps, Hashing, Collisions Map, Dynamic Programming, Shortest Paths, Topological Sorting, String Search, Rabin-Karp Algorithms, and Computational Complexity.

Excerpt:

Data Structures and Algorithms

…

Iterators

• Iterators (or limited pointers) are used to point at the memory addresses of STL containers
• They are primarily used in the sequence of numbers, characters, etc.
  • iterator: random-access containers
  • bidirectional iterator: non-random-access containers
• Reduce the complexity and execution time of the program
• Benefits:
  • A flexible way to access data in containers that don’t have obvious means of accessing all of the data (e.g., maps)
  • STL algorithms defined in use iterators
• Negatives:
  • No boundary check
  • Can be invalidated if the underlying container is changed significantly

Container Adaptors

• Container Adaptors are classes that use an encapsulated object of a specific container class as its underlying container, providing a specific set of member functions to access its elements
  • queue: based on deque or list
  • priority queue: based on vector or deque
  • stack: based on deque, vector, or list
• Example: queue<int, list<int=””> > q;</int,>

Algorithm Analysis

• Two algorithms to solve the same problem, interested in:
  • Time Complexity: how long they take
  • Space Complexity: How much space they take up
• Reliably compare algorithms:
  • Testing gives good information –> limited to the cases tested and can be
    resource-intensive
  • Big-O notation: upper-bound of algorithms’ time complexity
    • In the abstract sense, running time is really the number of steps the
      the algorithm takes for a given input size –> count the number of steps
• Which algorithm’s time consumption grows faster

Big-O Notation

• Given two functions ƒ and g, we say ƒ is in big-O of g (denoted by ƒ 0(g)) if: , N such that, we have
  • That means: given a big enough number n, f(n) is less than or equal to the
    constant times of g(n)