CAP 5636

Fall 2016

Class description: Principles of artificial intelligence. Uninformed and informed search. Constraint satisfaction. AI for game playing. Probabilistic reasoning, Markov decision processes, hidden Markov models, Bayes nets. Neural networks and deep learning.
Instructor: Dr. Lotzi Bölöni
Office: HEC - 319
Phone: (407) 243-8256 (on last resort)
E-mail: (preferred means of communication)
Web Site:
The assignments and the other announcements will be posted on the course web site
Classroom: ENG1 0286
Class Hours: Tue, Th 4:30PM - 5:45PM
Office Hours: Tue, Th 6:00PM - 7:30PM
Pre-requisites: Some programming experience.
Textbook: Russel & Norvig, 3rd edition
Grading: Homeworks: 25%, Quizzes: 5%
Midterm 1: 20%, Midterm 2: 20%, Final: 30%. Grading formula:
        HW = (HW1 + HW2 + HW3 + ...+ HWn) / n
        Q = (Q1 + ... + Qn) / n
        Overall = 0.25 * HW + 0.05 * Q + 0.2 * M1 + 0.2 * M2 + 0.3 * F
HW2, M2 etc are exactly the number you got, so if you got 112, that is what you put in.
Standard 90/80/70/60 scale will be used for final grades (curved if necessary).
All the exams are open book, open notes.
Integrity: The department, college, and University are committed to honesty and integrity in all academic matters. We do not tolerate academic misconduct by students in any form, including cheating, plagiarism and commercial use of academic materials. Please consult the Golden Rule Handbook for the procedures which will be applied.
Verification of engagement: As of Fall 2014, all faculty members are required to document students' academic activity at the beginning of each course. In order to document that you began this course, please complete the following academic activity by the end of the first week of classes, or as soon as possible after adding the course, but no later than August 27. Failure to do so will result in a delay in the disbursement of your financial aid.
To satisfy this requirement, you must finish the first quiz posted online. Log in to Webcourses, choose CAP 5636, and submit your answers online.


Lecture Notes, Readings, Homeworks
Aug. 23
History and positioning of AI
[slides] History and positioning of AI
Aug. 25
Uninformed search
  • Reflex agents
  • Search problems
  • Depth first and breadth first search
  • Uniform cost search

[slides] Uninformed search
Aug. 30
Informed search: A* search and heuristics
  • Informed search methods
  • Heuristics
  • Greedy search
  • A* search
  • Graph search

[slides] Informed search
Sep. 1
Constraint satisfaction problems 1
  • Constraint satisfaction problems as a special case of search
  • Examples: Map coloring, n-Queens, Sudoku etc.
  • Formulation
  • Solving CSPs - backtracking search

[slides] Constraint satisfaction problems 1
Sept. 6
Constraint satisfaction problems 2
  • Efficient solutions for CSPs
  • Iterative methods
  • Local search: simulated annealing, genetic algorithms

[slides] Constraint satisfaction problems 2
Homework 1: Project 1 from the Berkeley AI class. Due September 20th
Points are worth as follows: Q1..Q4 25 points each, Q5..A8 10 points each. Total achievable points 140 points.
Sept. 8
Game playing and adversarial search
  • Types of games
  • Adversarial search, minimax
  • The problem of depth
  • Evaluation functions
  • Alpha Beta pruning

[slides] Adversarial search
Sept. 13 Expectimax search and utilities
  • Expectimax search
  • Refresher about probabilities
  • Utilities and rationality
[slides] Expectimax search and utilities
Sept. 15
Markov decision processes 1
  • Defining MDPs: policies and utilities
  • Optimal policy, value of state, value of Q-state

[slides] Markov Decision Processes 1
Sept. 20
Markov decision processes 2
  • Policy iteration

[slides] Markov Decision Processes 2
Sept. 22
Reinforcement learning 1
  • Reinforcement learning as a twist on MDPs

[slides] Reinforcement learning 1
Sept. 27
  • Model-based and model-free learning
  • Temporal difference learning

Sept. 29

Oct. 4
Midterm 1: from introduction to Markov Decision Processes (inclusive)
Oct. 6
Reinforcement learning 2
  • Exploration vs. exploitation, regret
  • Generalization across states
  • Policy search

[slides] Reinforcement learning 2
Oct. 11

Oct. 13
  • Random variables
  • Joint and marginal distributions, conditional distribution

[slides] Probability
Oct. 18
  • Product rule, chain rule, Bayes' rule
  • Inference
  • Independence

Oct. 20
Markov models
  • Markov chains
  • Conditional independence
  • Stationary distributions

[slides] Markov models
Oct. 25
Hidden Markov models
  • Hidden Markov models
  • Example: robot localization

[slides] Hidden Markov models
Oct. 27
Particle filters and applications of HMMs
  • Particle filters
  • Robot localization with particle filters
  • Dynamic Bayes nets

[slides] Particle filters and Applications of HMMs

Nov. 1
  • Most likely explanation
  • Speech recognition

Nov. 3
Classification, principles of machine learning, naive Bayes
  • Classification
  • Model-based classification
  • Naive Bayes
  • Spam filter example
  • Generalization and overfitting
  • Parameter estimation

[slides] Classification and naive Bayes
Homework 2: Project 4 from the Berkeley AI class. Due November 29th
Points are worth as follows: Q1..Q4 25 points each, Q5..A7 30 points each. Total achievable points 190 points.
Nov. 8
Neural networks - perceptron
  • Error driven classification
  • Linear classifiers
  • Perceptrons
  • Support vector machines
  • Applications: web search

[slides] Perceptron
Nov. 10
Midterm exam 2: From reinforcement learning to particle filters (inclusive)

Nov. 15
Case-based reasoning, kernels and clustering
  • Case-based reasoning
  • Similarity
  • Kernelization
  • Clustering
  • K-Means

[slides] Kernels and clustering
Nov. 17
Deep learning
[slides] Introduction to deep learning

Nov. 22
Deep learning 2: Long short term memory

Nov. 24
Thanksgiving break

Nov. 29
Artificial General Intelligence 1.
  • General definitions of intelligence
  • Cognitive architectures: SOAR, ACT-R
  • Can intelligence exist without embodiment?

Dec. 1
Artificial General Intelligence 2.
  • Narrative-based approaches, Xapagy.
  • Superintelligence.
  • Ethical issues and dangers of superintelligence.

Final exam Thursday, December 08, 2016, 4:00 PM - 6:50 PM