Advanced Algorithms

Overview: Final Exam

Topics

  1. Algorithm analysis review.
    1. Big O notation.
    2. 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!)\).
  2. Algorithm design techniques.
    1. Divide and conquer.
    2. Greedy algorithms.
    3. Backtracking.
    4. Memoization.
    5. Dynamic programming.
  3. Python language specific features.
    1. Type hints.
    2. Bitwise operators: &, |, ^, ~, <<, >>.
    3. Comprehensions: lists, sets, dictionaries, generators.
    4. Classes, data classes, named tuples.
  4. Combinatorics.
    1. Power set.
    2. Combinations (with and without repetitions).
    3. Permutations (with and without repetitions).
  5. Search algorithms.
    1. Depth-first search (DFS).
    2. Breadth-first search (BFS).
    3. A* search.
  6. Priority queues.
    1. Min heaps and max heaps.
    2. Heap insertion and deletion.
    3. Heapsort.
  7. Graphs.
    1. General graph concepts.
    2. Graph traversal algorithms.
    3. Spanning trees.
    4. Minimum spanning tree algorithms (Jarník/Prim, Kruskal).
    5. Dijkstra’s algorithm.
  8. String related algorithms.
    1. Tries.
    2. Brute force search.
    3. KMP algorithm.
  9. Adversarial search.
    1. General combinatorial game theory concepts.
    2. Minimax algorithm.
    3. Alpha-beta pruning.
  10. Miscellaneous problems.
    1. Knapsack problem.
    2. Traveling salesman problem.

Allowed Items During the Exam

NOTE: Once the exam starts you are not allowed to share any items with anyone else.

  1. Pen, pencil, eraser, pencil sharpener.

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

  3. Personal cheat sheet with the following characteristics:


    1. Must be one of these:

      • \(5 \times 8\) inches index card (\(12.7 \times 20.32\) cm).

      • Half letter size sheet of paper (\(13.97 \times 21.59\) cm).

    2. Must be handwritten. Computer-made cards/sheets are not allowed.

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

    4. Must include your student ID and full name on the upper-left corner of both sides of the card/sheet.

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