> Comp 150 Final exam study guide   Dordal      Exam is Tues, May 9, 1:45

> The exam will cover the following material:

> 1. Architecture
> Section 6.2:
>     Binary representation of numbers
>         ASCII representation of characters
>     Encoding instructions
> Section 6.3: omit
> Section 6.4:
>     Parsing, and building parse trees
>     Generating code from expressions

> Topics:
>     binary numbers
 
 
> 2. HTML  (no XML)
>   AE 4.3: Anatomy of a [web] Page
>   AE 4.4: Essential HTML
>   	These two sections cover web-page basics
>   AE 4.5: Information Structures
>   	Web-page lists (<ul>), tables (<table>), and frames
>   AE 4.7: XSL: Processing XML
>   	How XSL defines conversions from XML to HTML
 
     
> 3. Material on computer networks. See the networks handout 
> (on my main Comp 150 page)
 
> 4. Basics of Python, including simple loops
> For this exam you will be asked to produce simple python expressions and loops.
> You might want to consult the Exam 2 study guide for useful python examples.
 
> 5. Artificial Intelligence:
> 	Turing Test
> 	Why natural-language processing is hard
> 	representations for sentences
> 	Scripts
> 	using scripts to resolve ambiguous pronouns
> 	using a knowledge base to resolve what prepositional phrases modify
> 	using a knowledge base to resolve ambiguous pronouns
>	machine reasoning
>	automated proofs using resolution
 	
> I will provide you with the same "syntax cheat sheet" for python that
> you had on exam 2.
> 
> You should be able to understand how dictionaries are used.
>     
> ==========================================================================
> 
> Sample problems:
> 
> 1. Write a python function to check each word in a list "wlist" 
> for membership in a dictionary "dict". If word w is found in dict
> (if w in dict), return dict[w]. If no word matches, return "notfound".
> 
> 	def wcheck1 (wlist):

The nice thing about writing this as a function is that, once you've
found a match, you just return, and don't have to worry about the 
rest of the function:

def wcheck1 (wlist):
    for w in wlist:
        if w in dict:
            return dict[w]
    return "notfound"

Note that the following version is WRONG: it never gets past the first
word. It either returns dict[w] for w the first word of wlist,
or it returns "notfound"

WRONG:	def wcheck1 (wlist):
WRONG:	    for w in wlist:
WRONG:	        if w in dict:
WRONG:	            return dict[w]
WRONG:	        else:
WRONG:	            return "notfound"

> (b). Write a python function to check each word in a list "wlist"
> for membership in dictionary "dict1". Then, if none of the words
> are in "dict1", check each word for membership in dictionary "dict2".
> Again, return dict1[w] if word w is in dict1; dict2[w] if a word
> is found in dict2, and "notfound" otherwise.
> 
> Be sure you check all the words for being in dict1 before you 
> check any for being in dict2. An application of this might be
> a chatterbot where we first tried to match a dict1 word, and 
> only if all those failed did we go on to dict2.

def wcheck1 (wlist):
    for w in wlist:
        if w in dict1:
            return dict1[w]
    for w in wlist:		# now start over on dict2
        if w in dict2:
            return dict2[w]
    return "notfound"


> 2. Give a parse tree for the following expressions. Leaf nodes
> of the tree should be numbers/variables; all interior nodes
> should be +,-,*,etc.
> 
> (a). 1+(2*(3-(4*5)))		(b). (x-1)*(x+1)

         +                                *  
        / \                             /   \ 
      1     *                          -     +    
           / \                        / \   / \
          2   -                      x  1  x   1
             / \
            3   *
               / \
              4   5
              
          
> 3. (a). Write HTML for a simple      (b). Write the html neces-
> page with two headers, two para-     sary to produce two column
> graphs below each header, at         text using a TABLE; create 
> least one unnumbered list of         the table and show where the
> topics, and a section of "unfor-     text would go. The result should
> matted" computer code.               look like this problem.

(b) One-row table: a single <tr>..</tr>, with two columns inside.
<table>
<tr>
<td>
3. (a). Write HTML for a simple 
page with two headers, two para-
graphs below each header, at  
least one unnumbered list of   
topics, and a section of "unfor-
matted" computer code.    
</td>
<td>
(b). Write the html neces-
sary to produce two column
text using a TABLE; create 
the table and show where the
text would go. The result should
look like this problem.
</td>
</tr>
</table>

> 4. (a). List some reasons why natural-language interpretation is 
> so difficult.

It is hard to resolve ambiguities in the text; eg what modifies what
It is hard to resolve pronouns
It is hard to recognize metaphor
It is hard to figure out whether references to things are intended
as definite or indefinite

> (b). Discuss one way of representing natural-language sentences
> within the computer.

The traditional strategy is to represent things as, in effect,
sentence diagrams: using a structure with "slots" for:
	* the verb or verb phrase (primary action)
	* the subject (primary actor, a noun phrase)
	* the direct object (that which is acted upon)
	* any modifier phrases indicating TO, WHERE, WITH, etc

> (c). In the sentence
> 
> 	Mary saw the mountains flying to Denver
> 	
> discuss at least one possible way of determining whether 
> "flying to Denver" modifies "Mary", "saw", or "mountains".

"flying to denver" doesn't modify Mary simply by placement.
If there were a group of Marys and we wanted to identify the
one flying to Denver, we would write

	(The) Mary flying to Denver saw the mountains
	
Not that this situation makes any sense.


"flying to denver" cannot modify mountains simply because 
mountains don't fly. If the sentence were
	
	Mary saw the mountains covered with snow
	
then "covered with snow" *would* modify mountains. This sentence
does NOT mean that Mary was covered with snow when she looked
at the hills.


"flying to denver" modifies "saw": it indicates that the place
Mary saw the mountains was while flying to denver.


> 5. Suppose we have the following logic relationships
> 
> 1. A	(given as true)
> 2. B	if 	A
> 3. C	if 	A
> 4. D	if 	A & C
> 5. E	if 	C & D
> 6. F	if	E & B

> (a). Show how we can conclude F by starting at A and moving forward.

From 1, we know A
From 2, we conclude B: known facts = {A, B}
From 3, we conclude C: known facts = {A, B, C}
From 4, we conclude D, because we know A and C. known facts now is {A, B, C, D}
From 5, and the fact that C and D are known, we conclude E.
From 6, and the fact that B and E are known, we conclude F.


> (b). Show how we can conclude F is true by starting at F and working
> backwards ("F would be true if E and B are true...."). At each step,
> state which of the rules 1-6 above is being applied. Note that,
> as there is exactly one rule concluding each of A-F, there is never
> any ambiguity.

To show F, it suffices by rule 6 to show E and B.
   To show E, it suffices by rule 5 to show C and D for rule 5
       To show C, it suffices by rule 3 to show A
           A is given: KNOWN: {A}
       KNOWN: {A, C}
       To show D, it suffices by rule 4 to show A and C. But these are known.
       KNOWN: {A, C, D}
   KNOWN: {A, C, D, E}
   To show B, it suffices by rule 2 to show A, which is known.
   KNOWN: {A, B, C, D, E}
Known: {A, B, C, D, E, F}
       

> (c). Now consider the following logic relationships.
> 
> 1. A	(given as true)
> 2. B	if 	A
> 3. D	if 	A & C
> 4. E	if 	A & D
> 5. E	if	A & B
> 6. F	if 	E
> 
> Suppose we start with F and work backwards, each time choosing
> the first applicable rule. Show how we have to BACKTRACK because
> the first rule for E (rule 4) fails us.

To show F, it suffices by rule 6 to show E
   To show E, it suffices by rule 4 to show A and D.  #4 is 1st rule concluding E
       A is given: KNOWN={A}
       To show D, it suffices by rule 3 & the fact A is known to show C
           There is no rule for C! BACKTRACK
       No other rule for D: BACKTRACK again
   To show E, it suffices by rule *5* to show A & B. A is known
       To show B, it suffices by rule 2 to show A, which is known.
       KNOWN: {A, B}
   KNOWN: {A, B, E}
KNOWN: {A, B, E, F}


> 6. Suppose you are generating a dynamic web page (perhaps as a result
> of an html form). You have a python variable LIS representing a list
> of strings. Write a Python loop to generate a series of paragraphs,
> one per string, each followed by a <hr> (horizontal rule) tag.
> Thus, if LIS is ['foo', 'bar', 'how are you'], the html should be
> 
> 	<p>
> 	foo
> 	<hr>
> 	<p>
> 	bar
> 	<hr>
> 	<p>
> 	how are you
> 	<hr>

for str in LIS:
    print "<p>"
    print str		# no quotes
    print "<hr>"


> 7. Give a general discussion of how a CPU uses its clock signal to
> execute a sequence of instructions stored in memory.

Typically the clock drives a large DECODER: with each tick of 
the clock, a different set of lines is activated. Sample:

Tick: 	1. Activate the lines to move the contents of memory at PC
	to the instruction decoder
	
Tick: 	2. Activate the lines to increment PC and decode the
	instruction
	
Tick: 	3. Activate the lines to fetch from memory the *data*
	at the address in the upper half-word of the instruction,
	IF NECESSARY
	
Tick:	4. Activate the lines to send inputs to the ALU

Tick:	5. Activate the lines to select the output of the ALU, 
	and store it
	
Tick:	Step 1 again

The CPU in general relies on being fast enough to complete each
step within one clock tick.

On very rare occasions the clock signal causes part of the CPU
to "check again if another part has finished executing"; 
this allows CPU actions of indefinite length.


> 8. Consider the following database of facts. Parent(x,y) means
> y is a parent of x.
> 
> 1. Parent(lisa, mary)
> 2. Parent(lisa, sam)
> 3. Parent(bill, mary)
> 4. Parent(bill, sam)
> 5. Parent(bob, bill)
> 6. Parent(bob, eva)
> 7. Parent(eva, clara)
> 8. Parent(ralph, lisa)
> 9. Parent(ralph, fred)
>10. Parent(sue, lisa)
> 
> Cousin(x,y) :- Parent(x,z), Parent(z,w), Parent(y,u), Parent(u,w)
> 
> (a). Show Cousin(ralph, bob)

At each step we choose here the FIRST untried fact that applies.

Cousin(ralph, bob) if Parent(ralph, z), Parent(z, w), Parent(bob, u), Parent(u,w)

    Try z = lisa from rule 8: Parent(ralph, lisa)
    Suffices to show Parent(lisa, w), Parent(bob, u), Parent(u, w)
     
        Try w = mary from rule 1: Parent(lisa, mary)
        Suffices to show Parent(bob, u), Parent(u, mary)
        
            Try u = bill, rule 5
            Suffices to show Parent(bill, mary).
            
            TRUE!
Done, with no backtracking.

BUT if we'd exchanged rules 5 and 6, we would have tried u=eva first, 
and failed immediately, and had to backtrack to the other rule.


If we'd exchanged rules 8 & 9, we would have tried z=fred at the
beginning, and failed to find a match for Parent(fred, w),
and had to backtrack.



> (b). Find all X for which Cousin(ralph, ?Y) is true.

Cousin(ralph, Y) if Parent(ralph, z), Parent(z, w), Parent(Y, u), Parent(u,w)

    Try z = lisa from rule 8: Parent(ralph, lisa)
    Suffices to show Parent(lisa, w), Parent(Y, u), Parent(u, w)
     
        Try w = mary from rule 1: Parent(lisa, mary)
        Suffices to show Parent(Y, u), Parent(u, mary)
        
            Optimize the rules a little, and try to satisfy the SECOND clause:
            Parent(u,mary) (because it has only one unknown) Try u = lisa, rule 1
            Suffices to show Parent(Y, lisa).
            
           	TRUE with Y=ralph, but this obviously isn't what we wanted
           	
            BACKTRACK to try u=bill, rule 3; suffices to show Parent(Y,bill)
            TRUE! with Y=bob
            
       Now try w=sam from rule 2: no new solutions
       
   Now try z=fred from rule 9: no solutions; there are no other relationship
   facts about Fred which we can use.
   
Done


If we ask Cousin(bob, ?Y), we should get Ralph & Sue (and, technically, Bob).