SoniaSandbox

Temp notes for Lecture 6

Exams and HWs

• In-class midterm on 10/

studying for the exam:

don't memorize lecture notes,

understand the problems and how to solve them

if you understand all the homeworks you'll be in good shape

Homeworks coming up

• HW5: Due next wednesday

downPass, maximum likelihood

• HW6:

search tree space

Up Pass

• If we know what the best answer is at the root- all of out other internal nodes aren't necessarily the best guess. We need an upPass algorithm that passes information from the root, back up to the leaves.

• just for working through this example, we are dealing with one

def upPass(tree,parent):

if tree is a leaf: #(stop)

return

i123 = parent <intersect> left <intersect> right

i12 = left <intersect> right

i23 = parent <intersect> left

i13 = parent <intersect> right

if i123 != None:

tree['data'] = i123

else: #possible to simplify if empty set doesn't add

if i12 != None:

data += i12

if i13 != None:

data += i13

if i23 != None:

data += i23

if data == None:

data = parent + left + right # do you want the union here really?

tree['data']= data

• What should we do when there is no intersect ?
  • when you start upPass that can't be the case because every parent should have an interset with its children if youve donw downPass correctly.
  • BUT this situation does arise as you traverse up the tree because you eliminate possibilities at a parent before you test for intersect with the children.

<strikeout>hello?</strikeout>