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):
	

(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.



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)



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.


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

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

(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".

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.

(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.

(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.



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>


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


8. Consider the following database of facts. Parent(x,y) means
y is a parent of x.

Parent(lisa, mary)
Parent(lisa, sam)
Parent(bill, mary)
Parent(bill, sam)
Parent(bob, bill)
Parent(bob, eva)
Parent(eva, clara)
Parent(ralph, lisa)
Parent(ralph, fred)
Parent(sue, lisa)

Cousin(x,y) :- Parent(x,z), Parent(z,w), Parent(y,u), Parent(u,w)

(a). Show Cousin(ralph, bob)


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