Computer Science 3200, Fall '24
Potential Exam Questions

---

Copyright 2024 by H.T. Wareham
All rights reserved

---

Topic 1, Topic 2, Topic 3, Topic 4, Topic 5, Topic 6, Topic 7, Topic 8, Topic 9, Topic 10

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 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?
• What are three of the four basic types of agents? Rank these types from least to most encoded intelligence.
• Given an agent, what are the environment, environment configurations, and problem associated with that agent?
• 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?
• Which of these three types is complete, and under what conditions?
• What are the time complexities of each of these three types?
• 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.
• (*) Given a graph, give the graph-based BFS / DFS search tree for finding a shortest path from vertex x to vertex y.
• (*) Given an action-weighted modified STRIPS problem, give the search tree created by BFS / DFS / UCS when finding all possible solutions.
• 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?

Topic #4 (Hash tables and local search; Lectures #7-8)

• What is a hash table?
• What is a hash function?
• What is the difference between a perfect hash function and a minimal perfect hash function?
• Name and briefly describe three of the non-mathematical hash function properties discussed in class.
• Name and briefly describe two of the hash function algorithms discussed in class.
• What is a hash collision?
• Name and briefly describe two of the hash collision resolution policies discussed in class.
• 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 #9-10)

• 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 #6 (Constraint satisfaction problems (CSPs); Lecture #10-11)

• 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 #7 (Logical reasoning; Lectures #11-15)

• 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?

Topic #8 (Evolutionary computing (EC); Lecture #16)

• What are two of the EC genotype representations discussed in class?
• What are five of the components of an evolutionary algorithm that were discussed in class?
• Which of the following statements about evolutionary computing are true? Which are false?

Topic #9 (Reinforcement learning (RL); Lecture #17)

• What are the four components of an RL-specified problem that were discussed in class?
• Which of the following statements about reinforcement learning are true? Which are false?

Topic #10 (Neural networks and deep learning; Lecture #18)

• What are four of the types of neural network architectures that were discussed in class?
• Which of the following statements about neural networks and deep learning are true? Which are false?