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.
- Depth-first search (DFS).
- Breadth-first 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.
- Alpha-beta 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. Computer-made 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 upper-left corner of both sides of the card/sheet.
-
There are no restrictions on the specific content written on the card/sheet.
|