Copyright © Gordon S. Novak Jr.
Permission is granted for individuals to make copies of these notes for personal use, or for instructors to make copies for classroom use.
1. CS 378, Symbolic Programming
2. Course Topics
3. Symbolic Programming
4. Functional Programming
5. Clojure
6. Why Symbolic and Functional Programming?
7. Class Projects
8. Clojure
9. Quotation
10. List
11. Constructing a List
12. Access to Parts of a List
13. List Access Functions
14. IF statement
15. Tests on cons
16. Recursion
17. Tracing Function Calls
18. Designing Recursive Functions
19. Design Pattern for Recursive Functions
20. Recursive Processing of List
21. Recursive List Design Pattern
22. Filter a List
23. Tail Recursive Processing of List
24. Tail Recursive List Design Pattern
25. Constructive Tail Recursive Reverse
26. Tail Recursive Reverse Execution
27. Append
28. Append: Big O Hazard
29. Beware the Bermuda Triangle
30. Set as Linked List
31. Intersection
32. Tail-Recursive Intersection
33. Union and Set Difference
34. Association List
35. Let
36. Map
37. Some and Every
38. println, do, when, str
39. doseq and sort
40. Trees
41. Arithmetic Expressions as Trees
42. Computer Programs as Trees
43. English Sentences as Trees
44. Representations of Trees
45. First-Child / Next-Sibling Tree
46. Linked List Tree
47. Binary Tree Recursion
48. Design Pattern: Binary Tree Recursion
49. Flattening Binary Tree
50. Examples: Flattening Tree
51. Tracing Flattening Binary Tree
52. Postorder
53. Search
54. State Space Search
55. Depth-First Order: Recursive Default
56. Tree Recursion
57. DFS: Code to Build Answer
58. Answer for State Space Search
59. Design Pattern: Depth-first Search
60. Comments on Search Algorithm
61. Tail-Recursive Search
62. Robot Mouse in Maze
63. Robot Mouse Program
64. Robot Mouse Example
65. Tracing the Robot Mouse
66. Tracing the Robot Mouse ...
67. Depth-First Search
68. Big O for Trees
69. Bounded Depth-First Search
70. Iterative Deepening
71. Cost of Iterative Deepening
72. Depth-First Search
73. Solving Equations
74. Solving an Equation by Search
75. Examples: Base Cases
76. Recursive Cases: Operators
77. Recursive Tree Search
78. Recursive Tree Search Example
79. Big O and Termination
82. Solving a Set of Equations by Search
83. Solving Physics Story Problems
84. Generating Code from Equations
85. Eliminating Unused Equations
86. Conservation Laws
87. Double-Entry Bookkeeping
88. Representing Financial Contracts
89. Finance Combinators
90. Pattern Matching Overview
91. Copy Tree and Substitute
92. Substitution Examples
93. Loop Unrolling
94. Loop Unrolling Code
95. Binding Lists
96. Multiple Substitutions
97. Instantiating Design Patterns
98. Tree Equality
99. Tracing Equal
100. Design Pattern: Nested Tree Recursion
101. Tracing Nested Tree Recursion
102. Pattern Matching
103. Specifications of Match
104. Match Function
105. Matching and Substitution
106. Transformation by Patterns
107. Solving Equations with Patterns
108. Symbolic Differentiation
109. Repetitive Transformation
110. Optimization by Patterns
111. Constant Folding
112. Correctness of Transformations
113. Knuth-Bendix Algorithm
114. Programs and Trees
115. Macros
116. In-line Compilation
117. Partial Evaluation
118. Partial Evaluation
119. Example
120. Simple Partial Evaluator
121. Simple Partial Evaluator...
122. Examples
123. Examples
124. Binding-Time Analysis
125. Futamura Projections
126. Interpreter
127. Specialization
128. Parameterized Programs
129. Pitfalls of Partial Evaluation
130. Pitfalls ...
131. Language Translation
132. Program Transformation using Lisp
133. Max and Min of a Function
134. Knowledge Representation and Reasoning
135. Representation Hypothesis
136. Kinds of Knowledge
137. Logic
138. Logical Representation
139. Propositional Logic
140. Interpretation in Propositional Logic
141. Equivalent Formula Laws
142. Ways to Prove Theorems
143. Rules for Backward Chaining
144. Backward Chaining
145. Backchaining
146. Backchaining Code
147. (backchain goal rules facts)
148. Backchaining Code, version 2
149. Fact = Rule with No Premises
150. Normal Forms
151. Satisfiability Checking (Model Checking)
152. SAT Solvers
153. Uses of SAT Solvers
154. Predicate Calculus (First-order Logic)
155. Order of Quantifiers
156. Skolemization
157. Unification
158. Unification Algorithm
159. Examples of Unification
160. Substitutions
161. Unification Code
162. Unification Code ...
163. Unification Examples
164. Soundness and Completeness
165. Resolution
166. Conjunctive Normal Form
167. Resolution Example
168. Resolution Example
169. Natural Deduction
170. Backchaining Theorem Prover
172. Deductive Composition of Astronomical
173. Difficulty of Programming
174. Domain Theory
175. Astronomical Domain
176. Problem Difficulty
177. Where is the shadow of Io on Jupiter?
178. Shadow of Io Theorem
179. Shadow of Io Program
180. Performance
181. Deductive Composition of Programs
182. Logic Form of Rules
183. Navigation in the Plane
184. Navigation Predicates
185. Example Navigation Problem
186. Difficulties with Deductive Synthesis
187. Knowledge Rep. in Predicate Calculus
188. Rules
189. Backward Chaining
190. Importance of Backchaining
191. PROLOG
192. Predicate Calculus as Programming Language
193. When to Use Logic
194. Unit Conversion
195. Conversion Using SI Units
196. Unit Checking
197. Special Conversions
198. Unit Simplification
199. Problem Solving by Unit Conversion
200. Fixing Conversion Errors
201. Units in Programming Languages
202. Expert Systems
203. Power-Based Strategy
204. Expert Reasoning
205. Expert Knowledge
206. Choosing a Domain
207. Rule-Based Systems
208. Advantages of Rules
209. EMYCIN
210. Rule-Based Expert Systems
211. Reasoning Under Uncertainty
212. Bayes' Theorem
213. Uses of Bayes' Theorem
214. Joint Probability Distribution
215. Chain Rule
216. Bayesian Networks
217. Computing with Bayesian Networks
218. A Heretical View
219. EMYCIN's Certainty Factors
220. Certainty Factor Meaning
221. EMYCIN Data CF's
222. EMYCIN Antecedent CF
223. Rule Certainty Factors
224. Certainty Factor Combination
225. Certainty Factor Combination
226. Summary of CF Computations
227. Contradictions:
228. Duplicate Rules
229. Rule Subsumption
230. Increasing Certainty
231. EMYCIN CF vs. Probability Theory
232. Sensitivity Analysis
233. Explanation
234. Expert Systems vs. Decision Trees
235. Rule Induction
236. Sample Decision Tree:
237. Example of Rule Induction
238. Final Decision Tree with Classifications
239. Algorithm for Rule Induction
240. Alternatives for select-feature
241. Limitations of Rule Induction
242. Digital Low-Pass Filter
243. Getting Knowledge From Expert
244. Interaction with Expert
245. Conceptual Islands
246. Advantages of Conceptual Islands
247. Expansion with Conceptual Islands
248. Orthogonal Knowledge Sources
249. Example of Orthogonal Knowledge Sources
250. The Tuning Fallacy
251. Natural Language Processing (NLP)
252. Why Study Natural Language?
253. Model of Natural Language Communication
254. Minimality of Natural Language
255. Zipf's Law
256. Areas of Natural Language
257. Computer Language Understanding
258. Problems in Understanding Language ...
259. Morphology
260. Lexicon
261. Lexical Features
262. Size of Lexicon
263. Statistical Natural Language Processing
264. Part-of-Speech Tagging
265. AI View of Syntax
266. Grammar
267. Language Generation
268. Parsing
269. Ambiguity
270. Sources of Ambiguity
271. Foreign Languages
272. Formal Syntax
273. Notation
274. Phrase Structure Grammar
275. Recognizing Automaton
276. Regular Languages
277. Context Free Languages
278. What Kind of Language is English?
279. Parsing
280. Top-down Parser
281. Bottom-up Parsing
282. Augmented Transition Networks
283. Augmented Transition Networks
284. Separability of Components
285. Problems with Separability
286. Combining Syntax and Semantics
287. How to Combine Syntax \& Semantics
288. Natural Language as an AI Problem
289. Reference
290. Referent Identification
291. English
292. Expression Trees to English
293. Generating English
294. Simple Language Processing: ELIZA
295. Spectrum of Language Descriptions
296. Semantic Grammar
297. Semantic Grammar: Extended Pattern Matching
298. Example Semantics for a Semantic Grammar
299. Compositional Semantics
300. Additional Language Features
301. Recursive Descent
302. Parsing English
303. ATN Program
304. Parsing Functions
305. Grammar Compiler
306. Sentence Pointer Handling
307. Sentence Pointer Handling ...
308. Lexicon Example
309. Word Category Testing
310. Database Access
311. Database Access
312. Building Database Access
313. Grammar Rules
314. Restaurant Database Grammar
315. Notes on Database Grammar
316. Restaurant Queries
317. Physics Problems
318. Physics Queries
319. Physics Units
320. Physics Changes
321. Natural Language Interfaces
322. Problems with NL Interfaces
323. Mapping
324. Implementation of Mapping
325. Functional Programming
326. Associative and Commutative
327. Computation as Simulation
328. Mapping in Lisp
329. Mapcat and Filter
330. Input Filtering and Mapping
331. Reduce
332. Combining Map and Reduce
333. MapReduce and Massive Data
334. Distributed Programming is Hard!
335. What MapReduce Does for Us
336. Map Sort Reduce
337. Simplified MapReduce
338. Mapreduce in Clojure
339. Simple MapReduce Example
340. MapReduce Example
341. Hamburger Example
342. How MapReduce Works
343. Map Worker
344. Buffering
345. Load Balancing
346. Reduce Worker
347. PageRank
348. PageRank Example
349. Running PageRank Example
350. Advanced Performance
351. Performance Techniques in MapReduce
352. Algorithm Failure
353. Atomic Commit