Midterm 2 Information - CompSci 161 - Winter, 2025 (Dillencourt)

For general information about test rules and the test format, click here.

NOTE: This is the finalized version.

List of topics

The test will cover the material covered in the first five sets of lecture notes and the sixth set of lecture notes up through and including slide 6-38.

The following is a list of topics that may be covered on Midterm 2. It lists the primary coverage area of this test. The test will not contain questions that focus exclusively on earlier material, but some knowledge of earlier material may be necessary. Midterm 1 covered up through the material on comparison-based sorting, so the primary coverage area of Midterm 2 starts with the next topic after that, which is address-calculation sorting.

Note: There may be questions about the mechanics of algorithms that were covered in the lectures and in the lecture notes. For these questions, you will need to know the algorithms as described in the lectures and in the lecture notes.

• Address-calculation sorting:
  • Counting sort
  • Bucket sort
  • Radix sort
• External sorting
  • Polyphase Merge
  • Replacement selection (enhancement to polyphase merge)
• Greedy algorithms:
  • Fractional knapsack
  • Task scheduling to minimize the number of processors required
  • Task scheduling on a uniprocessor to maximize the number of tasks that can be performed
  • Huffman trees and Huffman coding
• Divide aand conquer
  • Setting up a divide-and-conquer recurrence equation to describe the running time of an algorithm
  • Solving a divide-and-conquer recurrence equation
    • Simplified method
    • Master method
  • Binary search
  • Merge sort
  • Constructing a binary heap
  • Integer multiplication
  • Strassen's method:
    • You do not need to know the detailed equations for Strassen's method
    • You are expected to know that it is possible to multiply two 2-by-2 matrices with 7 scalar multiplications, and understand why this results in a more efficient algorithm for matrix multiplication
• Dynamic Programming
  • The basic approach:
    • Recursion vs. memorized recursion vs. dynamic programming
    • Expressing the solutions: subproblems, description of function, goal, initial conditions, recurrence equation
    • Modifying the program to obtain the optimum strategy in addition to the optimum value
  • Specific dynamic programming algorithms:
    • Optimal Weighted-interval scheduling
    • Truck-loading problem
    • 0/1 Knapsack problem
    • Optimal Matrix chain multiplication
    • Note: We expect you to be familiar with the formulation of dynamic programming problems as presented in the lectures and the lecture notes and able to formulate solutions accordingly. In particular:
      • The specification of the solution to a Dynamic Programming Problem as described on slide 6-15. Examples of its use can be found on slides 6-16,6-21, 6-28, and 6-35.