> Comp 150 Final exam study guide   Dordal    


==========================================================================

Dale & Lewis exercises:

1. HTML, Ch 16: Book exercises: p 526, #40, 41

40: <a href="http://www.cs.utexas.edu/users/ndale">Dale Home Page</a>

41: The browser quits the current page and goes to the utexas page.
 
==================================
  
2. Networks, Chapter 15
    Book exercises: p 502, #32, 36, 41, 43, 44, 56, 58, 59, 60

32: A local-area Ethernet is limited in size by the physical limits built
into ethernet, but is usually much smaller than even that: one floor of
a building, typically. Larger Ethernets are built with switches.

36. An ISP provides your connection to the backbone. The backbone
itself is the largest ISPs (with full routing tables, no DEFAULT routes)
exchanging traffic.

41. DSL uses native digital signalling over the phone line. 
Analog modems send digital data encoded as an analog signal.
(As such, they are capped by the 4,000 Hertz cap for voice signals!)

43. Packets are small buffers of data, with headers. Data is sent as
packets so that lines can be shared by other connections through 
alternation of different packets from different sources.

44. Packet switching refers to a switch/router receiving a packet
and retransmitting it along the next link to its final destination.

56. IP addresses are 4-byte addresses used by the Internet Protocol.
Every host on the Internet has a unique IP address.

58. An IP address has a Network part and a Host part.

59. Class A has 7 bits for network addr and 24 bits for host.
Class B has 14 network bits and 16 host bits; class C has 21 net and 8 host bits.
To find the maximum number of networks or hosts, 
take 2 to the power of the # of bits.

60. How many hosts are possible in Class A, B, and C networks?

Class A:	2^24 hosts
Class B:	2^16 hosts
Class C:	2^8 hosts

==================================
  
3. Operating-system basics, ch 10
    Book exercises: pp 347-350: 33, 57, 58, 59, 60, 61, 62, 63, 66, 67
 
33. Timesharing means that clock interrupts are used to ensure that every
process is granted at least *some* time very promptly. This makes it possible
to run interactive processes that require rapid response, while at the same
time also allowing long, slow programs.

57. In the book's notation, a virtual address of <2,133> would mean page 2
(wherever that was), 133 bytes into it. Normally these would be expressed as
a single number; if the page size were 4K, then the 2 would represent 2*4096, 
or 8192+133=8325. 

58. From the table, page 2 is located at physical page (frame) 7, so the 
physical address is 7*1024 + 85 = 7253.

59. From the table, page 3 is located at physical page (frame) 3 (purely
coincidentally), so the physical address is 3*1024 + 555 = 3627.

60. The logical address <3,1555> is really <4,531>, since 1555=1024+531 
is bigger than 1024. Given the table shown, it is not a legal address.

61. Virtual memory (literally, having more apparent memory than is
physically present) is *implemented* by demand paging, in which frames
that have not been used recently can be written out to the disk.

62.  See Fig 10.8: New, Ready, Running, Waiting, (back to Ready), 
eventually to Terminated.

63. A process moves from Ready to Running when the scheduler gets around to it.
A process moves from Running to Waiting when it has requested some non-immediate
service from the OS (such as any I/O).
A process moves from Waiting to Ready when that I/O has completed and the
data is available.
A process moves from Running to Ready if it has consumed its immediate cpu
time quota.

66. A context switch is essentially the shift from one process (and one
set of page tables) to another.

67. Nonpreemptive scheduling means no timer interrupts, so that a process
that is not doing any I/O can hog the CPU for a long time. Preemptive means
that the timer interrupts will always give other processes a chance.
 
==================================
  
4. Artificial Intelligence, ch 13
    Book exercises: p 437, # 31, 43

31: The Turing Test is Alan Turing's proposed test for whether a computer
can be said to be indistinguishable from a person (in the context of the test).

43. Trees for chess are too large because the size is exponential.
Specifically, suppose at each turn there are 20 plausible moves 
(even that number requires substantial trimming to remove trivial or 
unlikely moves). Then to account for both sides' possible moves in one turn,
we have 20x20 = 400 cases. To try to consider what the consequences might
be 10 moves into the future, we have 400^10 cases, ~ 10^26.


==================================
  
5. Relational database model, ch 12
    Book exercises: p 405, 48, 49, 50, 51, 52
   
48. A relational DB is organized as a collection of tables.

49. Fields are "columns" of the tables: specific attributes (name, address,
date) that an object can have.

50. Other fields that the table of figure 12.7 might contain could be:
	any other field about a specific movie, eg:
	playing time
	VHS v DVD
	director
	star

51. Other fields that the table of figure 12.8 might contain could be:
	any other field about a specific customer, eg:
	city, state
	phone
	account #
	email

52. A key is a column (or sometimes set of columns) in a table that 
uniquely determines the rest of the data in that row. Specifically, 
two different rows of a table are NOT permitted to have the same key.

==========================================================================
==========================================================================
 
> 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. Discuss the security risks involved in having your browser 
> run programs downloaded remotely from a web page, and discuss 
> how java applets and Microsoft activeX each deal with these risks. 
 
If your browser runs programs on your machine that are downloaded from
the remote site, then those programs potentially have full control of your
machine.

Java deals with this by running remote programs in a "sandbox", where
access to *any* local-machine files is disallowed (unless permitted
by the user). 

ActiveX addresses this by giving the program full control, but requiring
that the program be digitally signed so you can be sure of its 
authenticity. 

Alas, in practice, being sure that a buggy program is "authentic" 
may not be worth much.

===============================================
          
> 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, and at     text using a TABLE; create 
> least one unnumbered list of         the table and show where the
> topics.                              text would go. The result should
>                                      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, and at  
   least one unnumbered list of   
   topics.    
</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>

If desired, you can add the border=0 attribute:
	<table border="0">

===============================================

> 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. [Give router tables for each router]

Note that there is no DEFAULT route here. In the tables below, 
a destination of DIRECT means it is immediately connected by one
of the links. The next_hop entry for all non-DIRECT destinations 
is thus always a router.

R1:
dest	next_hop
A	DIRECT
B	DIRECT
C	R2
D	R2
E	R2
F	R2

R2:
dest	next_hop
A	R1
B	R1
C	DIRECT
D	DIRECT
E	R3
F	R3


R3:
dest	next_hop
A	R2
B	R2
C	R2
D	R2
E	DIRECT
F	DIRECT

===============================================


> 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. Consider the following html form. Write a python cgi program that accesses
> the two fields and prints their sum:

You would be given a demo cgi program if this were on the exam.

import cgi

def main():
    form = cgi.FieldStorage()
    n1str = form.getfirst("num1", "0")
    n1    = int(n1str)		# convert to integer
    n2str = form.getfirst("num2", "0")
    n2    = int(n2str)		# convert to integer

    print "<html><body>" 	# optional?
    print "sum is ", (n1+n2)
    print "</body></html>	# optional?
    
try:
     print "Content-type: text/html\n\n" 
     main() 
except:
     cgi.print_exception()

===============================================

> 8. How would the HTML above appear on the user's screen?

Save it into a file and load it into firefox!

===============================================

> 9. Write a <FRAMESET> specification so the frames will be arranged as follows:

>    +---+---------+
>    |   |         |
>    |   +---------+
>    |   |         |
>    |   |         |
>    |   |         |
>    |   |         |
>    +---+---------+

The outer FRAMESET specifies two columns; the inner one specifies two rows.
This is the "reverse" of the lab 6 example. I will assume that the first
column is 140 pixels wide, and the upper-right box is 200 pixels deep.

Also, I've named the three regions left, top, and bottom.

<frameset cols="140,*" frameborder="NO" border="0" framespacing="0">
    <frame name="left" src="left.html">
    <frameset rows="200,*">
        <frame name="top" src="top.html">
        <frame name="bottom" src="bottom.html">
    </frameset>
</frameset>

===============================================

> 10. Write HTML for a table for the following

This is more-or-less straightforward use of <tr> for rows, and <td> for cols.

<table>
<tr>
	<td>col1</td>  	<td>col2</td>	<td>col3</td>
</tr>
<tr>
	<td>Tues</td>  	<td>Wed</td>	<td>Thurs</td>
</tr>
<tr>
	<td>3</td>  	<td>15</td>	<td>now it's time for html</td>
</tr>
<tr>
	<td>one</td>  	<td>last</td>	<td>row</td>
</tr>
</table>

===============================================

>11. What is the significance of how IP addresses are assigned?

IP addresses are assigned by the network administrator. The first part
of the address is the network part; all hosts on the same LAN share the
network part. The second, host, part is assigned locally.

This allows the entire LAN to be represented as a single router-table
entry, which allows router-table scaling to internet size.

===============================================

>12 How does TCP implement reliable transmission, given that 
> the underlying networks are inherently unreliable?  

TCP waits to see if each packet it sends is acknowledged by the receiver.
If an acknowledgement is not received in time, the data is retransmitted.
Also, all packets have a checksum for error correction, and are numbered
so that they can be delivered in the correct order.