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, Topic 5, Topic 6

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 #4 (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?

Topic #5 (Constraint satisfaction problems (CSPs); Lecture #9-10)

• Given a CSP and a natural-language statement of a constraint on the variables in that CSP, give a possible formal statement of that constraint.
• Given a CSP, either give a solution for that CSP or state that no solutions exist.
• Given a CSP and orderings on the variables and value-domains in that CSP, give the complete value-assignment tree for that CSP and indicate which nodes are complete consistent assignments.
• Given a CSP and orderings on the variables and value-domains in that CSP, give the value-assignment tree for that CSP after pruning all inconsistent partial assignment subtrees (leaving the root of each such subtree in the tree enclosed by a dashed box) and indicate which nodes are complete consistent assignments by enclosing them in solid boxes.
• What are the three types of constraint consistency checks discussed in class?

Topic #6 (Logical reasoning; Lectures #10-XXX)

• With respect to logical reasoning, what are the two general approaches to deriving agent behaviour?
• What is the formal definition of a |= b?
• What is the difference between entailment and logical inference?
• What does it mean for a logical inference procedure to be sound? Complete? Grounded?
• Given a natural language statement, give a formal encoding of that statement as a sentence in propositional logic.
• Given a sentence in propositional logic, give a natural language statement of the meaning encoded in that sentence.
• Given a sentence in propositional logic, how many models are there for that sentence?
• Given two sentences s1 and s2 in propositional logic, what is the formal definition of the logical equivalence of s1 and s2?
• What are the two broad classes of logical inference procedures discussed in class?
• Given a sentence s in propositional logic and orderings on the variables and Boolean values in that sentence, give the complete basic model-tree for s and circle the nodes in that tree corresponding to models in which s is true.
• Given a sentence s in propositional logic and orderings on the variables and Boolean values in that sentence, give the model-tree for s after pruning all unsatisfiable partial model-subtrees (leaving the root of each such subtree in the tree enclosed by a dashed box) Nand indicate which nodes in that tree correspond to models in which s is true by enclosing them in solid boxes.
• Given several sentences in propositional logic, circle those sentences that are in Conjunctive Normal Form (CNF).
• Given several sentences in propositional logic, circle those sentences that are definite clauses.
• What is the unit resolution rule? Generalized resolution rule?
• Given the clauses making up the CNF form of a propositional logic knowledge-base KB and a sentence s, give a proof using the unit resolution rule which establishes that KB |= s.
• Given the clauses making up the CNF form of a propositional logic knowledge-base KB and a sentence s, give a proof using the generalized resolution rule which establishes that KB |= s.
• What are the two types of algorithm discussed in class for logical inference on definite clause knowledge bases? What is the basic way in which these algorithms differ?
• Given a set D of definite clauses, a set S of possible implication-symbols, and a set F of fact-sets, state which members of S can be derived by Forward Chaining with respect to D for each fact-set in F.
• Given a set D of definite clauses and a set S of possible implication-symbols, state all distinct fact-sets that are required for Backward Chaining to derive each member of S with respect to D. Note that you may not assume that each member of S has exactly one derivation relative to D.
• What is meant by "the ontological (epistemological) commitments of a representation language"?
• Given several representation languages, what are their respective ontological commitments?
• Give three ways in which first-order logic extends propositional logic.
• Given a natural language statement, give a formal encoding of that statement as a sentence in first-order logic.
• Given a sentence in first-order logic, give a natural language statement of the meaning encoded in that sentence.
• How are special- and general-purpose knowledge bases different?