Module 6

KA Topics:

• Differences among best, expected, and worst case behaviors of an algorithm

• Asymptotic analysis of upper and expected complexity bounds

• Big O notation: formal definition

• Complexity classes, such as constant, logarithmic, linear, quadratic, and exponential

• Empirical measurements of performance

• Time and space trade-offs in algorithms

KA Learning Outcomes:

1. Explain what is meant by “best”, “expected”, and “worst” case behavior of an algorithm.

2. In the context of specific algorithms, identify the characteristics of data and/or other conditions or assumptions that lead to different behaviors. [Assessment]

3. Determine informally the time and space complexity of simple algorithms. [Usage]

4. State the formal definition of big O. [Familiarity]

5. List and contrast standard complexity classes. [Familiarity]

6. Perform empirical studies to validate hypotheses about runtime stemming from mathematical analysis. Run algorithms on input of various sizes and compare performance. [Assessment]

7. Give examples that illustrate time-space trade-offs of algorithms. [Familiarity]

Algorithmic Strategies

KA Topics:

• Brute-force algorithms

• Greedy algorithms

• Divide-and-conquer (cross-reference SDF/Algorithms and Design/Problem-solving strategies)

• Recursive backtracking

• Dynamic Programming

KA Learning Outcomes:

1. For each of the strategies (brute-force, greedy, divide-and-conquer, recursive backtracking, and dynamic programming), identify a practical example to which it would apply. [Familiarity]

2. Use a greedy approach to solve an appropriate problem and determine if the greedy rule chosen leads to an optimal solution. [Assessment]

3. Use a divide-and-conquer algorithm to solve an appropriate problem. [Usage]

4. Use recursive backtracking to solve a problem such as navigating a maze. [Usage]

5. Use dynamic programming to solve an appropriate problem. [Usage]

6. Determine an appropriate algorithmic approach to a problem. [Assessment]

Fundamental Data Structures and Algorithms

KA Topics:

• Simple numerical algorithms, such as computing the average of a list of numbers, finding the min, max, and mode in a list, approximating the square root of a number, or finding the greatest common divisor

• Sequential and binary search algorithms

• Worst case quadratic sorting algorithms (selection, insertion)

• Worst or average case O(N log N) sorting algorithms (quicksort, heapsort, mergesort)

• Hash tables, including strategies for avoiding and resolving collisions

• Binary search trees

  • Common operations on binary search trees such as select min, max, insert, delete, iterate over tree

• Graphs and graph algorithms

  • Representations of graphs (e.g., adjacency list, adjacency matrix)

  • Depth- and breadth-first traversals

KA Learning Outcomes:

1. Implement basic numerical algorithms. [Usage]

2. Implement simple search algorithms and explain the differences in their time complexities. [Assessment]

3. Be able to implement common quadratic and O(N log N) sorting algorithms. [Usage]

4. Describe the implementation of hash tables, including collision avoidance and resolution. [Familiarity]

5. Discuss the runtime and memory efficiency of principal algorithms for sorting, searching, and hashing. [Familiarity]

6. Discuss factors other than computational efficiency that influence the choice of algorithms, such as programming time, maintainability, and the use of application-specific patterns in the input data. [Familiarity]

7. Explain how tree balance affects the efficiency of various binary search tree operations. [Familiarity]

8. Solve problems using fundamental graph algorithms, including depth-first and breadth-first search. [Usage]

9. Demonstrate the ability to evaluate algorithms, to select from a range of possible options, to provide justification for that selection, and to implement the algorithm in a particular context. [Assessment]