Midterm 1

Learning Objectives

Search

  1. Understand how to formulate and define problems as search problems.

  2. Describe and implement various search algorithms.

  3. Understand how search algorithms run on a given problem.

  4. Analyze the time and space complexity of a variety of search algorithms.

  5. Give example search applications where one search algorithm would outperform others, e.g. a situation where DFS would outperform BFS.

  6. Verify or create admissible/consistent heuristics for a given search problem

  7. Describe the trade-offs between computationally cheap, inaccurate heuristics and computationally expensive heuristics

  8. Understand both the algorithmic differences and the distinct use cases for tree search vs graph search.

Adversarial Search

  1. Define a game, zero-sum game, standard form, and a game search tree

  2. Trace and implement Minimax, Expectimax, and Expectiminimax given a start state, player list, and actions.

  3. Describe the bounded lookahead algorithm

  4. Define and create evaluation functions

  5. Analyze a minimax tree using alpha-beta pruning to determine pruned nodes

Constraint Satisfaction Problems

  1. Describe definition of CSP problems and its connection with general search problems

  2. Formulate a real-world problem as a CSP

  3. Describe and implement backtracking algorithm

  4. Define arc consistency

  5. Describe and implement forward checking and AC-3

  6. Explain the differences between MRV and LCV heuristics

  7. Identify variables and values chosen by MRV and LCV heuristics

Local Search

  1. Describe and implement the following local search algorithms:

    1. Iterative improvement algorithm with min-conflict heuristic for CSPs

    2. Hill Climbing (Greedy Local Search)

    3. Random Walk

    4. Simulated Annealing

  2. Identify optimality of local search algorithms

  3. Compare different local search algorithms as well as contrast with classical search algorithms

  4. Select appropriate local search algorithms for real-world problems

Linear and Integer Programming

  1. Formulate a problem as a Linear Program (LP)

  2. Convert a LP into a required form, e.g., inequality form

  3. Plot the graphical representation of a linear optimization problem with two variables and find the optimal solution

  4. Understand the relationship between optimal solution of an LP and the intersections of constraints

  5. Describe and implement a LP solver based on vertex enumeration

  6. Describe the high-level idea of Simplex algorithm

  7. Formulate a problem as a Integer (Linear) Program (IP or ILP)

  8. Write down the Linear Program (LP) relaxation of an IP

  9. Plot the graphical representation of an IP and find the optimal solution

  10. Understand the relationship between optimal solution of an IP and the optimal solution of the relaxed LP

  11. Describe and implement branch-and-bound algorithm

Practice Exams

Please find practice midterms and solutions attached below. We have included some recordings of TAs walking through solutions to some select problems. If you have any questions, please feel free to post on Piazza or ask during Office Hours.

Practice Midterm 1A: blank/sol


Practice Midterm 1B (ignore logic question): blank/sol