Welcome to CMPT 310, Summer 2019!

Welcome to CMPT 310: a discussion of the fundamental problems of artificial intelligence (AI), and approaches to solving them.

The course marking scheme, along with weights and due dates for assignments, quizzes, etc. are on Canvas.

Here is the official course outline. Please note a couple of things:

Assignments

The course marking scheme, along with weights and due dates for assignments, quizzes, etc. are on Canvas.

Midterm exam

Closed-book, in-class during a regular lecture time. Please note that you will be asked to place all books, jackets, computers, cell phones, etc. at the side of the room.

Importantly, you may not have a cell phone with you when you write the exam. You must put your cell phone in your bag, or keep it at the front of the room.

There will not be time during the midterm to allow people to use the washroom, so please be prepared!

More information:

  • The date of the exam is in Canvas.

  • The exam could have any type of questions, such as:

    • Tracing questions, where you are asked to, for example, run an algorithm by hand on a tree or graph.
    • Writing pseudocode, e.g. pseudocode versions of important algorithms.
    • Short answer, true/false, multiple choice, etc.

    This is not necessarily an exhaustive list. There could be other types of questions, and not all these questions types will necessarily occur on the exam.

  • Here are the sections of the textbook the midterm covers:

    • Chapter 1 (introduction): 1.1
    • Chapter 2 (intelligent agents): 2.1, 2.2, 2.4
    • Chapter 3 (solving problems by searching):
      • 3.1
      • 3.2: focus mainly on problems discussed in lectures/notes
      • 3.3: know pseudocode for Tree-Search and Graph-Search algorithms!
      • 3.4: you can skip 3.4.6: Bidirectional Search
      • 3.5: for A*-search, you don’t need to know the proof of optimality, but you should know the definitions of the major terms and the major characteristics of A*-search; for 3.5.3, you only need to know the names of a couple of memory-bounded heuristic search algorithms
      • 3.6: skip 3.6.4 onwards
    • Chapter 4 (beyond classical search):
      • 4.1: know the terminology of local search; know the pseudocode code for, and be able to trace by hand these algorithms: hill-climbing (and variations), simulated annealing, and local beam search; for genetic algorithms, you only need to know the basic idea, and you don’t need to know the pseudocode or be able to trace them
    • Chapter 5 (adversarial search):
      • You only need to know what is the notes and PowerPoint presentation for chapter 5 (see the course notes below)
    • Chapter 6 (constraint satisfaction):
      • 6.1: you can skip 6.1.2 - 6.1.3
      • 6.2.2: know what arc consistency is, and be able to run the AC-3 algorithm by hand
      • 6.3: be able to run backtracking by hand on a CSP; know the major heuristics and variations
      • 6.4: be able to run min-conflicts by hand to solve a CSP

  • Here is a sample midterm exam (solutions).

  • Here is a copy of the Summer 2019 CMPT 310 midterm exam (solutions)

Please read the grading FAQ for answers to commonly asked question about how grades are calculated.

Final exam

Closed-book, at a time set by SFU during exam schedule: see Canvas for the exact date and time.

Closed-book, at a time set by SFU during exam schedule. Please note that you will be asked to place all books, jackets, computers, cell phones, etc. at the side of the room.

Some basic exam rules that will be followed:

  • You cannot leave in the first 30 minutes (in order to give people who arrive late a chance to write the exam).
  • In the last 10 minutes of the exam, no one can leave. This is to avoid disturbing people who are still working on the exam.

Importantly, you may not have a cell phone with you when you write the exam. You must put your cell phone in your bag, or keep it at the front of the room.

Please read the grading FAQ for answers to commonly asked question about how grades are calculated.

More information:

  • The exam could have any type of questions, such as:

    • Tracing questions, where you are asked to, for example, run an algorithm by hand on a tree or graph.
    • Writing pseudocode, e.g. pseudocode versions of important algorithms.
    • Short answer, true/false, multiple choice, etc.

    This is not necessarily an exhaustive list. There could be other types of questions, and not all these questions types will necessarily occur on the exam.

  • In general, you should refer to the lecture notes below to see what topics were covered (and in what depth) in the lectures; also are references to the textbook about the topics covered after the midterm:

    • Chapter 7: Logical Agents (propositional logic and SAT)
      • 7.1: know basic terminology and architecture of logic-based agents
      • 7.2: might be useful to review this, but you don’t need to know anything specific to the Wumpus world
      • 7.3, 7.4: review of propositional logic; make sure you know basic terms
      • 7.5: know CNF; know the basic algorithm for resolution theorem proof (don’t need to know proof about completeness); you should know what a Horn clause is (7.5.3), but you won’t be asked anything about forward/backward chaining (7.5.4)
      • 7.6: know the basic approach and heuristics used in the DPLL SAT algorithm; know the pseudocode for WalkSAT
      • 7.7: not covered on the exam
    • Chapter 10: Classical Planning
      • 10.1: know the basic terminology and format of a classical planning problem, including basic sample domains (like blocks world); skip 10.1.4 (complexity of planning)
      • 10.2: understand the difference between forward and backwards (regression); know some heuristics used by modern forward planners
      • 10.3: not covered
      • 10.4.4.: know the basic idea of partial order planning and how it differs from state-based planning (like forward and backwards planners)
    • Chapter 18: Learning from Examples
      • 18.1: know the “big picture” of learning terms, and basic approaches different kinds of learning takes
      • 18.2: know the definition of supervised learning, and some of the general issues that arise when using it
      • 18.3: know the basic idea of decision trees, how they work, how they can be learned, etc.; you don’t need to memorize the information theory formulas used for splitting, but you should understand the general idea; skip 18.3.5 and 18.3.6
      • 18.4, 18.5: skip
      • 18.6: know the basic idea of of univariate linear regression (18.6.1), including what sorts of problems it can be useful for and how it differs from classification (you don’t need to memorize the formulas); you can skip 18.6.2 onwards (but the discussion of the Perceptron learning rule in 18.6.3 might useful to review)
      • 18.7: know the basic idea of neural networks, including the basic structures of an artificial neuron; know how single-layer feed-forward neural nets based on perceptrons work, and how they can be trained; 18.7.3 skip onwards
      • 18.8.1: know the basic idea of the k-nearest neighbor algorithm (you don’t need to know the terms in the section from Minkowski distance onwards)
      • skip other parts of 18.8
      • 18.9, 18.10: skip
      • 18.11.1: understand the hand-written digits problem, and how a Perceptron network could be set up to solve it
    • Chapter 20: Reinforcement Learning
    • Chapter 22: Natural Language Processing
      • please refer to the lecture notes to see what exact topics where covered, and in what depth

Software

Most of the assignments will be using Python 3, and you should install the aima-python code on your computer (including the sample data sets). Follow the installation instructions on the aima-python page.

Note that some of the aima-python is written inside of Jupyter Notebooks, so you ought to install that on your system as well.

While you are welcome whatever operating system you prefer, keep in mind that all examples will be from Ubuntu Linux. Thus, we recommend that you install that latest desktop version of Ubuntu Linux on a virtual machine (such as Virtual Box).

Some assignments may also use minisat, a popular SAT solver. To install it on Ubuntu Linux, just run this at the command-line:

$ sudo apt install minisat

Course Notes

The following are the planned topics. The precise topics might change slightly as the course progresses, and we may spend more/less time on certain topics.