Computer Science 3200, Fall '25
Potential Exam Questions

---

Copyright 2025 by H.T. Wareham
All rights reserved

---

Topic 1, Topic 2, Topic 3, Topic 4

Questions prefixed by "(*)" involving executing one or more of the algorithms discussed in class.

Topic #1 (Course introduction; Lecture #1)

• In what year was the first workshop on AI held at Dartmouth College?
• Name three intelligent abilities and their associated AI application areas.
• Name two of the three pairwise distinctions of types of AI given in class and briefly describe what the pair of terms in one of these distinctions means.
• Name the two types of AI algorithms discussed in class with respect to mode of algorithm creation.

Topic #2 (Agents and Environments; Lectures #2 and #3)

• Given an agent, what are its associated sensors, percepts, actuators, actions, and (if any) knowledge?
• (*) Given a deterministic finite-state agent, an environment, and the initial position of the agent in the environment, what does that agent do?
• Name the four basic types of agents discussed in class and rank these types from least to most encoded intelligence.
• Given an agent, what are the environment, environment configurations, and problem associated with that agent?
• What are the two types of spaces associated with environments that were discussed in class?
• What are four of the seven environment properties discussed in class? For each of these properties, please also give the names of the two types associated with that property.
• Given several environments and a set of environment properties, what are the property-distinctions for each of the given environments relative to the given properties?

Topic #3 (Problem solving and search; Lectures #3-7)

• What are the four components of a well-defined problem?
• What are the four basic kinds of data in a search tree node?
• What are the four measures for assessing the problem-solving performance of a search strategy?
• What are the two basic types of search strategies?
• What are three of the five types of uninformed tree-based search discussed in class?
• For each of a given set of search algorithms discussed in class, indicate whether that is optimal or complete in general by writing ``Yes'' or ``No'' in the appropriate boxes in a provided table.
• For each of a given set of search algorithms discussed in class, what are the time and space complexities of that algorithm?
• What is the difference between tree-based and graph-based search?
• What is a closed list? An open list?
• (*) Given a graph, give the tree-based BFS / DFS / UCS search tree for finding a shortest path from vertex x to vertex y. As was done in class, please process edge-actions (and in the case of UCS, resolve ties in priority queue extraction) in alphabetical order by the destination vertex.
• (*) Given a graph, give the graph-based BFS / DFS search tree for finding a shortest path from vertex x to vertex y. As was done in class, please process edge-actions in alphabetical order by the destination vertex.
• (*) Given an action-weighted modified STRIPS problem, give the search tree created by BFS / DFS / UCS when finding all possible solutions. As was done in class and Assignment #1, please process all actions (and in the case of UCS, resolve ties in priority queue extraction) in the given action order.
• What makes a heuristic function admissible? Consistent?
• Given a particular heuristic for a given problem, explain why it is or is not admissible or consistent.
• What are the two types of informed tree-based search discussed in class?
• Which of these two types is optimal, and under what conditions?
• What are the two basic types of local search discussed in class?
• What are two of the state-space landscape features discussed in class?
• Why must the number of sideways moves be limited in sideways-move hill climbing search?
• Why is k-state local beam search not equivalent to k instances of random-restart hill climbing search?

Topic #5 (MiniMax search and AlphaBeta pruning; Lecture #7-9)

• What are the differences between Breadth-First Search and MiniMax search? Include differences in the search trees in your answer.
• (*) Given a MiniMax game tree with leaf node evaluation values filled in, fill in all other node evaluation values to compute the best possible evaluation value at the root node of the tree and indicate which move by the current player gives this value.
• What are the performance properties of MiniMax search?
• What is AlphaBeta pruning? How does it work?
• What are the performance properties of MiniMax + AlphaBeta search?