CPS721: a Final Exam Study Guide

1. Section 1
2. Section 2
3. Section 3
4. Section 4
5. Section 5
6. Section 6
7. Section 7
8. Section 8
9. Section 9
10. Section 10
11. Section 11

The exam includes both multiple-choice (MC) questions and the questions where you have to write a short program or an essay. Bring an eraser and a pencil to write: you may need them to solve some of the questions. A soft HB #2 pencil is strongly recommended. Use a pencil, not a pen so that you can erase and update MC answers, if needed. For MC questions, once you have solved a problem, you have to fill in the bubble on the MC form. Do not guess! If the question requires you to choose several answers, but you are not sure, then select only those answer(s) which you know are correct. You do not need calculators. You must leave your mobile phone and your digital watch in your bag.

Below you can find a list of topics to study. The final exam will be cumulative and it will include topics covered throughout the term. Study ALL slides and handouts posted in the folder "Course Documents" on D2L. Specifically, pay attention to the slides with midterm review and final exam review. Read your solutions to homework assignments, as some exam questions can be similar. If your homework partner solved part of assignment questions, try to solve them yourself before you discuss them with anyone.

You can expect questions similar to labs, assignments and similar to exercises that were discussed (or mentioned) in class. Study your lecture notes. Read solutions discussed in class and during the tutorials. Make sure you read PDF slides with a midterm review posted on D2L. Also, practice to solve yourself all questions from the sample midterm and final tests posted on D2L. If you worked with a partner to solve exercises from homework, read your partner's solutions and/or ask your partner to explain them to you.

The list of topics includes an estimate of %-weight assigned to each topic.

• (about 10%) Formulate queries in Prolog (as in A1, Part 1 and in midterm). Note you have to write queries, not the rules. The queries are conjunctions of predicates that can be negated. Negation can be applied not only to a single predicate, but to a conjunction of predicates as well, e.g.,

          ?- predicate(X,Y), not ( predicate1(X), predicate2(Y), X > Y ).
  

  The latter is a common query pattern in Prolog that allows to retrieve from the data base an unique element characterized by super-lative adjectives such as the oldest, the largest, the cheapest, and so on.

• (about 8%) Structures in Prolog: how to use terms inside predicates, recursive programs with terms. For example, a family database (with terms for a person and date of birth), a binary tree example, or using the term next(H,T) to represent a list [H | T]. You can read the handout about binary trees as terms (posted on D2L) that includes an exercise. Read also similar exercises in the midterm review PDF files, your personal notes, and/or quizzes.

• (about 15%) Recursive programs (possibly with arithmetics), recursion over lists and over terms (A1 and A2, Parts 2 and 3, and the sample midterm questions). Read all handouts posted in Documents folder on D2L. Use case analysis: for each case you have to write a separate rule. Usually, you check a condition, and if it is true, do what is required, and then, sometimes, make a recursive call. Make sure you understand clearly which arguments in the given predicate provide input to your program, and which arguments are used to return the results. You have to understand how to write programs for predicates "append(L1,L2,L3)" and "member(Element,List)". However, the actual test questions about recursion will likely not need "append" and "member", and it is possible that programs must be written without these predicates. E.g., we can easily write recursive programs for "length(L,N)", "sum(List,S)" and for "replaceOne(X,Y,L1,L2)", "replaceAll(X,Y,L1,L2)" without using "append" and "member". In D2L cps721 course shell, read handouts related to the 2nd assignment that we discussed in class ("city reachable from Toronto", "blocks world").
  You have to know the following topics:
  • - arithmetics in Prolog
  • - using case analysis when developing a recursive program
  • - order of predicates in rules (is it important or not?)
  • - order of rules in a program (what happens if one changes the order of rules)
  • - negated predicates in recursive rules
  • - recursive programs with terms (structures) inside predicates

• (about 12%) Constraints (A3 and a midterm question about a CSP). Read slides from the class. Read also your lecture notes: we discussed in class the standard techniques. You have to know 2 approaches to solving problems with constraints: "pure generate and test" technique and "interleaving of generate and test". Note how dependency graph helps to choose an efficient order of constraints. Start solving this kind of exercises with writing facts that characterize all elements in the given finite domain. This can be done by writing a few atomic statements using a given predicate. The same predicate should be used throughout your program to retrieve values for variables (i.e., to "generate" values for variables). Next, think how many variables you need. This is always stated informally in English in the problem: number of the variables depend on how many unknowns you have. Then, write the single Prolog rule implementing the predicate solve(List). In this rule, implement all of the constraints. If you decide to use any helping predicates, then implement them.

• (about 15-20%) Natural Language Understanding (NLU)
  • main concepts, levels of analysis, applications;
  • grammars;
  • parsing of noun phrases and simple sentences: you should be able to draw a successful parsing tree given a grammar and a sentence or a noun phrase (recall that parsing trees are different from a query evaluation trees since in the parsing tree you need neither branches that fail, nor backtracking);
  • implementation of NLU systems (Assignment 4): there is no need to memorize the parser, but you are expected to understand how it works.
  You can read examples of parsing in your lecture and lab notes on NLU.

• (about 5%) General questions (short essay can be expected). You can read also handouts and lecture notes. Pay attention to what has been discussed in the 1st and 2nd weeks of classes (in September).

• (about 20-25%) Problem solving and planning (A5):
  • - properties of the general problem solver: what happens during the 1st stage (when the recursive rule for the predicate "reachable(S,L)" is applied) and what happens during the 2nd stage (when the program is searching for a sequence of legal moves).
  • - the predicate legal_move(S2,M,S1): why is it useful (hint: it serves two different purposes)
  • - predicates max_length(List,N) and reverse(List1,List2): what they do
  • - situations and fluents approach: main advantages and main differences from the state-based approach
  • - precondition axioms (how to write them)
  • - successor state axioms (SSA): how to write them. There are 2 main types of successor state axioms. Each positive effect axiom is saying when the fluent becomes true after doing an action. There is a separate rule for each action that makes fluent true. As for negative effect rules, recall that when you write a SSA saying that the fluent truth value is preserved, you have to say the fluent remains true unless none of the actions that make it false was the last action that was executed, i.e, you have to write a conjunction of the form (not A=act1, not A=act2, ) on the RHS of the rule.
  • - complexity of planning, what kind of search strategies we can use to save time on search
  • - depth-first search (DFS) and breadth-first search (BFS)
  • - declarative heuristics and how the predicate "useless(Action,Sit)" helps save time on search.
  Read your lecture notes (e.g., tiles on a grid example), your quiz, assignment 5 and the examples of precondition and successor state axioms discussed in class and during the tutorial. In total, more than 5 different examples have been discussed.

• (about 12-15%) Bayesian Networks
  • - basic probability theory: axioms of probability, conditional probability, joint probability, chain product rule, marginal probability, discrete random variables, joint probability distributions of discrete random variables, independence, conditional independence of a random variable from other variables, what computational advantage is provided by independence: examples.
  • Bayesian Network: definition, conditional probability tables, main properties.
  • Why Bayesian networks are useful and popular
  • How to use Bayesian networks to compute joint probability
  • How to use joint probability distribution to answer queries about conditional probabilities (recall: marginalization).
  • Examples of Bayesian Networks.
  Read your lecture notes (we discussed a few examples in class), your lab notes, and handouts on Bayesian Networks posted in the Documents folder on D2L.

General Exam Related Rules

• Place all cell phones, watches, personal audio equipment and other electronic devices in bags
• Place student ID on the upper right hand corner of the desk for verification
• Have no pencil cases on desks, only writing materials
• Have no food or drink during the exam unless medically required
• Water in transparent bottles, without any labels attached, may be brought into the exam room.
• Remove hats while writing the exam unless required by religious observance
• Conduct the exam in silence
• Be enrolled in the course to write the exam
• Raise their hands to ask a question, use washroom, or request additional supplies
• In the case of an emergency, leave all exam materials on the desk and follow the instructions of the invigilator
• Maintain all academic integrity standards during an exam (see Academic Integrity for details)
• Not leave the exam within the first 30 minutes, not enter the exam more than 30 minutes after it has begun or leave the exam within the last 15 minutes
• Not have any materials on the desk other than those designated by the instructor.

PLEASE NOTE:
* CHECK YOUR EXAM SCHEDULE VERY CAREFULLY. EXAM TIMES VARY BY DAY AND ARE
NOT NECESSARILY STANDARD.
* IT IS STRONGLY RECOMMENDED THAT YOU NOT BRING ANY VALUABLES TO THE EXAM
THAT YOU DO NOT WISH TO LEAVE IN YOUR BAG.
* IF AN ELECTRONIC DEVICE IS FOUND ON YOUR PERSON DURING AN EXAM, IT WILL BE
CONFISCATED AND RETURNED TO YOUR DEPARTMENT/SCHOOL.
*YOU WILL NOT BE PERMITTED TO BEGIN YOUR EXAM UNTIL YOU COMPLY WITH THE
RULES.  NOTE: YOU MUST STOP WRITING YOUR EXAM WHEN THE EXAM IS COMPLETED.
* FAILURE TO COMPLY WITH THE RULES MAY RESULT IN BEING CHARGED WITH ACADEMIC MISCONDUCT


Policy 60

The academic integrity framework for this final exam is the following.

 The work is to be completed individually. It is not a group project.


 The work is to be completed only by students registered in the course.


  Students may not consult friends and cannot collaborate while working
      on the final exam.


  This is a closed book exam. Students cannot consult their notes,  or 
      any other sources of information while working on this final exam. 


  The evaluation is not to be shared, now or in the future, with other students,
      at TMU or elsewhere.
	Similarly, your solutions cannot be shared in any form with anyone. 

For questions related to Academic Integrity at TMU, contact:
https://www.torontomu.ca/academicintegrity/