http://www.cs.nyu.edu/courses/summer08/G22.3033-002/
These are example solutions. Please keep in mind that often, there is not just one correct solution to a question. If you come up with different answers, then it may be that both your answers and these answers here are correct. Of course, these answers here may also contain mistakes. If you spot a mistake, please let me know so I can correct it.
(5+6+6 = 17 points)
Sub PrintArray(Arr())
Debug.Print "PrintArray:"
For I = 0 To UBound(Arr)
Debug.Print " " & I & " " & Arr(I)
Next I
End Sub
Sub Main()
Dim fruits(2)
fruits(0) = "apple"
PrintArray fruits
fruits(1) = "orange"
fruits(2) = "banana"
PrintArray fruits
End Sub
(5 + 8 = 13 points)
(2 - ((2 - 2) - (2 * 2)))
And, Or, Xor, Eqv,
Imp) on the same line, but in fact, they do not all have the same
precedence. Does implication (“Imp”) have a higher precedence,
lower precedence, or the same precedence as conjunction (“And”)
in VBA? Describe experiments for answering this question.
(10 points) Write a function that computes the Euclidian distance between two arrays. The Euclidian distance between two vectors A and B is defined as
sqrt((A0-B0)^2 + ... + (An-Bn)^2)
For example, consider the following test driver:
Sub Main()
Dim x1(2) As Double, x2(2) As Double
x1(0) = 0: x1(1) = 0: x1(2) = 0
x2(0) = 0: x2(1) = 0: x2(2) = 0
Debug.Print EuclidDistance(x1, x2)
x2(0) = 1
Debug.Print EuclidDistance(x1, x2)
x1(2) = 1
Debug.Print EuclidDistance(x1, x2)
End Sub
The program should print 0, 1, and 1.41421.
(10 points)
Write a function AverageRows that computes the average of each row in a two-dimensional array, and writes the results to a one-dimensional array. For example, consider the following test driver:
Sub Main()
Dim x(1, 2) As Double
x(0, 0) = 1: x(0, 1) = 2: x(0, 2) = 0
x(1, 0) = 0: x(1, 1) = 0: x(1, 2) = 2
Dim y(1) As Double
Call AverageRows(y, x)
Debug.Print y(0) & ", " & y(1)
End Sub
The program should print 1, 0.66667.
(5+5 = 10 points)
Option Explicit
Public Celsius As Double
Public Property Let Fahrenheit(f As Double)
Celsius = 5 * (f - 32) / 9
End Property
Public Property Get Fahrenheit() As Double
Fahrenheit = (9 * Celsius / 5) + 32
End Property
(5 + 5 = 10 points)
(15 points) Consider the following abstract class StringMap.
Option Explicit
Public Function size() As Integer
End Function
Public Function Contains(key As String) As Boolean
End Function
Public Property Let Data(key As String, Value As Variant)
End Property
Public Property Get Data(key As String)
End Property
StringMap defines the interface for a container that maps strings
to values. Write a subclass SimpleStringMap that implements
StringMap. For example, consider the following test driver:
Sub driveStringMap()
Dim m As StringMap
Set m = New SimpleStringMap
m.Data("apple") = "Apfel"
m.Data("pear") = "Birne"
Debug.Print m.size & " " & m.Data("apple")
m.Data("apple") = "pomme"
Debug.Print m.size & " " & m.Data("apple")
End Sub
The program should print 2 Apfel, 2 pomme. Don't worry
about performance, just write a simple correct implementation of the
interface. Make sure that your implementation works for an unbounded
number of elements, not just two.
(15 points) A dendrogram is a tree diagram that arranges similar items in clusters. For example, the following dendrogram shows items A-E in a hierarchy, annotating each cluster with a similarity score.
A textual specification for the above example dendrogram is
(((A:1.5:B):2.8:(C:1.9:D)):4.8:E)
Your task is to design a dialog box for drawing a dendrogram that looks like this:
This will require you to create a user form, and to wire it up with the
appropriate callbacks. To do the actual drawing, you can use the
subroutine DrawDendrogram defined below.
Sub ParseDendrogram(ByVal spec As String, ByRef lspec As String, _
ByRef y As Double, ByRef rspec As String)
Dim c1 As Integer, c2 As Integer, depth As Integer, i As Integer
c1 = -1: c2 = -1: depth = 0
For i = 1 To Len(spec)
Select Case Mid(spec, i, 1)
Case "("
depth = depth + 1
Case ")"
depth = depth - 1
Case ":"
If 1 = depth Then If c1 < 0 Then c1 = i Else c2 = i
End Select
Next i
lspec = Mid(spec, 2, c1 - 2)
y = CDbl(Mid(spec, c1 + 1, c2 - c1 - 1))
rspec = Mid(spec, c2 + 1, Len(spec) - c2 - 1)
End Sub
Sub DrawDendrogram(ByVal cvs As Canvas, ByVal spec As String, _
ByRef x As Double, ByRef y As Double)
' The original x is the position where the left-most leaf should go.
' On return, x = width of subtree and y = height of subtree.
Dim ox As Double
ox = x
If Mid(spec, 1, 1) = "(" Then
Dim lspec As String, rspec As String
ParseDendrogram spec, lspec, y, rspec
Dim lx As Double, ly As Double, rx As Double, ry As Double
lx = x
DrawDendrogram cvs, lspec, lx, ly
rx = ox + lx
DrawDendrogram cvs, rspec, rx, ry
x = lx + rx
Dim x1 As Double, x2 As Double
x1 = ox + 0.5 * (lx - 1): x2 = ox + lx + 0.5 * (rx - 1)
With ActiveWindow.Selection.SlideRange.Shapes
.AddLine(cvs.x(x1), cvs.y(ly), cvs.x(x1), cvs.y( y)).Select
.AddLine(cvs.x(x1), cvs.y( y), cvs.x(x2), cvs.y( y)).Select
.AddLine(cvs.x(x2), cvs.y( y), cvs.x(x2), cvs.y(ry)).Select
End With
Else
x = 1: y = 0
ActiveWindow.Selection.SlideRange.Shapes.AddLabel( _
msoTextOrientationHorizontal, cvs.x(ox),cvs.y(0), 0.4,0.4).Select
ActiveWindow.Selection.ShapeRange.TextFrame.TextRange.Text = spec
End If
End Sub
The DrawDendrogram subroutine relies on an instance of class
Canvas to translate logical x/y positions into physical positions
on the slide. The class module Canvas is defined as follows:
Public xbase As Double, xscale As Double
Public ybase As Double, yscale As Double
Public Function x(ByVal logicalX As Double)
x = xbase + xscale * logicalX
End Function
Public Function y(ByVal logicalY As Double)
y = ybase - yscale * logicalY
End Function
(10 points) Add explicit type annotations to the following VBA module.
Function geometricMean(arr())
geometricMean = 1
For i = LBound(arr) To UBound(arr)
geometricMean = geometricMean * arr(i)
Next i
n = 1 + UBound(arr) - LBound(arr)
geometricMean = geometricMean ^ (1.0 / n)
End Function
Sub main()
Dim A(1)
A(0) = 1: A(1) = 2
Debug.Print geometricMean(A)
End Sub
(10 points) Consider the following excerpt of Perl's operator table.
Operator Arity Associativity Description
** 2 right exponentiation
* 2 left multiplication
= 2 right assignment
Fully parenthesize the following expression:
$x = $y = 3 ** 3 ** 3 * 2.
(4+3+3 = 10 points)
(7+6 = 13 points)
(0[xX])?[a-fA-F0-9]+. Rewrite this regular expression using
only the “essential” features of formal regular expressions.
ps -l” command. For example, consider the
following output:
doowop1:~> ps -l
F S UID PID PPID C PRI NI ADDR SZ WCHAN TTY TIME CMD
0 S 1088 23431 23421 0 75 0 - 18991 wait pts/4 00:00:00 bash
0 R 1088 23641 23431 0 77 0 - 15863 - pts/4 00:00:00 ps
The PID and PPID of the line of output for bash are 23431 and 23421.
(5 + 7 = 12 points)
#!/usr/bin/perl -w
$a = "-";
sub f {
our $a = "f";
sub g { local $a = "g"; h() }
sub h { print $a, "\n" }
g();
print $a, "\n"
}
f()
This homework practices the “How to learn a language” steps from the lecture on 5/29/2008:
doowop1. Here is a list of compute
servers:
http://www.cims.nyu.edu/systems/resources/computeservers/.
(2+0+2+2 = 6 points) Consider the following Perl script:
#!/usr/bin/perl -w
while (<>) {
chomp;
push @rows, [ split /,\s/ ];
}
for $row (@rows) {
for ($i = 0; $i < @$row; $i++) {
$w = length $row->[$i];
$widths[$i] = $w if !$widths[$i] || $w > $widths[$i];
}
}
for $row (@rows) {
for ($i = 0; $i < @$row; $i++) {
print " " x (1 + $widths[$i] - length $row->[$i]);
print $row->[$i];
}
print "\n";
}
csv2fixed.pl, and the input into another file, for example,
table.csv. Then, you do perl csv2fixed.pl < input.csv).
0, 0, 10, 0
10, 0, 10, 0
10, -10, 10, 0
$_?
@$row return, and why? (This might be one of those
cases where you need to ask a Perl-guru if you can't figure it out
yourself.)
(8 points) Extend the script from problem hw03-3 so it computes the average of each column, and prints it as an added row at the bottom of the output. For example, given this input:
3, 4, 3
0, 0, 0
4, 5, 2.5
2, -1, 4
your script should print this output:
3 4 3
0 0 0
4 5 2.5
2 -1 4
2.25 2 2.375
For example, the average of column 3,0,4,2 is 2.25.
(8 points) Extend the script from problem hw03-3 so it computes the Euclidian distance of each row to the first row, and prints it as an added column at the right of the output. For example, given this input:
3, 4, 3
0, 0, 0
4, 5, 2.5
2, -1, 4
your script should print this output:
3 4 3 0
0 0 0 5.8309518948453
4 5 2.5 1.5
2 -1 4 5.19615242270663
For example, the first row has zero distance from itself. The second row
has Euclidian distance 5.8309518948453 from the first row.
(5+5 = 10 points)
(4+4+4 = 12 points)
sub isprime {
my ($num, $f, @factors) = ($_[0], 2);
while (1 != $num) {
if (0 == $num % $f) {
return $f == $num unless wantarray;
push @factors, $f;
$num /= $f;
} else {
$f++;
}
}
return @factors;
}
Give four examples for calling this function: with a prime or a non-prime, in a list context or a scalar context.
sub map_block (&@) {
my ($block, @listin) = @_;
my @listout = ();
push @listout, &$block() for (@listin);
return @listout;
}
Explain where and how this function uses the default variable $_.
map_block above to add 5 to every
element of a list. For example, your code should turn the list
1,2,3 into the list 6,7,8.
(10 + 4 = 14 points)
TwoWayMap. An instance of this class should behave like an
associative array that maps keys to values, but should also work in the
reverse direction, mapping values back to keys. For example, the
following code:
use TwoWayMap;
our $e2g = new TwoWayMap;
$e2g->put('apple', 'Apfel');
$e2g->put('pear', 'Birne');
print $e2g->get('apple'), "\n";
print $e2g->rev('Apfel'), "\n";
print $e2g->rev('Birne'), "\n";
should print Apfel, apple, pear. You can assume
that all keys and values are strings.
TwoWayMap so that it also
accepts an initialization list. For example, the following code:
use TwoWayMap;
our $e2g = new TwoWayMap 'grape' => 'Traube', 'onion' => 'Zwiebel';
print $e2g->get('grape'), "\n";
print $e2g->rev('Traube'), "\n";
print $e2g->rev('Zwiebel'), "\n";
should print Traube, grape, onion.
(14 points) Write a Perl script that reads a table and writes a dendrogram specification. Consider this example input:
A, 4, 0
B, 8, 5
C, 4, 4
There are three rows. Hierarchical clustering starts by putting each row
in a cluster by itself. Then, it finds the two clusters with the
smallest Euclidian distance. The distance between clusters A and
C is sqrt((4-4)**2+(4-0)**2)=4, and these two clusters are
closest to each other. Hierarchical clustering combines them to obtain a
partial dendrogram specification (A:4:C). The combined cluster
(A:4:C) has two rows and the arithetic mean [(4+4)/2, (0+4)/2] = [4, 2]. Thus, the current set of clusters is:
(A:4:C) => 2 x [4, 2]
B => 1 x [8, 5]
Now, hierarchical clustering repeats the same step. There are only two
clusters left, so those are automatically the two clusters with the
smallest Euclidian distance. The distance between the two remaining
clusters is sqrt((8-4)**2+(5-2)**2)=5. Hierarchical clustering
combines them as before, using a weighted average. The set of clusters
becomes:
((A:4:C):5:B) => 3 x [5.33, 3]
Since there is only one cluster left, hierarchical clustering
terminates. Your Perl script should print the final dendrogram
specification ((A:4:C):5:B) to standard output.
You can then copy-and-paste the output of your Perl script into the VBA dialog box you designed for hw02-4 to visualize the dendrogram as a tree. With appropriate scaling, this is what it looks like:
Here is the link to the example solution from hw02-4:
http://www.cs.nyu.edu/courses/summer08/G22.3033-002/solutions-hw02-4.ppt
(4+4+4 = 12 points) Consider the following PHP code.
<?php
class Vector {
var $x = 0;
var $y = 0;
function __construct($x, $y) {
$this->x = $x;
$this->y = $y;
}
function __get($propName) {
if ($propName == 'length')
return sqrt($this->x * $this->x + $this->y * $this->y);
}
function __set($propName, $value) {
if ($propName == 'length') {
$oldLen = sqrt($this->x * $this->x + $this->y * $this->y);
$this->x *= $value / $oldLen;
$this->y *= $value / $oldLen;
}
}
}
$v = new Vector(2,3);
printf("|%.2f, %.2f| = %.2f<br/>\n", $v->x, $v->y, $v->length);
$v->length = 5;
printf("|%.2f, %.2f| = %.2f<br/>\n", $v->x, $v->y, $v->length);
?>
(4+4+4 = 12 points) Consider the following PHP code.
<?php
class Vector {
var $x = 0;
var $y = 0;
function __construct($x, $y) {
$this->x = $x;
$this->y = $y;
}
function length() {
return sqrt($this->x * $this->x + $this->y * $this->y);
}
}
$a = array(new Vector(0,4), new Vector(-3,4), new Vector(2,3));
function cmp_vector($a, $b) {
$aa = $a->length(); $bb = $b->length();
return $aa < $bb ? -1 : $aa == $bb ? 0 : 1;
}
usort($a, "cmp_vector");
foreach ($a as $i => $v)
printf("%2d => (%d, %d)<br/>\n", $i, $v->x, $v->y);
?>
(5+5+5 = 15 points)
http://www.cs.nyu.edu/~your_cims_id/hw05-3a.html
For example, if your_cims_id is hirzel, then the URL would
be:
.htaccess file to create a password protected HTML page
that can be viewed from any web browser using the following URL:
http://www.cs.nyu.edu/~your_cims_id/php/hw05-3b.html
For example, with your_cims_id as hirzel, you get the
following URL, which requires you to enter the user name student
and the password P_8sh_P:
http://www.cs.nyu.edu/~hirzel/php/hw05-3b.html
Please create a user name grader. Please indicate the URL and the
password for grader in your submission, so that Robert Soulé
can access your web page.
.htaccess file,
create a PHP script hw05-3c.php with the following code:
<html><body>
<?php
if(!empty($_GET['who'])) { echo "Hi, {$_GET['who']}.";}
?>
<form action="<?php echo $_SERVER[PHP_SELF]; ?>" method=get>
Who shall be greeted: <input type="text" name="who" />
</form>
</body></html>
(See also http://www.cs.nyu.edu/~hirzel/php/hw05-3c.phps).
Test it and make sure it works. For example, for your_cims_id
hirzel, user name student, and password P_8sh_P,
this URL runs the script for you:
(11 points) Write a PHP script that converts cooking quantities, units,
and ingredients to metric units. For data input, use a form that
provides three text fields, one each for Quantity, Unit, and
Ingredient. When the user enters values for all three and clicks the
submit button, your script should print the converted result at the top
of the web page. Your script should be a self-processing page, in other
words, use the same page for input and output. For example, if the user
enters the values 3, cup, and flour in the three
input fields and clicks the Submit button, your script should
return a page that looks like this:
Your PHP script should offer the same kinds of conversions as the Perl example from the lecture slides. Please copy-and-paste the source code of your script into your homework submission. In addition, please put the script online at the following URL (replacing your_cims_id by your CIMS id):
http://www.cs.nyu.edu/~your_cims_id/php/hw05-4.php
(3+3+4 = 10 points) Consider the following Perl regular expression:
^[0-9]+(\.[0-9]*)?$
0
if that 0 is the entire part before the decimal point. For
example, the string "0.99" should still match, but the string
"001.23" should not match.
(3+3+4 = 10 points)
(4+2+2+2 = 10 points) Consider the following Perl code:
@x = (7, 8, 9);
$y = (7, 8, 9);
print @x + 0;
for $i (@x) { print $i }
for $i ($y) { print $i }
(2+4+4+4 = 14 points) Consider the following HTML document with JavaScript.
<html><head>
<meta http-equiv="Content-Script-Type" content="text/javascript" />
<script>
function curry(f, x) {
return function(y) {
return f(x, y);
}
}
</script>
</head><body>
<h1><a href="http://en.wikipedia.org/wiki/Currying">Currying</a></h1>
<script>
function add(x,y){ return x + y; }
var inc = curry(add, 1);
var double = curry(function(x,y){ return x * y; }, 2);
document.write(inc(5) + "<br/>\n");
document.write(double(5) + "<br/>\n");
</script>
</body></html>
inc,
what is the function, and what is the environment? And in the
environment, what is f bound to, and what is x bound to?
double, what is the function, and what is the
environment? And in the environment, what is f bound to, and what
is x bound to?
curry to create a closure for squaring a
number. For example, square(5) should return 25.
(2+4+4 = 10 points) Consider the following HTML document with JavaScript.
<html><head>
<meta http-equiv="Content-Script-Type" content="text/javascript" />
<script>
function C() { }
C.prototype.f = function() { return 'Cf'; }
C.prototype.g = function() { return 'Cg'; }
C.prototype.h = function() { return 'Ch'; }
function D() { }
D.prototype = new C();
D.prototype.constructor = D;
D.prototype.g = function() { return 'Dg'; }
function E() { }
E.prototype = new D();
E.prototype.constructor = E;
E.prototype.h = function() { return 'Eh'; }
</script>
</head><body>
<script>
var x = new D();
document.write(x.f() + ', ' + x.g() + ', ' + x.h() + "\n<br/>");
var y = new E();
document.write(y.f() + ', ' + y.g() + ', ' + y.h() + "\n<br/>");
</script>
</body></html>
x?
y?
(12 points) Write an HTML document with a form that has two text input fields and two buttons. When the user enters a value in the “Celsius” field and presses the “To Fahrenheit” button, that should trigger a JavaScript event handler that shows the converted temperature in the “Fahrenheit” input field. Likewise, when the user enters a value in the “Fahrenheit” field and presses the “To Celsius” button, that should trigger a JavaScript event handler that shows the converted temperature in the “Celsius” input field. Below is an example screen shot. Remember to test your code in both the Mozilla Firefox and the Microsoft Internet Explorer web browsers.
(14 points) Write a constructor PriorityQueue that creates an object
that supports three methods: push, pop, and peek. A
priority queue allows elements to be added in any order, but always
returns the smallest element. The push method adds an element to
the queue. The pop method removes and returns the smallest
element in the queue. The peek method also returns the smallest
element in the queue, but does not remove it. If you put your code in a
file called PriorityQueue.js, then you can test it with the following
driver:
<html><head>
<meta http-equiv="Content-Script-Type" content="text/javascript" />
<script src="PriorityQueue.js"></script>
<script>
var q = new PriorityQueue();
function doPush() {
var val = document.driver.push.value;
q.push(val);
var log = document.getElementById("log");
log.innerHTML += "push(" + val + ")\n<br/>";
}
function doPop() {
var val = q.pop();
var log = document.getElementById("log");
log.innerHTML += "pop() -> " + val + "\n<br/>";
}
function doPeek() {
var val = q.peek();
var log = document.getElementById("log");
log.innerHTML += "peek() -> " + val + "\n<br/>";
}
</script>
</head><body>
<form name="driver">
<input type="text" name="push">
<input type="button" value="Push" onclick="doPush();">
<br/>
<td><input type="button" value="Pop" onclick="doPop();">
<br/>
<td><input type="button" value="Peek" onclick="doPeek();">
</form>
<span id="log"></span>
</body></html>
The following screen snapshot demonstrates the behavior of a priority queue through a sequence of calls.
(6+6 = 12 points) Try the Google Suggest web application, which is available at http://www.google.com/webhp?complete=1&hl=eN. Now think about what you would need to do to write a similar web application yourself.
(6+6+6 = 18 points) Consider the following PHP script.
<html><head>
<title>Translation Database</title>
</head><body>
<!-- show form for user input -->
<form action="<?php echo $_SERVER[PHP_SELF]; ?>" method=get>
<table border=0>
<tr><td>English: <td><input type="text" name="eng"><br/>
<tr><td>Translated: <td><input type="text" name="tra"><br/>
</table>
<input type="radio" name="request" value="add">
Add</br>
<input type="radio" name="request" value="e2f">
Get (English to Translated)</br>
<input type="radio" name="request" value="f2e">
Get (Translated to English)</br>
<input type="radio" name="request" value="del">
Delete</br>
<input type="submit" value="submit">
</form>
<!-- open database, and create table if it does not yet exist -->
<?php
$db = sqlite_open("/home/hirzel/data/sqlite2", 0666, $err);
if ($err) { die($err); }
sqlite_query($db, "SELECT * FROM Translate", SQLITE_BOTH, $err);
if ($err) {
echo "Table 'Translate' does not yet exist, creating it ...<br/>";
$q = "CREATE TABLE Translate"
. "(English VARCHAR(50), Translated VARCHAR(50))";
sqlite_query($db, $q, SQLITE_BOTH, $err);
if ($err) { die($err); }
} else {
echo "Reopened table 'Translate'.<br/>";
}
?>
<!-- process input, if any -->
<?php
if ("add" == $_GET[request]) {
$q = "INSERT INTO Translate VALUES("
. "'" . addslashes($_GET[eng]) . "', "
. "'" . addslashes($_GET[tra]) . "')";
sqlite_query($db, $q);
if ($err) { die($err); }
echo "Add English '" . htmlentities($_GET[eng]) . "', " .
"Translated '" . htmlentities($_GET[tra]) . "' succeeded.";
} else if ("e2f" == $_GET['request']) {
$q = "SELECT Translated FROM Translate WHERE English = "
. "'" . addslashes($_GET[eng]) . "'";
$rows = sqlite_query($db, $q);
if ($err) { die($err); }
$row = sqlite_fetch_array($rows, SQLITE_BOTH);
if ($err) { die($err); }
echo "Get English '" . htmlentities($_GET[eng]) . "' returned "
. "Translated '" . htmlentities($row[Translated]) . "'.";
} else if ("f2e" == $_GET['request']) {
# put your code here
echo "Sorry, lookup from Translated to English not yet implemented.";
} else if ("del" == $_GET['request']) {
# put your code here
echo "Sorry, deletion not yet implemented.";
}
?>
</body>
data directory, for example,
like this:
cd ~
mkdir data
chmod 777 data
The file permissions must enable the web server to read and write your data directory. You will also need to change the line
$db = sqlite_open("/home/hirzel/data/sqlite2", 0666, $err);
to use your own directory. When you submit this homework, please indicate the URL at which the script is running.
(8 points) Write a PHP script that uses a session variable to count how often the user has visited it. For example, after the second visit, the page should look like this:
(6 + 6 = 12 points) Consider the AJAX application from the lecture slides from 7/3/2008, repeated here for your convenience.
a.html
<html><head>
<meta http-equiv="Content-Script-Type" content="text/javascript" />
<script src="c.js"></script>
</head><body bgColor="#00ff00">
Time: <span id="time">(please click button)</span>
<form name="in">
<input type="button" value="Toggle Color" onclick="localChange();">
<input type="button" value="Request Time" onclick="sendRequest();">
</form>
</body></html>
b.php
<?php sleep(3); echo date('h:i:s') ?>
c.js
function localChange() {
var blue = document.bgColor == '#0000ff'
document.bgColor = blue ? '#00ff00' : '#0000ff';
}
function sendRequest() {
document.getElementById('time').innerHTML = '(please wait)';
var xhr = false;
function handleResponse() {
if (4 == xhr.readyState && 200 == xhr.status)
document.getElementById('time').innerHTML = xhr.responseText;
}
try { xhr = new XMLHttpRequest(); } catch(e1) {
try { xhr = new ActiveXObject("Msxml2.XMLHTTP"); } catch(e2) {
try { xhr = new ActiveXObject("Microsoft.XMLHTTP"); } catch(e3) {
alert('Could not create XMLHttpRequest object.'); } } }
xhr.open('GET', 'b.php?nonce=' + Math.random(), true);
xhr.onreadystatechange = handleResponse;
xhr.send(null);
}
Questions
(4+3+3 = 10 points) Consider the following JavaScript code:
var a = 1;
function outer(b) {
function inner() {
document.write("a=" + a + ", b=" + b + "</br>\n");
}
return inner;
}
var my_closure = outer(2);
my_closure();
a = 3;
my_closure();
my_closure?
my_closure?
(2+5+3 = 10 points) Consider a web email application that lets the user create an attachment. After the user selects the file to attach, the application uploads it to the server in the background. At the same time, the user can interact normally with the application. When the file is uploaded, the page changes so the user knows the file is at the server.
(4+3+3 = 10 points)
(3+12 = 15 points) Consider the following buggy Perl script:
#!/usr/bin/perl # 1
use strict; use warnings; # 2
# 3
sub compute_avg { # 4
my @sums; # 5
my $nrows = $#_; # 6
for (my $i=0; $i<$nrows; $i++) { # 7
my $row = $_[$i]; # 8
for (my $j = 0; $j < @$row; $j++) { # 9
$sums[$j] += $row->[$j]; #10
} #11
} #12
my @result; #13
for (my $i = 0; $i < @sums; $i++) { #14
$result[$i] = $sums[$i] / $nrows; #15
} #16
return @result; #17
} #18
#19
sub to_string { #20
my $result = ""; #21
for my $row (@_) { #22
$result .= " " . $_ for (@$row); #23
$result .= "\n"; #24
} #25
return $result; #26
} #27
#28
our @input = ([2, 1, 3], [0, 1, 1], [4, 1, 2]); #29
print "initial input:\n" . to_string @input; #30
our @expected = ([2, 1, 3], [0, 1, 1], [4, 1, 2], [2, 1, 2]); #31
print "expected output:\n" . to_string @expected; #32
our @avg = compute_avg @input; #33
our @output = @input; #34
push @output, [ @avg ]; #35
print "actual output:\n" . to_string @output; #36
1 Hypothesis (e.g., variable has wrong value in given line)
Experiment (e.g., run debugger, set breakpoint, inspect value)
Observation (e.g., the value of the variable at that place)
Conclusion (e.g., hypothesis verified, falsified, inconclusive)
2 Hypothesis ...
Experiment ...
Observation ...
Conclusion ...
3 ...
...
(0 points) When you learn a new language, a good way to make progress is by solving some moderately difficult programming problems. At the same time, when you learn a new algorithm, a good way to understand and remember it is by implementing it. Therefore, I suggest you combine the two by using one of the new languages you learned in prior lectures to implement one of the debugging algorithms you learned in the most recent lecture.
ddmin algorithm to JavaScript or PHP. You can start from
the Perl version on the slides, or you can start from the publicly
available Python version by Andreas Zeller.
(4+6 = 10 points) Consider the following Python script.
#!/usr/bin/env python
class Tree:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def preorder(self):
yield self.value
if self.left:
for v in self.left.preorder():
yield v
if self.right:
for v in self.right.preorder():
yield v
my_tree = Tree(1,
Tree(2,Tree(4),Tree(5)),
Tree(3,Tree(6),Tree(7)))
def print_preorder(tree):
print 'preorder:'
for y in my_tree.preorder():
print y
print_preorder(my_tree)
Tree.inorder that walks the tree
in-order instead of pre-order. An in-order walk first visits all nodes
in the left subtree, then the current node, then all nodes in the right
subtree. The following picture shows a tree for which an in-order
walk would visit nodes in alphabetical order:
d
/ \
b f
/ \ / \
a c e g
After you write the generator Tree.inorder, the following code:
def print_inorder(tree):
print 'inorder:'
for y in my_tree.inorder():
print y
print_inorder(my_tree)
should cause the following output to be printed:
inorder:
4
2
5
1
6
3
7
(4+6 = 10 points) Consider the following Ruby script.
#!/usr/bin/env ruby
class Tree
attr_accessor :value, :left, :right
def initialize(value, *leftRight)
@value = value
if 0 < leftRight.length()
@left = leftRight[0]
@right = leftRight[1]
end
end
def preorder()
yield @value
if @left
@left.preorder {|v| yield v }
end
if @right
@right.preorder {|v| yield v }
end
end
end
$my_tree = Tree.new(1,
Tree.new(2, Tree.new(4), Tree.new(5)),
Tree.new(3, Tree.new(6), Tree.new(7)))
def print_preorder(tree)
puts 'preorder:'
tree.preorder {|y| puts y.to_s + "\n" }
end
print_preorder($my_tree)
print_sum that uses the iterator
to compute the sum of all values in the tree. For example, the following
call:
print_sum($my_tree)
should cause the following output to be printed:
sum:
28
(7+4+4=15 points)
(15 points) Consider the following skeleton PHP script:
#!/usr/bin/env php
<?php
class Tree {
# --- add your code here ---
}
$myTree = new Tree(1,
new Tree(2, new Tree(4), new Tree(5)),
new Tree(3, new Tree(6), new Tree(7)));
function printPreorder($tree) {
echo "preorder:\n";
$tree->preorder(create_function('$v', 'echo "$v\n";'));
}
printPreorder($myTree);
?>
Implement the body of class Tree so that the construction
(new Tree(...)) and iteration ($tree->preorder(...))
at the bottom of the script work, and produce the same output as
the equivalent Python and Ruby scripts above.
(3+3+4 = 10 points) Consider the following BNF grammar rules:
| identifier | ::= | id_start | id_start id_rest
| |
| id_rest | ::= | id_inner | id_inner id_rest
| |
| id_start | ::= | _ | letter
| |
| id_inner | ::= | _ | letter | digit
| |
| letter | ::= | A | B | ... | Z | a | b | ... | z
| |
| digit | ::= | 0 | 1 | ... | 9
|
(2+2+2+2+2 = 10 points) Please keep your answers to the following questions short.
echo statement in PHP go?
document.write() call in JavaScript go?
(5+5 = 10 points)
"pe" . ("a", "rl").
("a", "rl")?
("a", "rl")?
("a", "rl") after type conversion, but before the converted value gets used?
"pe" . ("a", "rl")?
sqrt @a, assuming array @a has the value (1,9,4,9).
@a?
@a?
@a after type conversion, but before the converted value gets used?
sqrt @a?
(4+6 = 10 points) Consider the following Python code.
numbers = [1, 2]
extensions = ["html", "pdf"]
quizzes = [("quiz%d.%s" % (n, e)) for n in numbers for e in extensions]
quizzes at the end of the code snippet?
@numbers = (1, 2);
@extensions = ("html", "pdf");
Translate the third line of the Python code to Perl.
(3+3+4 = 10 points)
Consider the following PHP script editor_poll.php.
<html><body>
<?php if (empty($_GET['editor'])) { ?>
<form action="editor_poll.php">
<input type="radio" name="editor" value="emacs" /> Emacs
<input type="radio" name="editor" value="notepad" /> Notepad
<input type="radio" name="editor" value="vi" /> Vi
<input type="radio" name="editor" value="other" /> Other
<br />
<input type="submit" value="submit" />
</form>
<?php } else { ?>
You selected: <?php echo $_GET['editor'] ?>
<?php } ?>
</body></html>
(2+2+2+4 = 10 points) Consider the following JavaScript code.
function Vector(x, y) { this.x = x; this.y = y; }
Vector.prototype.length = function() {
q = this.x * this.x + this.y * this.y;
return Math.sqrt(q);
}
v = new Vector(3, 4);
document.write(v.length());
v?
v?
new in JavaScript does.
Sub PrintArray(Arr() As String)
Debug.Print "PrintArray:"
For I% = 0 To UBound(Arr)
Debug.Print " " & I & " " & Arr(I)
Next I
End Sub
Sub Main()
Dim fruits(2) As String
fruits(0) = "apple"
PrintArray fruits
fruits(1) = "orange"
fruits(2) = "banana"
PrintArray fruits
End Sub
2 - (2 - 2 - 2 * 2)
Function EuclidDistance(A() As Double, B() As Double) As Double
EuclidDistance = 0
Dim I As Integer
For I = LBound(A) To UBound(A)
EuclidDistance = EuclidDistance + (A(I) - B(I)) ^ 2
Next I
EuclidDistance = EuclidDistance ^ 0.5
End Function
Sub AverageRows(Result() As Double, Rows() As Double)
Dim I As Integer, J As Integer
For I = LBound(Rows, 1) To UBound(Rows, 1)
Result(I) = 0
For J = LBound(Rows, 2) To UBound(Rows, 2)
Result(I) = Result(I) + Rows(I, J)
Next J
Result(I) = Result(I) / (1 + UBound(Rows, 2) - LBound(Rows, 2))
Next I
End Sub
Celsius, which is defined like a
variable, and Fahrenheit, which is defined by two property
methods Let and Get. The following code reads and writes
both:
Dim t As Temperature
Set t = New Temperature
t.Celsius = 25
Debug.Print t.Celsius & " C = " & t.Fahrenheit & " F"
t.Fahrenheit = 25
Debug.Print t.Celsius & " C = " & t.Fahrenheit & " F"
These properties encapsulate a temperature value, which is stored internally as Celsius, but can be accessed as both Celsius and Fahrenheit. The user can not tell the difference between the two properties.
Get and Let methods for reading and writing the value,
and checking that the value is written only once. For example:
Private myPropValue
Private myPropWritten As Boolean
Sub Class_Initialize()
myPropWritten = False
End Sub
Public Property Let myProp(val)
If Not myPropWritten Then
myPropValue = val
myPropWritten = True
End If
End Property
Public Property Get myProp()
myProp = myPropValue
End Property
myControl, then the VBA execution engine calls back
to subroutine myControl_Click when the user clicks a button.
Option Explicit
Implements StringMap
Private used As Integer
Private keys() As String
Private values() As String
Sub Class_Initialize()
used = 0
ReDim keys(2)
ReDim values(2)
End Sub
Public Function StringMap_Size() As Integer
StringMap_Size = used
End Function
Public Function StringMap_Contains(key As String) As Boolean
Dim i As Integer
For i = 0 To used - 1
If keys(i) = key Then StringMap_Contains = True: Exit Function
Next i
StringMap_Contains = False
End Function
Public Property Let StringMap_Data(key As String, val As Variant)
Dim i As Integer
For i = 0 To used - 1
If keys(i) = key Then values(i) = val: Exit Property
Next i
If UBound(keys) = used - 1 Then ReDim keys(2 * used)
keys(i) = key
values(i) = val
used = used + 1
End Property
Public Property Get StringMap_Data(key As String)
Dim i As Integer
For i = 0 To used - 1
If keys(i) = key Then StringMap_Data = values(i): Exit Property
Next i
End Property
You can find the full example solution in the following Powerpoint presentation:
http://www.cs.nyu.edu/courses/summer08/G22.3033-002/solutions-hw02-4.ppt
Here, we just describe the most important parts. The GUI is illustrated in the questions. The code sheet requires two event handlers, for the two buttons:
Private Sub cmdDraw_Click()
Dim cvs As Canvas
Set cvs = New Canvas
Const dpi As Double = 72
cvs.xbase = dpi * CDbl(txtXbase.Value)
cvs.xscale = dpi * CDbl(txtXscale.Value)
cvs.ybase = dpi * CDbl(txtYbase.Value)
cvs.yscale = dpi * CDbl(txtYscale.Value)
Dim spec As String, x As Double, y As Double
spec = txtSpec.Value: x = 0: y = 0
DrawDendrogram cvs, spec, x, y
End
End Sub
Private Sub UserForm_Click()
End
End Sub
The handler code assumes that you have renamed the different form
elements appropriately. For example, the text box for the specification
is called txtSpec. To do the renaming, right-click on a form
element, select “properties” from the context menu, then edit the
“(Name)” field. While you are there, you should also initialize the
“Value” properties with reasonable defaults.
Function geometricMean(arr() As Double) As Double
Dim i As Integer, n As Integer
geometricMean = 1
For i = LBound(arr) To UBound(arr)
geometricMean = geometricMean * arr(i)
Next i
n = 1 + UBound(arr) - LBound(arr)
geometricMean = geometricMean ^ (1.0 / n)
End Function
Sub main()
Dim A(1) As Double
A(0) = 1: A(1) = 2
Debug.Print geometricMean(A)
End Sub
$x = ($y = ((3 ** (3 ** 3)) * 2))
_E in the form's code sheet.
(|0x|0X)
(a|b|c|d|e|f|A|B|C|D|E|F|0|1|2|3|4|5|6|7|8|9)
(a|b|c|d|e|f|A|B|C|D|E|F|0|1|2|3|4|5|6|7|8|9)*
^\s*(?:\S+\s+){3}(\S+)\s+(\S+)
g f. Variable $a in Function g
uses dynamic scoping. Therefore, it is visible in the callee function
h: since g is the closest calling function, it hides
variable $a from the nesting function f. The second print
statement in function f, on the other hand, does not see
$a from function g anymore, because it has already
returned, and is not a calling function anymore, let alone the closest
one.
#!/usr/bin/perl -w
sub g { $a = "g" }
g();
print $a, "\n";
sub f { print $a, "\n" }
f()
This code prints g g. That means that the assignment $a = "g" implicitly declared a fresh global variable $a that is
visible both at the top level and in another function f that is
neither nested in nor called by function g.
0 0 10 0
10 0 10 0
10 -10 10 0
6.66666666666667 -3.33333333333333 10 0
while (<>) loop header reads lines from standard input to
$_. The function chomp trims whitespace away from
$_. The function split divides $_ up into
comma-separated values to initialize an array reference to store in
@rows.
$row holds a reference to an array, and @$row
dereferences it to get the array. Since it gets used like a scalar, Perl
interprets it as the length of the referred-to array.
#!/usr/bin/perl -w
while (<>) {
chomp;
push @rows, [ split /,\s/ ];
}
#-------- added code for hw03-4 start --------
for $row (@rows) {
for ($i = 0; $i < @$row; $i++) {
$sums[$i] += $row->[$i];
$count[$i]++;
}
}
for ($i = 0; $i < @sums; $i++) {
$avg[$i] = $sums[$i] / $count[$i];
}
push @rows, [ @avg ];
#-------- added code for hw03-4 end --------
for $row (@rows) {
for ($i = 0; $i < @$row; $i++) {
$w = length $row->[$i];
$widths[$i] = $w if !$widths[$i] || $w > $widths[$i];
}
}
for $row (@rows) {
for ($i = 0; $i < @$row; $i++) {
print " " x (1 + $widths[$i] - length $row->[$i]);
print $row->[$i];
}
print "\n";
}
#!/usr/bin/perl -w
while (<>) {
chomp;
push @rows, [ split /,\s/ ];
}
#-------- added code for hw03-5 start --------
for ($r = 0; $r < @rows; $r++) {
$delta = 0;
for ($i = 0; $i < @{$rows[$r]}; $i++) {
$delta += ($rows[$r]->[$i] - $rows[0]->[$i]) ** 2;
}
push @{$rows[$r]}, $delta ** .5;
}
#-------- added code for hw03-5 end --------
for $row (@rows) {
for ($i = 0; $i < @$row; $i++) {
$w = length $row->[$i];
$widths[$i] = $w if !$widths[$i] || $w > $widths[$i];
}
}
for $row (@rows) {
for ($i = 0; $i < @$row; $i++) {
print " " x (1 + $widths[$i] - length $row->[$i]);
print $row->[$i];
}
print "\n";
}
Dynamic typing means that most type checks occur at runtime rather than at compile time. This is not the same as weak typing, because the dynamic checks need not be weak. For instance, Scheme has strong dynamic typing: checks are deferred until runtime, but conversions have to be explicit in most cases.
print "12 ", (isprime 12) ? "is" : "is not", " a prime\n";
print "prime factors of 12: ";
for $f (isprime 12) { print "$f " }
print "\n";
print "13 ", (isprime 13) ? "is" : "is not", " a prime\n";
print "prime factors of 13: ";
for $f (isprime 13) { print "$f " }
push @listout, &$block() for (@listin); makes
heavy use of the default variable $_. The statement modifier
for(@listin) iterates over the elements of @listin,
putting each one in $_. Therefore, when the block gets called by
&$block(), the variable $_ holds an array element. The
code in the block can use this for computation.
@in = (1, 2, 3);
my @out = map_block { $_ + 5 } @in;
for (@out) { print $_, ' ' }
use strict; use warnings;
package TwoWayMap;
sub new {
my ($cls, %init) = @_;
my $self = bless( { MAP => {}, REV => {} }, $cls );
for my $key (keys %init) {
$self->put($key, $init{$key});
}
return $self;
}
sub put {
my ($self, $key, $val) = @_;
$self->{MAP}{$key} = $val;
$self->{REV}{$val} = $key;
}
sub get {
my ($self, $key) = @_;
return $self->{MAP}{$key};
}
sub rev {
my ($self, $val) = @_;
return $self->{REV}{$val};
}
1
#!/usr/bin/perl
use strict; use warnings;
# hash, mapping from string to array reference
# key = cluster name, such as '(A:4:C)' or 'B'
# first array element = weight (number of clustered elements)
# remaining array elements = sum (of columns of all elements)
our %clusters = ();
sub sanity_print {
print "{\n";
for my $key (keys %clusters) {
my $weight = $clusters{$key}->[0];
printf "%20s => %d x [", $key, $weight;
for (my $col = 1; $col < @{$clusters{$key}}; $col++) {
print ", " unless $col == 1;
print $clusters{$key}->[$col] / $weight;
}
print "]\n";
}
print "}\n";
}
while(<>) {
chomp;
my @row = split /\s*,\s*/;
my $key = $row[0];
$row[0] = 1; # weight 1 = cluster contains one row
$clusters{$key} = [ @row ];
}
sub euclid_distance {
my ($cluster1, $cluster2) = @_;
my ($weight1, $weight2) = ($$cluster1[0], $$cluster2[0]);
my $result = 0;
for (my $i = 1; $i < @$cluster1; $i++) {
my ($c1, $c2) = ($$cluster1[$i], $$cluster2[$i]);
$result += ($c1 / $weight1 - $c2 / $weight2) ** 2.0;
}
$result **= 0.5;
return $result;
}
sub find_closest_pair {
my %cls = @_;
my @keys = keys %cls;
my ($res1, $res2) = ($keys[0], $keys[1]);
my $min_dist = euclid_distance($cls{$res1}, $cls{$res2});
for my $i (@keys) {
for my $j (@keys) {
if ($i ne $j) {
my $dist = euclid_distance($cls{$i}, $cls{$j});
if ($dist < $min_dist) {
$res1 = $i;
$res2 = $j;
$min_dist = $dist;
}
}
}
}
return ($min_dist, $res1, $res2);
}
sub combine_clusters {
my ($cluster1, $cluster2) = @_;
my @result = ();
for (my $i = 0; $i < @$cluster1; $i++) {
push @result, $$cluster1[$i] + $$cluster2[$i];
}
return [ @result ];
}
while (1 < scalar(keys %clusters)) {
#sanity_print(); # uncomment this line to test/debug
my ($dist, $k1, $k2) = find_closest_pair(%clusters);
my $new_key = "($k1:$dist:$k2)";
my $new_val = combine_clusters($clusters{$k1}, $clusters{$k2});
delete $clusters{$k1};
delete $clusters{$k2};
$clusters{$new_key} = $new_val;
}
print keys %clusters, "\n";
|2.00, 3.00| = 3.61
|2.77, 4.16| = 5.00
0 => (2, 3)<br/>
1 => (0, 4)<br/>
2 => (-3, 4)<br/>
"cmp_vector" as a parameter to library
function usort(). That way, the library function makes a
call-back to function cmp_vector() whenever it needs to compare
two vectors for sorting.
"cmp_vector", or write a new
function, and pass a different string for the call-back. Here is an
example for the second solution:
function cmp_vector_by_x($a, $b) {
$aa = $a->x; $bb = $b->x;
return $aa < $bb ? -1 : $aa == $bb ? 0 : 1;
}
usort($a, "cmp_vector_by_x");
No user name or password required.
User name grader, password hype3.
User name grader, password hype3.
<html>
<head>
<?php
function convert($qty, $unit, $ing) {
$cup2g = array('flour' => '110', 'sugar' => 225, 'butter' => 225);
$volume = array('cup' => 1, 'tbsp' => 16, 'tsp' => 48, 'ml' => 236);
$weight = array('lb' => 1, 'oz' => 16, 'g' => 453);
if (array_key_exists($ing, $cup2g) && array_key_exists($unit, $volume)) {
$qty = 1.0 * $qty * $cup2g[$ing] / $volume[$unit];
$unit = 'g';
} elseif (array_key_exists($unit, $volume)) {
$qty = 1.0 * $qty * $volume[ml] / $volume[$unit];
$unit = 'ml';
} elseif (array_key_exists($unit, $weight)) {
$qty = 1.0 * $qty * $weight[g] / $weight[$unit];
$unit = 'g';
}
return ((int)($qty + .5)) . " $unit $ing";
}
?>
</head>
<body>
<?php if(!empty($_GET['qty'])) { ?>
Converted result:
<?php echo convert($_GET['qty'], $_GET['unit'], $_GET['ing']); ?>
<br/>
<?php } ?>
<form action="<?php echo $_SERVER[PHP_SELF]; ?>" method=get>
<table border=1>
<tr><td>Quantity
<td><input type="text" name="qty" value=<?php echo $_GET[qty] ?> />
<tr><td>Unit
<td><input type="text" name="unit" value=<?php echo $_GET[unit] ?> />
<tr><td>Ingredient
<td><input type="text" name="ing" value=<?php echo $_GET[ing] ?> />
</table>
<input type="submit" value="Submit" />
</form>
</body>
</html>
"3.141", "1000"
"3.1a", "12.34.56"
^(0|[1-9][0-9]*)(\.[0-9]*)?$
$_GET or
$_POST.
echo, print()) of
running the PHP snippet.
3 7 8 9 9
$y = (7, 8, 9) provides a scalar
context to the list literal (7, 8, 9), and therefore assigns
9.
@x + 0 provides a scalar context to the array
@x, and therefore returns 3.
for $i ($y) { print $i } provides a list
context to the scalar $y, and therefore uses it as a list of one
element, 9.
6, 10
curry.
The environment is a call object for curry, with f=add
and x=1.
curry.
The environment is a call object for curry, with f bound
to the anonymous function function(x,y){x/y} and x=2.
var square = curry(
function(n,x){ for(var z=1;n>0;n--,z*=x); return z; },
2);
Cf, Dg, Ch
Cf, Dg, Eh
<html><head>
<meta http-equiv="Content-Script-Type" content="text/javascript" />
<script>
function c2f() {
var c = document.converter.celsius.value;
var f = c * 9 / 5 + 32;
document.converter.fahrenheit.value = f;
}
function f2c() {
var f = document.converter.fahrenheit.value;
var c = (f - 32) * 5 / 9;
document.converter.celsius.value = c;
}
</script>
</head><body>
<form name="converter">
<table border=0>
<tr>
<td>Celsius:
<td><input type="text" name="celsius">
<td><input type="button" value="To Fahrenheit" onclick="c2f();">
<tr>
<td>Fahrenheit:
<td><input type="text" name="fahrenheit">
<td><input type="button" value="To Celsius" onclick="f2c();">
</table>
</form>
</body></html>
function PriorityQueue() {
this.data = [];
}
PriorityQueue.prototype.push = function(x) {
this.data.push(x);
}
PriorityQueue.prototype.minIndex = function() {
var result;
for (var i in this.data)
if (undefined == result || this.data[i] < this.data[result])
result = i;
return result;
}
PriorityQueue.prototype.peek = function() {
return this.data[this.minIndex()];
}
PriorityQueue.prototype.pop = function() {
var i = this.minIndex();
var result = this.data[i];
delete this.data[i];
return result;
}
<html><head>
<title>Translation Database</title>
</head><body>
<!-- show form for user input -->
<form action="<?php echo $_SERVER[PHP_SELF]; ?>" method=get>
<table border=0>
<tr><td>English: <td><input type="text" name="eng"><br/>
<tr><td>Translated: <td><input type="text" name="tra"><br/>
</table>
<input type="radio" name="request" value="add">
Add</br>
<input type="radio" name="request" value="e2f">
Get (English to Translated)</br>
<input type="radio" name="request" value="f2e">
Get (Translated to English)</br>
<input type="radio" name="request" value="del">
Delete</br>
<input type="submit" value="submit">
</form>
<!-- open database, and create table if it does not yet exist -->
<?php
$db = sqlite_open("/home/hirzel/data/sqlite2", 0666, $err);
if ($err) { die($err); }
sqlite_query($db, "SELECT * FROM Translate", SQLITE_BOTH, $err);
if ($err) {
echo "Table 'Translate' does not yet exist, creating it ...<br/>";
$q = "CREATE TABLE Translate"
. "(English VARCHAR(50), Translated VARCHAR(50))";
sqlite_query($db, $q, SQLITE_BOTH, $err);
if ($err) { die($err); }
} else {
echo "Reopened table 'Translate'.<br/>";
}
?>
<!-- process input, if any -->
<?php
if ("add" == $_GET[request]) {
$q = "INSERT INTO Translate VALUES("
. "'" . addslashes($_GET[eng]) . "', "
. "'" . addslashes($_GET[tra]) . "')";
sqlite_query($db, $q);
if ($err) { die($err); }
echo "Add English '" . htmlentities($_GET[eng]) . "', " .
"Translated '" . htmlentities($_GET[tra]) . "' succeeded.";
} else if ("e2f" == $_GET['request']) {
$q = "SELECT Translated FROM Translate WHERE English = "
. "'" . addslashes($_GET[eng]) . "'";
$rows = sqlite_query($db, $q);
if ($err) { die($err); }
$row = sqlite_fetch_array($rows, SQLITE_BOTH);
if ($err) { die($err); }
echo "Get English '" . htmlentities($_GET[eng]) . "' returned "
. "Translated '" . htmlentities($row[Translated]) . "'.";
} else if ("f2e" == $_GET['request']) {
# echo "Sorry, lookup from Translated to English not yet implemented.";
$q = "SELECT English FROM Translate WHERE Translated = "
. "'" . addslashes($_GET[tra]) . "'";
$rows = sqlite_query($db, $q);
if ($err) { die($err); }
$row = sqlite_fetch_array($rows, SQLITE_BOTH);
if ($err) { die($err); }
echo "Get Translated '" . htmlentities($_GET[tra]) . "' returned "
. "English '" . htmlentities($row[English]) . "'.";
} else if ("del" == $_GET['request']) {
# echo "Sorry, deletion not yet implemented.";
$q = "DELETE FROM Translate WHERE "
. "English = '" . addslashes($_GET[eng]) . "' AND "
. "Translated = '" . addslashes($_GET[tra]) . "'";
sqlite_query($db, $q);
if ($err) { die($err); }
echo "Delete English '" . htmlentities($_GET[eng]) . "', " .
"Translated '" . htmlentities($_GET[tra]) . "' succeeded.";
}
?>
</body>
<?php session_start(); ?>
<html><head>
<title>Session counter</title>
</head><body>
In this session, you have visited this page
<?php
if (empty($_SESSION[count]))
$_SESSION[count] = 0;
$_SESSION[count]++;
echo $_SESSION[count];
?>
times.
</body>
<html><head>
<meta http-equiv="Content-Script-Type" content="text/javascript" />
<script src="c.js"></script>
</head><body bgColor="#00ff00">
Reversed: <span id="reverse">(please click button)</span>
<form name="in">
String to reverse: <input type="text" name="forward"><br/>
<input type="button" value="Toggle Color" onclick="localChange();">
<input type="button" value="Reverse String" onclick="sendRequest();">
</form>
</body></html>
b.php
<?php sleep(3); echo htmlentities(strrev($_GET[fwd])) ?>
c.js
function localChange() {
var blue = document.bgColor == '#0000ff'
document.bgColor = blue ? '#00ff00' : '#0000ff';
}
function sendRequest() {
document.getElementById('reverse').innerHTML = '(please wait)';
var xhr = false;
function handleResponse() {
if (4 == xhr.readyState && 200 == xhr.status)
document.getElementById('reverse').innerHTML = xhr.responseText;
}
try { xhr = new XMLHttpRequest(); } catch(e1) {
try { xhr = new ActiveXObject("Msxml2.XMLHTTP"); } catch(e2) {
try { xhr = new ActiveXObject("Microsoft.XMLHTTP"); } catch(e3) {
alert('Could not create XMLHttpRequest object.'); } } }
xhr.open('GET', 'b.php?fwd=' + document.in.forward.value, true);
xhr.onreadystatechange = handleResponse;
xhr.send(null);
}
result motivation
1 success same domain+protocol+port
2 success same domain+protocol+port
3 failure different protocol ftp
4 failure different domain www.columbia.edu
5 success same domain+protocol+port (port 80 is default)
6 failure different port 8080
7 failure same domain nyu.edu but different server www2
$name comes from user input,
for example, from $_GET['name']. Then, the attacker can provide
the following input:
foo'; drop table custid; --
This is the same input as on the slides. If embedded in SQL, it will end the current string and statement, then start a new statement that destroys a table.
addslashes. It is easy to reimplement from first principle:
function my_addslashes($str) {
$badchar = array("\\", '"', "'", "\0");
$replace = array();
foreach ($badchar as $c) array_push($replace, "\\" . $c);
$result = str_replace($badchar, $replace, $str);
return $result;
}
Somewhere along the way of information flowing from user input to HTML
output, the data must be sanitized. PHP already provides the function
htmlspecialchars for this purpose. If written from first
principle, it looks a lot like the SQL sanitization function from the
previous question:
function my_htmlspecialchars($str) {
$badchar = array("&", '"', "'", "<", ">");
$replace = array("&", """, "'", "<", ">");
$result = str_replace($badchar, $replace, $str);
return $result;
}
a=1, b=2
a=3, b=2
inner
outer(2), with the binding
b=2. Since the call object refers to the same global object both
during and after the call, the binding for a changes from
a=1 to a=3.
initial input:
2 1 3
0 1 1
4 1 2
expected output:
2 1 3
0 1 1
4 1 2
2 1 2
actual output:
2 1 3
0 1 1
4 1 2
1 1 2
1 Hypothesis compute_avg returns wrong value
(expected value would be 2 1 2)
Experiment perl -wd script.pl
b 17
c
p @result
Observation 1 1 2
Conclusion @result is wrong, hypothesis verified
2 Hypothesis at Line 15, numerator $sums[0] is wrong;
(expected value would be 2+0+4 == 6)
Experiment perl -wd script.pl
b 15
c
p $i, " ", $sums[$i]
Observation 0 2
Conclusion $i == 0 and $sums[$i] == 2 != 6
$sums[0] is wrong, hypothesis verified
3 Hypothesis Line 10 adds the wrong numbers into $sums[0]
(expected 3 iterations with $j==0, values 2 0 4)
Experiment perl -wd script.pl
a 10 print "==> " . $row->[$j] . "\n" if $j==0;
c
Observation ==> 2
==> 0
Debugged program terminated.
Conclusion Line 10 adds the correct values from the first two
rows, but is missing the value from the third row.
4 Hypothesis the outer loop iterates for the wrong number of rows
(expected $nrows would be 3)
Experiment perl -wd script.pl
b 7
c
p $nrows
Observation 2
Conclusion $nrows == 2, but should be == 3
5 Hypothesis the defect is in Line 6, since $#_ gives the index
of the last element, but we want the size, which is
one larger
Experiment change Line 6 to:
my $nrows = @_;
then rerun script
Observation expected output and actual output are identical
Conclusion done, the bug is fixed
No example solutions.
preorder:
1
2
4
5
3
6
7
#!/usr/bin/env python
class Tree:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def preorder(self):
yield self.value
if self.left:
for v in self.left.preorder():
yield v
if self.right:
for v in self.right.preorder():
yield v
def inorder(self):
if self.left:
for v in self.left.inorder():
yield v
yield self.value
if self.right:
for v in self.right.inorder():
yield v
my_tree = Tree(1,
Tree(2,Tree(4),Tree(5)),
Tree(3,Tree(6),Tree(7)))
def print_preorder(tree):
print 'preorder:'
for y in my_tree.preorder():
print y
print_preorder(my_tree)
def print_inorder(tree):
print 'inorder:'
for y in my_tree.inorder():
print y
print_inorder(my_tree)
preorder:
1
2
4
5
3
6
7
#!/usr/bin/env ruby
class Tree
attr_accessor :value, :left, :right
def initialize(value, *leftRight)
@value = value
if 0 < leftRight.length()
@left = leftRight[0]
@right = leftRight[1]
end
end
def preorder()
yield @value
if @left
@left.preorder {|v| yield v }
end
if @right
@right.preorder {|v| yield v }
end
end
end
$my_tree = Tree.new(1,
Tree.new(2, Tree.new(4), Tree.new(5)),
Tree.new(3, Tree.new(6), Tree.new(7)))
def print_preorder(tree)
puts 'preorder:'
tree.preorder {|y| puts y.to_s + "\n" }
end
print_preorder($my_tree)
def print_sum(tree)
puts "sum:"
sum = 0
tree.preorder {|y| sum += y }
puts sum
end
print_sum($my_tree)
Tree.preorder in the Python example above is a coroutine.
Every time the co-routine yields, it returns control to the caller. When
the caller calls it again, the coroutine resumes where it left off.
Method Tree.preorder in the Ruby example above takes a block as
a parameter. Every time the Ruby method Tree.preorder yields, it
calls the block. When the block returns, the method continues just like
after a normal call.
The difference is that the Python coroutine uses yield to return
to its caller, whereas the Ruby method uses yield to call its
block.
#!/usr/bin/env php
<?php
class Tree {
var $value, $left, $right;
function __construct($value, $left=null, $right=null) {
$this->value = $value;
$this->left = $left;
$this->right = $right;
}
function preorder($closure) {
$closure($this->value);
if ($this->left):
$this->left->preorder($closure);
endif;
if ($this->right):
$this->right->preorder($closure);
endif;
}
}
$myTree = new Tree(1,
new Tree(2, new Tree(4), new Tree(5)),
new Tree(3, new Tree(6), new Tree(7)));
function printPreorder($tree) {
echo "preorder:\n";
$tree->preorder(create_function('$v', 'echo "$v\n";'));
}
printPreorder($myTree);
?>
apple1, _weight
1apple, weight=
[A-Za-z_][A-Za-z0-9_]*
$_ENV, $_GET, $_POST,
$_COOKIE, $_SESSION).
3-a(1) context provider: operator .
3-a(2) conversion context: scalar (string)
3-a(3) converted value: "rl"
3-a(4) end result: "perl"
3-b(1) context provider: function sqrt
3-b(2) conversion context: scalar (number)
3-b(3) converted value: 4
3-b(4) end result: 2
["quiz1.html", "quiz1.pdf", "quiz2.html", "quiz2.pdf"]
for $n (@numbers) { for $e (@extensions) { push @quizzes, "quiz$n.$e" } }
editor is expected. For example:
http://www.cs.nyu.edu/~hirzel/editor_poll.php?editor=<script>alert("boo!")</script>.
You selected”, the code should be:
<?php echo htmlentities($_GET['editor']) ?>.
5
Vector.
Vector.prototype.
Vector.
Vector.prototype.
Vector, with the newly created object as
this.