Midterm 1 Information - CompSci 161 - Fall, 2022 (Dillencourt)

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

NOTE: This is a the finalized version.

List of topics

The test will cover the material covered in the first two sets of lecture notes and the third set of lecture notes up through and including slide 3-40.

The following is a list of topics that may be covered on the Test 1.

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.

• Asymptotic notation (Big O,Theta, Omega, little o)
• Mathematical background:
  • Sums and summations
  • Logarithms and Exponents
  • Floors and Ceilings
  • Factorials and combinations
  • Harmonic numbers
  • Proofs / Proof by induction
  • Basic Probability
• Basic data structures: Arrays, Linked lists, stacks, queues, dictionaries, hash tables
• Binary trees
• Sequential Search
• Binary search: Correctness, analysis, proof of optimality using decision trees
• Sorting, basic terminology (permutations, inversions)
• Comparison-based sorting:
  • Insertion sort
  • Selection sort
  • Quicksort, including worst-case and average-case analysis
  • Merge sort, including two applications:
    • Counting inversions in O(n log n) time and listing inversions in O(n log n + k) time, by appropriately modifying the mergesort algorithm
    • Counting line intersections in O(n log n) time and listing line intersections in O(n log n + k) time, by reducing the problem to inversion counting.
  • Priority queues
  • Binary heaps: basic properties, sift-up, sift-down, insertion, deletion, construction (heapify)
  • Heap sort
  • Lower bounds on comparison-based sorting / decision tree argument
  • Optimally sorting 5 elements