Final Exam Information - CompSci 161 - Fall, 2022 (Dillencourt)
The the test rules and test format will be
essentially the same for the final as for midterm 2.
Here are slides summarizing the test rules and test format
that were posted before midterm 2, in
PPTX
and
PDF
format.
List of topics
The test will cover the material covered in the
first eight sets of lecture notes.
The following is a list of topics that
may be covered on the the Final Exam.
The test is cumulative, with somewhat more emphasis on the new topics
(i.e., the topics covered after the second midterm).
It lists the primary coverage area of this test.
What this means is that a given newer topic has a higher likelihood of
being covered than a given topic from the earlier material,
but any topic on the list is fair game for an exam question.
Test 2 covered up through the material on graph basics and
directed acyclic graphs
so the newer topics are the topics that fall under the heading of
weighted graphs.
Note:
As on the midterm exams,
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
- Address-calculation sorting:
- Counting sort
- Bucket sort
- Radix sort
- 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 and 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
- Optimal Binary Tree
- 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.
- Graph algorithms:
- Graph basics:
- Undirected/directed graphs
- Definitions of basic terms associated with graphs and digraphs
- Formulae for sums of degrees, indegrees, outdegrees
- Paths, cycles, subgraphs, connected components, trees
- Representations of graphs: adjacency list, adjacency matrix
- Directed graphs,
Directed acyclic graphs (DAGs)
- Topological orderings, topological sorting
- Weighted graphs
- Shortest paths
- Definition, formulation of problem
- Dijkstra's algorithm
- Minimum spanning trees
- Definition, formulation of problem
- Prim-Jarnik algorithm
- Kruskal's algorithm
Last modified: December 10, 2023