Last update: March 9, 2010Review for the Midterm ExamCMSC 421: Midterm ReviewCMSC 421: Midterm Review 1Midterm Exam♦ Scope: Chapters 1–6, and Common LispThe test won’t include Chapters 7 and 8♦ Open book, open notes♦ No electronic devicesMy exams can sometimes be very hardBut don’t let it bother you, because I grade on a curvee.g., when I taught CMSC 421 in Fall 2007:Midterm Final GPA62% 64% 2.88To help you prepare, the “private materials” web page has the midterm andfinal exams for the last four times I taught the courseIt also has the answers to the first two homework assignmentsLater today, I’ll post the answers to the third oneCMSC 421: Midterm Review 2Chapter 1: Intelligent Agents♦ What AI is:♦ thinking versus acting♦ humanly versus rationallyI won’t ask any questions about Chapter 1CMSC 421: Midterm Review 3Chapter 2: Intelligent Agents♦ Agents and environments♦ Rationality♦ PEAS (Performance measure, Environment, Actuators, Sensors)♦ Environment types♦ Agent typesI probably won’t ask much about Chapter 2CMSC 421: Midterm Review 4Chapter 3: Search♦ Problem types:deterministic, nondeterministic,fully observable, partially observable, non-observableexample: vacuum world♦ Tree-search algorithmsBreadth-first searchUniform-cost searchDepth-first searchDepth-limited searchIterative deepening♦ tree search versus graph searchCMSC 421: Midterm Review 5Chapter 4: Informed Search and Exploration♦ Heuristic search algorithmsGreedy searchA* on trees or on graphs with consistent heuristicsA* on graphs with inconsistent heuristics♦ Heuristic functionsadmissibilityconsistencydominanceproblem relaxation♦ Iterative improvement algorithmsHill climbing, simulated annealing,local beam search, genetic algorithms♦ Not on the exam:IDA*sections 4.4 (continuous spaces) and 4.5 (online search)CMSC 421: Midterm Review 6Common Lisp♦ lists, atoms, list notation♦ defining your own Lisp functions♦ built-in Lisp operators (functions, predicates, special forms, macros)♦ recursion, loops, and mapping functions♦ passing functions as arguments♦ operators for sequences (lists, vectors, strings)♦ good programming style(no direct questions on this, but don’t write sloppy code!)♦ Not on the exam:• destructive operations (e.g., setf, nconc)versus nondestructive operations (e.g., setq, append)• the xkcd comics• interacting with the debuggerCMSC 421: Midterm Review 7Chapter 5: Constraint Satisfaction♦ Definition: variables, constraints♦ Representation: constraint graphs♦ Backtracking search♦ Variable selection heuristics:MRV (minimum remaining values)degree (most constraints on remaining variables)♦ Value selection heuristic: least constraining value♦ Pruning techniquesforward checkingarc consistency (constraint propagation)♦ Problem structure:independent subproblemstree-structured CSPscutset conditioningCMSC 421: Midterm Review 8Chapter 6: Adversarial Search♦ What type of game:two-player, perfect information, zero sum♦ Game trees, minimax values♦ Alpha-beta pruning♦ Depth-bounded search, static evaluation functions♦ Node ordering♦ Nondeterministic game trees (e.g., backgammon)expectiminimaxCMSC 421: Midterm Review
View Full Document
Unlocking...