Fall2003 Final Exam Review
Below are questions like those I plan to ask on the Final Exam (Monday 12/8 8-10:50 for 3 pm section, Tuesday 8-10:50 for 1 pm section). The exam will consist of 5-8 questions like these.
Please do try these questions! Post your answers, questions, comments, concerns, and criticisms on the pages for each question. Those comments, questions, etc. can also be about each others' answers! If someone posts an answer that you don't understand, ask about it! If you see a question here that you know the answer to, don't keep it to yourself – help your fellow students!
I will be reading your answers. Here are the ground rules for
the interaction.
- If you don't post, neither will I. I will not be posting official solutions to these problems at all! If one of you gets it right, terrific!
- I will try to always point out if an answer is wrong. I won't always point out when the answer is right.
- I am glad to work with you toward the right answer. I will give hints, and I'm glad to respond to partial guesses.
Applying your knowledge
(I) Your mother shows you this cool new image processing program she bought. "I can finally get rid of red-eye!" When she clicks the red-eye removal button, she:
- Draws a circle with her mouse around the red area in the eye.
- Then clicks on a palette of colors of what the eye color should be.
- And all the red is replaced with the selected color.
She says, "How did that work? That's amazing. How can the computer figure out what part is red?" Answer your mother's questions, (i) How did the red get replaced by the selected color? and (b) how did the computer know what part was red?
(II) You have a new computer that seems to connect to the Internet, but when you try to go to http://www.cnn.com you get a "Not Found" error. You call tech support, and they tell you to try to go to http://64.236.24.20 That works.
Now both you and the Tech know what's wrong with your computer's settings. What isn't working properly since you can get to a site via the Internet but can't get the domain name www.cnn.com to be recognized?
(III) Your father calls you. "My tech support people are saying that the company website is down because the database program is broken. What does the database have to do with our company website?"
You explain to him how databases can be integral to running large websites. Explain both (a) how the website comes to be authored through the database and (b) how the HTML is actually created.
Questions, comments, and answers for Final Exam Review Fall 2003: Applying your knowledge
Random Weather Comments
You're thinking about adding something to your HTML home page generator that will make random, relevant comments about the weather depending on the temperature.
- If it's going to be less than 32, you want to insert either "Watch out for ice!" or "Did I move North?!?"
- If it's going to be between 32 and 50, you want to insert either "I can't wait for winter to be over!" or "Come on, Spring!"
- If it's over 50 but less than 80, you want to insert either "It's getting warmer!" or "Light jacket or less weather."
- If it's over 80, you want to insert either "FINALLY! Summer!" or "Time to go swimming!"
Write a function named weathercomment that will take a temperature as input and return one of the phrases randomly. In other words, you want to use the temperature to decide which are the relevant phrases, then pick one randomly from there.
You might recall these programs from class and exam review as
examples. The top one generates gendered sentences, and the bottom one
uses return to return a sentence to be inserted into
import random
def sentence(x):
nounsM = ["Mark", "Adam", "Larry", "Jose", "Matt", "Jim"]
nounsF = ["Angela", "Laura", "Meghan", "Mary"]
verbs = ["runs", "skips", "sings", "leaps", "jumps", "climbs", "argues", "giggles"]
phrases = ["in a tree", "over a log", "very loudly", "around the bush", "while reading the Technique"]
phrases = phrases + ["very badly", "while skipping","instead of grading", "while typing on the CoWeb."]
if x =="M":
print random.choice(nounsM), random.choice(verbs), random.choice(phrases)
if x=="F":
print random.choice(nounsF), random.choice(verbs), random.choice(phrases)
import random
def sentence():
nouns = ["Mark", "Adam", "Angela", "Larry", "Jose", "Matt", "Jim"]
verbs = ["runs", "skips", "sings", "leaps", "jumps", "climbs", "argues", "giggles"]
phrases = ["in a tree", "over a log", "very loudly", "around the bush", "while reading the Technique"]
phrases = phrases + ["very badly", "while skipping","instead of grading", "while typing on the CoWeb."]
#print random.choice(nouns), random.choice(verbs), random.choice(phrases),"."
return random.choice(nouns)+" "+random.choice(verbs)+" "+random.choice(phrases)+"."
Questions, comments, and answers for Final Exam Review Fall 2003: Random Weather Comments
Handling an address book
Let's imagine that you are keeping track of all of your contacts in a file named contacts.txt in your JES directory. The format of the file is pound sign, name, colon, company, colon, phone number, colon, and key phrases that you want to remember about this contact. (You may assume that names, companies, phone numbers, and key phrases won't have colons in them.) The file might look like this:
#Calvin:Calvin & Hobbes:990-8979:Cartooning, tiger tamer, philosophy
#Luke:Skywalker Ranch:897-7765:Lightsaber battles, martial arts, philosopher
#Arthur:Camelot Inc.:453-8976:Holy grail seeker, sword puller, king
Write a function called contact that will take a keyword in a string as input. If that keyword is found in the contacts file, print the name, company, and phone number of the contact. If it is not found, print "Not Found". So, if you executed contact("king") for the above file, you would get printed out "Arthur:Camelot Inc.:453-8976"
You may want to use these programs from lecture as reference.
def findSequence(seq):
sequencesFile = getMediaPath("parasites.txt")
file = open(sequencesFile,"rt")
sequences = file.read()
file.close()
# Find the sequence
seqloc = sequences.find(seq)
#print "Found at:",seqloc
if seqloc != -1:
# Now, find the ">" with the name of the sequence
nameloc = sequences.rfind(">",0,seqloc)
#print "Name at:",nameloc
endline = sequences.find("\n",nameloc)
print "Found in ",sequences[nameloc:endline]
if seqloc == -1:
print "Not found"
def findTemperature():
weatherFile = getMediaPath("AtlantaWeather1.html")
file = open(weatherFile,"rt")
weather = file.read()
file.close()
# Find the Temperature
humloc = weather.find("Humidity")
if humloc != -1:
# Now, find the "," where the temp starts
temploc = weather.rfind(",",0,humloc)
endline = weather.find("<",temploc)
print "Current temperature:",weather[temploc+1:endline]
if humloc == -1:
print "They must have changed the page format -- can't find the temp"
Questions, comments, and answers for Final Exam Review Fall 2003: Handling an address book
Questions on Objects
- What's the difference between an instance and a class?
- How are functions and methods different?
- How is object-oriented programming different from procedural programming and functional programming?
- What is Polymorphism?
- How did biological cells influence the development of the ideas of objects?
Questions, comments, and answers for Final Exam Review Fall 2003: Questions on Objects
Questions on Functional Programming
- What's the difference between map, filter, and reduce?
- Why would anyone want to use functional programming?
- Give me an example of when people do use functional programming?
- Identify three reasons why someone should use multiple functions
rather than one big function in their programs.
Questions, comments, and answers for Final Exam Review Fall 2003: Questions on Functional Programming
Recursion
Remember this example:
>>> downUp("Hello")
Hello
ello
llo
lo
o
lo
llo
ello
Hello
Here's the code that we wrote that did it:
def downUp(word):
if len(word)==1:
print word #Print #1
return
print word #Print #2
downUp(word[1:])
print word #Print #3
a. Which print statement prints the ever-shortening ("on the way
down") words? Which print statement prints the single letter in the
middle? Which print statement prints the longer-growing words?
b. At most, how many copies of downUp are running at once with the
input "Hello"?
c. How would you modify downUp to create upDown that works like
this:
>>> upDown("Hello")
Hello
Hell
Hel
He
H
He
Hel
Hell
Hello
Questions, comments, and answers for Final Exam Review Fall 2003: Recursion
Crossword
Solve the crossword:
Across:
1. The property of methods that they can apply to more than one object.
2. A computational structure that has both data and behavior.
6. A property of objects that each holds its own data and behavior, that we can't reach inside another object.
9. What we call a function calling itself.
12. A specific function that takes a function as input and a list; it applies the function to each item of the list and returns just those items for which the input function returns true.
Down
1. An agreement for how two computers will interact; examples are HTTP and FTP.
4. A biological entity that scales well and is robust; a model for objects.
5. A network of networks based on a set of agreements.
7. A common language for database creation and manipulation.
8. A word that describes how objects can be combined (objects within objects) to create more complex structures.
10. A property of functions that are well-defined in such a way that the function does one and only one goal.
11. The address of something on the Web (abbreviation); Consists of a protocol, a server domain name, and the path to the page, image, or other object.
Questions, comments, and answers for Final Exam Review Fall 2003: Crossword
Questions on Databases
- Name some characteristics of well-designed relational databases.
- What is SQL?
- What is a join?
Questions, comments, and answers for Final Exam Review Fall 2003: Questions on Databases
Questions on Functions
- Identify three reasons why someone should use multiple functions
rather than one big function in their programs.
- What is procedural abstraction?
- What is good modularity?
Questions, comments, and answers for Final Exam Review Fall 2003: Questions on Functions
Name that algorithm!
a. Consider these two programs.
def half(filename):
source = makeSound(filename)
target = makeSound(filename)
sourceIndex = 1
for targetIndex in range(1, getLength( target)+1):
setSampleValueAt( target, targetIndex, getSampleValueAt( source,
int(sourceIndex)))
sourceIndex = sourceIndex + 0.5
play(target)
return target
and
def copyBarbsFaceLarger():
# Set up the source and target pictures
barbf=getMediaPath("barbara.jpg")
barb = makePicture(barbf)
canvasf = getMediaPath("7inX95in.jpg")
canvas = makePicture(canvasf)
# Now, do the actual copying
sourceX = 45
for targetX in range(100,100+((200-45)*2)):
sourceY = 25
for targetY in range(100,100+((200-25)*2)):
color = getColor(
getPixel(barb,int(sourceX),int(sourceY)))
setColor(getPixel(canvas,targetX,targetY), color)
sourceY = sourceY + 0.5
sourceX = sourceX + 0.5
show(barb)
show(canvas)
return canvas
What algorithm is being implemented in these two examples? Explain
the algorithm in English.
B. Consider these two programs:
def findInSortedList(something, alist):
for item in alist:
if item == something:
return "Found it!"
return "Not found"
and
def turnRed():
brown = makeColor(57,16,8)
file = r"C:\Documents and Settings\Mark Guzdial\My Documents\\mediasources\barbara.jpg"
picture=makePicture(file)
for px in getPixels(picture):
color = getColor(px)
if distance(color,brown)<100.0:
redness=getRed(px)*1.5
setRed(px,redness)
show(picture)
return(picture)
What algorithm is being implemented in these two examples? Explain
the algorithm in English.
Questions, comments, and answers for Final Exam Review Fall 2003: Name that Algorithm!
Questions on Complexity
- Who's Alan Turing and what did he do of interest to us?
- Is optimization (e.g., the ``song'' problem) class P or
intractable? What does intractable mean?
- Is the Traveling Salesman problem impossible to solve in
reasonable amounts of time?
- What is a binary search? How do linear and binary searches
differ? In "Big-O" terms?
Questions, comments, and answers for Final Exam Review Fall 2003: Questions on Complexity
JavaScript
Recall this program from the JavaScript lecture:
<html>
<head>
<title>The Simplest Possible Web Page</title>
<script>
function countToTen()
{
document.write("<ul>");
for (i=1; i<= 10; i++)
{
document.write("<li>Item number: ",i);
}
document.write("</ul>");
}
</script>
</head>
<body>
<h1>A Simple Heading</h1>
<p>This is a very simple web page.</p>
<p><image src="mediasources/barbara.jpg" />
</p>
<script> countToTen() </script>
</body>
</html>
Modify it to create a list of 100 entries just like this, starting at
100 and counting down to 1.
Questions, comments, and answers for Final Exam Review Fall 2003: JavaScript
Data structures
For each of the below data structures, define what it is, and write a small example that one can execute in a command area that uses that data structure.
- Array
- Matrix
- Tree
- List
- Hash Table
Questions, comments, and answers for Final Exam Review Fall 2003: Data structures
Compilers, interpreters, and languages, oh my!
- If you had a program written in C and you ran it through a C compiler, what would you expect to get out?
- If you had a program written in Java and you ran it through a Java compiler, what would you expect to get out?
- Why in the world would anyone want to use a virtual machine interpreter, and what does that have to do with programmable toaster ovens and cell phones?
- What's a scripting language?
Questions, comments, and answers for Final Exam Review Fall 2003: Compilers, interpreters, and languages, oh my!
Links to this Page
