Sample Final Exam for review purposes

CMPT310, Fall 2000, Qiang Yang and Janet Hsiao


  1. For the following Boolean function, calculate the entropy of the data set from formula


A and not B


  1. Build a decision tree for the above formula


  1. Train a perceptron for the above formula


  1. What is the error rate of the above decision tree on A and B?
  2. Build a grammar to parse the following sentence:

I will spend my Christmas in Vancouver


  1. Consider the following natural language understanding problem:



N I | AI


V like | took


And the sentence: I like AI


Now, formulate the natural language parsing problem on this sentence as a constraint satisfaction problem. What heuristic methods would you choose to solve it?


  1. Define stratified n-fold cross validation and 0.632 bootstrap estimation.


  1. Define supervised and unsupervised learning. Which of the following is unsupervised learning: decision-trees, neural networks, cluster?


  1. Describe an algorithm to perform a three-person game in English.