AI 100 MIDTERM I - SIDE A

Concepts, intelligence, evaluation, and representation

1. WHAT AI IS + HISTORY (Ch. 1-2)

AI: science/engineering of principles and systems for perception, learning, reasoning, language, decision, planning, problem-solving, and creativity. It explores possible intelligent systems, not only human copies.

Strong AI: cognition is computation. Weak AI: cognition can be modeled by computation. Weak is behaviorally testable; Strong is not established by behavior because of the other-minds problem. RQ1: B.

Computation

  • Algorithm/effective procedure: precise executable instructions mapping one finite symbol string to another.
  • Turing machine (TM): simplest abstract general computer; can compute anything a modern computer can, given enough time/tape; theoretical and often inefficient.
  • Church-Turing thesis: anything algorithmically computable is TM-computable. Separates impossible/undecidable from merely expensive. RQ2: B.

Historical through-line

Aristotle syllogisms → automata (imitation of life) → Llull combinatorial Ars Magna → Hobbes reasoning as calculation → Leibniz universal language/calculus, binary, calculator → Babbage programmable Analytical Engine → Ada Lovelace symbol manipulation/music/art → Boole algebra of thought → Hilbert/Ackermann Entscheidungsproblem → Turing (1936) formal computation → Dartmouth (1956) (McCarthy et al.) establishes AI as a field.

Trap: convincing automaton behavior does not prove intelligence or understanding. Even if Strong/Weak AI fail, useful AI artifacts and scientific insights remain.

Modern milestones/examples

1997 Deep Blue beats Kasparov; 2011 Watson wins Jeopardy; 2012 AlexNet GPU/ImageNet breakthrough; 2016 AlphaGo beats Lee Sedol (Move 37); 2018 AlphaFold; 2022 ChatGPT. Everyday AI: search/ranking, spam, recommendations, translation, Face ID, navigation, and accessibility.

Benefits vs risks

Benefits: discovery, medicine, accessibility, productivity, climate/energy/logistics, augmentation. Risks: bias, opacity, unreliable decisions, accountability gaps, misinformation/deepfakes, surveillance, cognitive offloading, sycophancy, hacking, misalignment, concentrated power.

2. INTELLIGENCE (Ch. 3)

No universal precise definition: an open-ended set of capacities — perceive/model, reason, learn/generalize, adapt, communicate, plan/predict, solve/decompose, create, cooperate, introspect, and know limits. Broad transfer to unfamiliar domains matters.

Theory families: performance/psychometric (task scores); structural/functional (mechanisms); cognitive (mental processes); contextual (social/cultural adaptation); existence (conditions enabling intelligence); developmental (competence emergence).

INTELLIGENCE THEORIES + IQ

Sternberg triarchic

  • Analytical: logical decomposition/problem solving ("book smart").
  • Creative: use experience for novel problems.
  • Practical: adapt to/shape environment ("street smart").

Gardner multiple intelligences

Verbal-linguistic, logical-mathematical, spatial-visual, bodily-kinesthetic, musical, intrapersonal, interpersonal, naturalist. Main claim: intelligence cannot be captured by one IQ number. RQ4: B.

Historical child IQ = 100 × mental age / chronological age.
Mental age 10, actual age 8 → 100(10/8) = 125 (RQ7: C).
Modern IQ is normalized, commonly mean 100 and SD 15.

Binet (1905): identify children needing educational support (RQ8: B), not identify genius or permanently rank innate ability. Scores are rough, non-permanent, and affected by culture/background; score is not intelligence.

3. EVALUATING AI

Turing Test / imitation game

Original: man and woman separately type answers to an interrogator, each seeking to be identified as woman. Modified: computer replaces one player. It passes if the computer convinces the interrogator it is human at least as often as the human comparison player (RQ9: B). It need not answer perfectly or fool every judge.

Course position: ordinary conversational form was effectively reached by LLMs around 2022, but results depend on duration, judges, rules, and protocol. Passing shows behavioral competence, not necessarily understanding. Total/Video tests are harder.

ELIZA

Joseph Weizenbaum, MIT, 1966. Rogerian therapist persona; keyword/pattern rules, pronoun transformations, statements recast as questions, and generic fallback. No language or therapy understanding, yet users projected meaning/personhood (ELIZA effect).

Chinese Room (Searle)

Rulebooks manipulate Chinese symbols by shape/position = syntax, not meaning = semantics (RQ11: B). Correct responses show competence, not necessarily comprehension. Formal symbol manipulation alone is insufficient for understanding.

Systems reply: person alone lacks understanding, but the whole room/person/books system understands. Searle: internalizing all rules still need not add meaning. He does not say no machine can understand; he rejects program execution as sufficient.

Other tests

  • Reverse Turing Test: human proves humanness to computer; CAPTCHA. RQ15: B.
  • Winograd schema: pronoun/reference ambiguity requiring commonsense; WinoGrande is the large-scale variant.
  • Lovelace Test: evaluator-constrained, acceptable, aesthetically compelling creative artifact (music/story/art/proof).
  • Visual/Video: recognition, spatial/counting, causal, social/emotional, and commonsense reasoning.

4. REPRESENTATION (Ch. 8)

A representation is a surrogate/stand-in for selected objects, properties, relations, processes, actions, beliefs, or goals. It lets an agent substitute thinking for acting. Coffee: hot → burns → wait. RQ56: B.

Design principles

  • "All models are wrong, but some are useful": perfect fidelity needs the world itself; omit task-irrelevant detail.
  • More information is not always better: details cost memory/search and can hide relevant structure. Judge a representation relative to the task.
  • Form vs content: lookup table, repeated counter, and standard addition can compute the same function with different time-memory tradeoffs.
  • Abstraction shrinks search: sticks/squares reframing reduced choices from C(17,5)=6188 to C(6,3)=20.

Road graph pattern

Nodes=cities; directed edge=one-way road; weight=distance/cost; path cost=sum of weights. Keeps identity/connectivity/distances; discards terrain, flora/fauna, and exact curves. RQ51: B; RQ54: C.

Representation types

TypeWhat it encodes
Feature spaceMeasured dimensions; proximity = similar feature values
Relational networkEntities as nodes; relations as links
Game/decision treeStates and successor choices
State graphStates plus labeled transitions
LogicPropositions/predicates plus inference
ProceduralKnowledge as how-to steps
FramePrototype object/scenario with slots
ProductionIF condition THEN action/consequence
IsomorphicPreserves relevant structure/metric; e.g., map

Choose the graph

Instagram follows = directed, usually unweighted; mutual friendship/LinkedIn connection = undirected; road distance = weighted (directed if one-way); planar graph = drawable without crossings.

HIGH-YIELD CONCEPT TRAPS

Strong = is; Weak = modeled by. Behavior does not establish mind. TT need not fool every judge. ELIZA = patterns, not understanding. Chinese Room = syntax, not semantics. CAPTCHA = Reverse TT. Gardner rejects one-number intelligence. IQ puts mental age on top. More detail is not always better.

THEORY ANSWER TEMPLATE

For explain/compare: (1) define exact term; (2) state mechanism/components; (3) give course example; (4) contrast nearest alternative; (5) state limitation/trap.

For argument questions: claim → thought experiment/evidence → inference → strongest objection/reply → qualified conclusion.

Fast examples: Chinese Room: syntax vs semantics + systems reply. Turing Test: protocol + competence/comprehension limit. Representation: retained vs discarded information + task relevance. AI risk: benefit, failure mode, affected party/accountability, mitigation.

AI 100 MIDTERM I - SIDE B

Boolean logic, neurons, automata, Turing machines, and search

5. BOOLEAN ALGEBRA + MP NEURONS (Ch. 4)

ABA AND BA OR BA XOR B
00000
01011
10011
11110

NOT 0=1, NOT 1=0. OR is inclusive/saturated addition (1 OR 1=1). Functional completeness: {AND, OR, NOT} can express every Boolean function. Tautology: A OR NOT A. Contradiction: A AND NOT A.

De Morgan: NOT(A OR B) = (NOT A) AND (NOT B); NOT(A AND B) = (NOT A) OR (NOT B).
Iff/equivalence: "chess iff not sunny" = C equivalent to NOT S.

Official MCQ calculation patterns

  • A=T,B=T,C=F: (NOT A AND C) OR NOT(B AND NOT C) = F (RQ19 B).
  • A=T,B=F,C=T: NOT A OR B OR C = T (RQ20 A).
  • X AND NOT Y is true only at (1,0): RQ21 C.
  • (P OR Q) AND NOT R: R=0 and P,Q not both 0 → 3 true rows (RQ22 B).
  • A AND NOT A always false: RQ23 B. Completeness: RQ25 B.

At A=F,B=T,C=F:
(NOT A OR B) AND NOT(B AND C) = T;
(A OR NOT B) OR C = F;
NOT(A OR B) = F = NOT A AND NOT B.

Evaluation order: parentheses/NOT first, then AND, then OR. Do not confuse NOT A OR B with NOT(A AND B): they differ at (1,0) and (1,1).

McCulloch-Pitts threshold neuron

s = Σ(wixi); y=1 iff s ≥ θ, otherwise y=0.

Weights: excitatory (+), inhibitory (-). Output is binary, not the weighted sum.

FunctionWeightsThreshold
AND(1,1)2
OR(1,1)1
NOT(-1)-0.5
2-of-3 majority(1,1,1)2

(1,1), θ=2 computes AND (RQ26 B). Input (0,1), weights (1,1), θ=1: s=1 → y=1 (RQ30 B).

One threshold unit computes only linearly separable functions; XOR/XNOR need multiple units/layers. A network can implement any Boolean function because AND/OR/NOT are complete. Comparison is ≥. Book's NOT θ=0 and slides' -0.5 both work; prefer -0.5.

6. CIRCUITS, AUTOMATA, TURING MACHINES

ModelInput / memory / ability
Boolean circuitFixed Boolean inputs; no memory; fixed function; feedforward
Finite automatonAny finite string; finite state; regular language; recurrent
Turing machineTape string; unbounded R/W tape; general algorithm; recurrent + memory

Finite automaton (FA/DFA)

Components: finite alphabet/states, start state (arrow from nowhere), accept state (double/concentric circle; RQ33 C), labeled transitions. Start → consume one symbol at a time → follow transition → after the entire finite input, accept iff final state accepts. Accepted strings form its regular language.

Trace every question: make symbol | old state | new state; use the final row only. Visiting accept early is irrelevant if later symbols leave it.

Review/tracing patterns

  • Two states, toggle on 1, loop on 0 → odd number of 1s; 11010 accepts.
  • 0 -a→ 1 -a→ 2 -a→ 3, loops on b → at least three a's.
  • Exactly 101: q0 -1→ q1 -0→ q2 -1→ qA; every wrong/additional symbol → rejecting sink.
  • RQ36 A: number of 0s is a multiple of 3.
  • RQ37 C: baba. RQ38 B: ending nonaccepting means reject.
  • RQ39 A: 100101 → C, accepted. RQ40 D: 0100101. RQ41 A: 1010.
FA has finite memory but handles arbitrary finite-length input. It cannot generally count without bound, recognize arbitrary balanced parentheses, or compare arbitrarily distant symbols/palindromes. Infinite ordinary input never finishes, so no final decision.

Turing machine

Finite-state control + effectively infinite cell tape + finite alphabet/blank + read/write head. Transition depends on (state, read symbol), then writes, moves L/R (lecture may allow stay), and changes state. Thus: FA + revisitable external R/W memory = TM (RQ43 C; RQ44 C).

TM can accept/reject before reading all initial input, or loop forever. Universal TM: input is another TM's encoded program plus its input; it simulates that machine.

Limits: Halting Problem and related undecidable problems: not every well-posed question has an algorithmic decision procedure.

7. PROBLEM FORMULATION (Ch. 9)

Specify: (1) state representation, (2) start, (3) goal state/predicate/test, (4) actions/operators, (5) each action's preconditions and postconditions. Solution = action sequence from start to goal; nodes=states, edges=actions; expansion generates successors.

Examples: 8-puzzle (tile arrangement; move blank); water jug ((x,y); fill/empty/pour); Wordle (known letter constraints; guess); navigation (cities/roads). Search is hard due to exponential combinatorial explosion.

8. SEARCH: BFS, DFS, IDS, COST (Ch. 9)

Queue = FIFO (pharmacy line) → BFS. Stack = LIFO (plates/recursion) → DFS. Use a visited/explored set for graph search to avoid cycles/repeated states.

BFSDFS
OrderShallowest level firstOne branch, then backtrack
StructureFIFO queueLIFO stack/recursion
Complete?Yes: finite b, finite-depth goalFinite spaces; may chase infinite branch
Optimal?Shallowest; cost-optimal if equal stepsNo
SpaceO(bd), exponential1+(b-1)d = O(bd), linear depth
ClueAll same-level links firstWikipedia rabbit hole

b = maximum branching factor; d = shallowest solution depth.

Core pseudocode

BFS: enqueue start. While queue: dequeue n; if goal, return path; enqueue each unvisited child.
DFS: push start. While stack: pop n; if goal, return path; push each unvisited child (push order reverses visit order).

Iterative deepening (IDS)

Run depth-limited DFS with cutoffs 0,1,2,... Combines BFS-like completeness/shallowest solution with DFS-like linear memory; repeated shallow work is usually cheap because the deepest level dominates.

Weighted shortest path / uniform-cost / branch-and-bound

Frontier is a priority queue ordered by accumulated path cost g(n). Expand cheapest path. With nonnegative edge costs, when the cheapest frontier path removed is a goal, it is optimal.

Do not confuse: BFS minimizes number of edges, not weighted cost. DFS is not optimal. A graph that looks short geometrically may have high weights. Lecture may use "admissibility" for guaranteed optimality; standard later usage often reserves admissible for a heuristic that never overestimates.

REVIEW-QUESTION RAPID KEY

TopicOfficial answer / discriminator
Strong AIRQ1 B: cognition IS computation
TMRQ2 B: simplest general theoretical model
GardnerRQ4 B: not one IQ number
IQRQ7 C: 125; RQ8 B: support children
TestsRQ9 B TT; RQ11 B syntax; RQ15 B reverse TT
Boolean19 B; 20 A; 21 C; 22 B; 23 B; 25 B
NeuronRQ26 B AND; RQ30 B output 1
FA33 C; 36 A; 37 C; 38 B; 39 A; 40 D; 41 A
TMRQ43 C; RQ44 C
RepresentationRQ51 B; RQ54 C; RQ56 B

LAST-MINUTE TRAPS

OR is inclusive. Completeness is not tautology. MP output is 0/1, not sum. XOR is not one threshold unit. FA acceptance uses final state after all input. TM tape is writable/revisitable. More detail can hurt. BFS shallowest is not cheapest weighted. DFS can disappear down an infinite branch.

THEORY/CALC CHECKLIST

Boolean: substitute T/F → NOT → AND → OR; show intermediate values. Neuron: products → sum s → compare s ≥ θ → binary y. FA: trace every character → final state → accept/reject. Search: state/start/goal/actions first; then frontier order; distinguish depth from cost. Representation: surrogate, retained/omitted information, task benefit.