Overview: Final Exam
Topics

Algorithm analysis review.

Big O notation.

Common runtime functions: \(O(1)\), \(O(\log N)\), \(O(N)\), \(O(N \log N)\), \(O(N^2)\), \(O(N^3)\), \(O(2^N)\), \(O(N!)\).

Algorithm design techniques.
 Divide and conquer.
 Greedy algorithms.
 Backtracking.
 Memoization.
 Dynamic programming.

Python language specific features.
 Type hints.
 Bitwise operators:
&
, 
, ^
, ~
, <<
, >>
.
 Comprehensions: lists, sets, dictionaries, generators.
 Classes, data classes, named tuples.

Combinatorics.
 Power set.
 Combinations (with and without repetitions).
 Permutations (with and without repetitions).

Search algorithms.
 Depthfirst search (DFS).
 Breadthfirst search (BFS).
 A* search.

Priority queues.
 Min heaps and max heaps.
 Heap insertion and deletion.
 Heapsort.

Graphs.
 General graph concepts.
 Graph traversal algorithms.
 Spanning trees.
 Minimum spanning tree algorithms (Jarník/Prim, Kruskal).
 Dijkstra’s algorithm.

String related algorithms.
 Tries.
 Brute force search.
 KMP algorithm.

Adversarial search.
 General combinatorial game theory concepts.
 Minimax algorithm.
 Alphabeta pruning.

Miscellaneous problems.
 Knapsack problem.
 Traveling salesman problem.
Allowed Items During the Exam
NOTE: Once the exam starts you are not allowed to share any items with anyone else.

Pen, pencil, eraser, pencil sharpener.

Simple scientific calculator. You are not allowed to use a cell phone, programmable calculator, tablet, computer, or any other electronic device.

Personal cheat sheet with the following characteristics:

Must be one of these:

Must be handwritten. Computermade cards/sheets are not allowed.

You can write in both sides of the card/sheet.

Must include your student ID and full name on the upperleft corner of both sides of the card/sheet.

There are no restrictions on the specific content written on the card/sheet.
