Difference between revisions of "CSC212 Homework 4 2014"

From dftwiki3
Jump to: navigation, search
(→‎Problem #2)
(→‎Your Assignment)
 
(29 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
--[[User:Thiebaut|D. Thiebaut]] ([[User talk:Thiebaut|talk]]) 15:49, 1 October 2014 (EDT)
 
--[[User:Thiebaut|D. Thiebaut]] ([[User talk:Thiebaut|talk]]) 15:49, 1 October 2014 (EDT)
 
----
 
----
 +
__TOC__
 +
<br />
 +
<bluebox>
 +
This assignment is due on 10/14/14 at 11:55 p.m.
 +
</bluebox>
 +
<br />
 
=Problem #1=
 
=Problem #1=
 
<br />
 
<br />
−
Write a program that computes the result of an arithmetic expression written in ''reverse polish notation'' (RPN), also called '''postfix notation'''.  We use '''post'''fix to indicate that the operator appears after (post) the operands.  You may want to read this [http://www-stone.ch.cam.ac.uk/documentation/rrf/rpn.html page] introducing the concept.
+
Write a program that computes the result of an arithmetic expression written in ''reverse polish notation'' (RPN), also called '''postfix notation'''.  We use '''post'''fix to indicate that the operator appears after (post) the operands.  You may want to read this [http://www-stone.ch.cam.ac.uk/documentation/rrf/rpn.html page] introducing the concept, or [http://www.cs.man.ac.uk/~pjj/cs212/fix.html this one], as well.
  
 
We, as humans, are used to ''infix'' notation.  In the infix notation, the operators appear in between the operands.  For example 3 + 5.  A regular, error-free, infix expression can be transformed into its postfix exquivalent easily, as illustrated with a few examples:
 
We, as humans, are used to ''infix'' notation.  In the infix notation, the operators appear in between the operands.  For example 3 + 5.  A regular, error-free, infix expression can be transformed into its postfix exquivalent easily, as illustrated with a few examples:
Line 79: Line 85:
 
==Tip==
 
==Tip==
 
<br />
 
<br />
−
* To convert a string to an integer, you can use this:
+
* To convert a string to an integer, you can use this approach:
 
   
 
   
 
  int num = Integer.parseInt( "1234" );  
 
  int num = Integer.parseInt( "1234" );  
 
   
 
   
−
* Look up the documentation [http://docs.oracle.com/javase/6/docs/api/java/lang/Integer.html#parseInt%28java.lang.String%29 here].
+
: Look up the documentation [http://docs.oracle.com/javase/6/docs/api/java/lang/Integer.html#parseInt%28java.lang.String%29 here].
 
<br />
 
<br />
 +
* When you develop your program, make it print the contents of the stack every time it parses a word (operator or number).  Here is an example of the debugging output generated by the solution program.  The first line is the user input, the last line is the normal output, and all the lines starting with "stack" are debugging output that should be removed from the final program.
 +
 +
5 6 7 + - 8 1 + *
 +
stack: [5]
 +
stack: [5, 6]
 +
stack: [5, 6, 7]
 +
stack: [5, 13]
 +
stack: [-8]
 +
stack: [-8, 8]
 +
stack: [-8, 8, 1]
 +
stack: [-8, 9]
 +
stack: [-72]
 +
-72
  
 
==Testing information==
 
==Testing information==
Line 147: Line 166:
 
=Problem #2=
 
=Problem #2=
 
<br />
 
<br />
−
* Store your program in a file called '''Hw4_2.java'''.
+
* This problem is an extension of Problem #1.  Store your program in a file called '''Hw4_2.java'''.
−
* This time we assume that the expressions may have errors in them.  Three types of errors are possible:
+
* This time we assume that the expressions may have errors in them.  Several types of errors are possible:
−
:* The numbers are not integers, but doubles.
+
:* The numbers may not be integers, but doubles.
 
:* The postfix notation may not be correct.  This can stem from several reasons:
 
:* The postfix notation may not be correct.  This can stem from several reasons:
−
::# Incorrect expressions do not end up evaluating to just one number.  For example, "3 5" is incorrect, since there would be 2 numbers left in the stack at the end of its evaluation.  Similarly, "3 5 6 +" is incorrect.   
+
::# Incorrect expressions do not end up evaluating to just one number.  For example, the expression "3 5" is incorrect, since it is missing an operator.  There would be 2 numbers left in the stack at the end of its evaluation.  Similarly, "3 5 6 +" is incorrect.   
−
::# It is possible also that when we get an operator, the stack contains fewer than 2 numbers at the top.  In this case we can't pop 2 numbers to operate on.  That would be an error as well.
+
::# It may be possible to get an operator when the stack contains fewer than 2 numbers at the top.  In this case we can't pop 2 numbers to operate on.  That would be an error as well.
−
* When your program discovers an error, it should print the word "'''ERROR'''" on the output.  All caps.  One word. No extra spaces.
+
::# The operation to perform may not result in a valid number (division by 0).
 +
* When your program discovers an error, it should print the word "'''ERROR'''" in all-caps, and stop.  The error message should contain one word only.   No extra spaces.
 
<br />
 
<br />
 
* Test your program thoroughly and submit it to Moodle.
 
* Test your program thoroughly and submit it to Moodle.
 
<br />
 
<br />
 +
 
=Problem #3=
 
=Problem #3=
 
<br />
 
<br />
 +
Several faculty at Smith (including myself) are interested in simulating the extend with which a human population gets infected by a virus.  One idea is to carry out a simulation on a small scale, for example using the population of students, faculty and staff on campus, and generate a model of all the connections people make during the day, moving around.  This way, if we assume that one person arrives on campus carrying a deadly virus, we can figure how many people he or she makes contact with on Day 1, then how many more people these contacts make on Day 2, etc.  A data visualization would indicate the extent and speed with which the campus population would get infected.
 +
 +
We could test this by creating a mobile app that could be uploaded to the data phones of volunteers who would go about their regular business everyday, and, at the end of the day, upload a file of their whereabouts that day to a server.  The server would then take all possible pairs of files, and see if their two owners were close to each other during the past day, and for how long. 
 +
 +
The format of such file would be simple: a simple text file containing 3 numbers per line:
 +
 +
time latitude longitude
 +
time latitude longitude
 +
...
 +
 +
where time is a number of second since midnight, and latitude and longitude the geographical location of the phone at that time, as recorded by its GPS.
 +
 +
For example, assume that Volunteer 1 uploads this (very simplified) location file:
 +
 +
<source lang="text">
 +
0  10 20
 +
1  10 20
 +
2  10 30
 +
3  10 30
 +
4  10 50
 +
5  10 70
 +
6  10 90
 +
7  10 90
 +
8  10 90
 +
9  10 90
 +
10  10 90
 +
</source>
 +
 +
We see that at Time 1 she's at Location (10, 20), and then moves in a straight line until Time 6, where she reaches Location (10, 90) where she remains until Time 10.
 +
 +
Assumes that we have another volunteer, Volunteer 2, who uploads this file:
 +
 +
<source lang="text">
 +
0  100 200
 +
1  100 200
 +
2    90 180
 +
3    80 150
 +
4    60 110
 +
5    30  90
 +
6    12  90
 +
7    11  90
 +
8    0  50
 +
9    0  40
 +
10  0  10
 +
</source>
 +
 +
 +
We see that at Times 6 and 7 the two were in close contact.  This is because the distance between Points (10, 90) and  (12,90) is very small, and so is the distance between Points (10, 90) and (11, 90).  So the two volunteers were "close" to each other for 2 time units. 
 +
<br />
 +
==Your Assignment==
 +
<br />
 +
* Write a program called Hw4_3.java.
 +
* Your program will get 4 pieces of information from the command line.
 +
:* A minimum distance under which two people will be said to be close enough that the virus can spread from one to the other.
 +
:* A minimum amount of time they have to be within the minimum distance for the virus to spread from one to the other.
 +
:* The name of a data file containing the locations of Volunteer 1
 +
:* The name of another data file containing the locations of Volunteer 2.
 +
<br />
 +
For reference, this is how the solution program gets this information from the command line:
 +
::<source lang="java">
 +
                // get the command line arguments
 +
                int minDist = Integer.parseInt( args[0] );
 +
                int minTime = Integer.parseInt( args[1] );
 +
                String file1 = args[2];
 +
                String file2 = args[3];
 +
</source>
 +
<br />
 +
 +
==Data Limitations==
 +
<br />
 +
* For  this assignment you can assume that the time stamps will '''always''' start at 0, and that there will never be gaps in the time stamps.  So the list of time stamps will always be consecutive numbers.
 +
<br />
 +
==Example==
 +
<br />
 +
* Here is an example of how you would run your program  if you wanted to see if two volunteers associated with two location files location1.txt and location2.txt, were ever within 2 distance units of each other for at least 3 time units.
 +
 +
          java Hw4_3  2 3  location1.txt  location2.txt
 +
 +
:In this case, the program must read the location data from a file called '''location1.txt''', and  location data from another file called '''location2.txt'''.    The program will store the location data in '''2 different lists''', one list for each file.  Then the program scans both lists and computes the distance between points that have the same time stamp.  The distance is computed as
 +
<br />
 +
:::<source lang="java">
 +
 +
  distance = Math.sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) );
 +
 +
</source>
 +
<br />
 +
where x''i'' is the second number on a line of the location files, and y''i'' the third number.
 +
* Your program will then compute the length of time (number of  lines, consecutive or not) during which the two volunteers are close to each other.  If this number is greater than or equal to the second number given on the command line, the program will output the word "CONTACT" on the screen.  If the number of lines (consecutive or not) is less than the minimum amount of time, the program outputs the word "NOT".
 +
<br />
 +
 +
==Example==
 +
<br />
 +
% cat locations1.txt
 +
0 10 20
 +
1 10 20
 +
2 10 30
 +
3 10 30
 +
4 10 50
 +
5 10 70
 +
6 10 90
 +
7 10 90
 +
8 10 90
 +
9 10 90
 +
10 10 90
 +
 +
% cat locations2.txt
 +
0 100 200
 +
1 100 200
 +
2 90 180
 +
3 80 150
 +
4 60 110 
 +
5 30 90
 +
6 12 90
 +
7 11 90
 +
8 0 50
 +
9 0 40
 +
10 0 10
 +
 +
% javac Hw4_3.java
 +
% java Hw4_3  2 1  locations1.txt locations2.txt
 +
CONTACT
 +
 +
%  java Hw4_3 2 2  locations1.txt locations2.txt
 +
CONTACT
 +
 +
% java Hw4_3 2 3  locations1.txt locations2.txt
 +
NOT
 +
 +
<br />
 +
 +
==Recommendations==
 +
<br />
 +
First, make your program work correctly when the minimum time period is 1 time unit.  This is the easiest to implement.  You just need to have 1 line in both list where the two users are less than the minimum distance away from each other to have contact.
 +
 
 +
Making your program work for longer than 1 time unit is harder and more challenging.  I am not expecting everybody to  accomplish this.  Programs that work well for 1 time unit as the minimum time will get a grade of at least 50/100.
 +
<br />
 +
<br />
 +
<onlydft>
 +
==Python Version for Debugging==
 +
<br />
 +
<source lang="python">
 +
import math
 +
 +
list1 = """0 10 20
 +
1 10 20
 +
2 10 30
 +
3 10 30
 +
4 10 50
 +
5 10 70
 +
6 10 90
 +
7 10 90
 +
8 10 90
 +
9 10 90
 +
10 10 90"""
 +
 +
list2 = """ 0 100 200
 +
1 100 200
 +
2 90 180
 +
3 80 150
 +
4 60 110 
 +
5 30 90
 +
6 12 90
 +
7 11 90
 +
8 0 50
 +
9 0 40
 +
10 0 10"""
 +
 +
def distance( x1, y1, x2, y2 ):
 +
    return math.sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) )
 +
 +
L1 = []
 +
for line in list1.split( "\n" ):
 +
    words = line.strip().split()
 +
    if len( words )==3:
 +
        tuple = [ int( word ) for word in words ]
 +
        L1.append( tuple )
 +
 +
L2 = []
 +
for line in list2.split( "\n" ):
 +
    words = line.strip().split()
 +
    if len( words )==3:
 +
        tuple = [ int( word ) for word in words ]
 +
        L2.append( tuple )
 +
 +
print( L1 )
 +
print( L2 )
 +
 +
for i in range( len( L1 ) ):
 +
    t1, x1, y1 = L1[i]
 +
    t2, x2, y2 = L2[i]
 +
    print( t1, t2, distance( x1, y1, x2, y2 ) )
 +
   
 +
   
 +
 +
</source>
 +
</onlydft>
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
<br />
 +
[[Category:CSC212]][[Category:Java]][[Category:Homework]]

Latest revision as of 08:38, 11 October 2014

--D. Thiebaut (talk) 15:49, 1 October 2014 (EDT)


This assignment is due on 10/14/14 at 11:55 p.m.


Problem #1


Write a program that computes the result of an arithmetic expression written in reverse polish notation (RPN), also called postfix notation. We use postfix to indicate that the operator appears after (post) the operands. You may want to read this page introducing the concept, or this one, as well.

We, as humans, are used to infix notation. In the infix notation, the operators appear in between the operands. For example 3 + 5. A regular, error-free, infix expression can be transformed into its postfix exquivalent easily, as illustrated with a few examples:

regular expression RPN expression

3 + 5

3 5 +

3 * ( 5 - 2 )

3 5 2 - *

(4 -1 ) * 8

4 1 - 8 *

( 5 * 10 ) / ( 3 - 2 )

5 10 * 3 2 - /


RPN expressions can be solved very easily by using a stack. For example, if the expression is: 

 3 5 + 7 *

which corresponds to (3 + 5) * 7, we proceed as follows: we read the symbols (numbers and operators) one at a time from the input, and if we find a number, we push it in the stack. If we find an operator, we pop 2 numbers from the stack, one after the other, apply the operator to the two numbers, then push the result back in the stack.

Example
Assume we want to evaluate the postfix string "3 5 + 6 *". Its infix equivalent to (3 + 5 ) * 6, which is 48.
Here we go: we scan our string, and get each number, or operator, one at a time.
3  --> push it in the stack:   
          stack = [3]

5  --> push it in the stack:   
          stack = [5 3]  (the top of the stack is 5)

+  --> Operator!  we pop the stack, get 5, pop again, get 3, add 5+3 together, 8, push that back in the stack.
         stack = [8]

6 --> push it in the stack:
         stack = [6 8]

* --> Operator! we pop the stack, get 6, pop again, get 8, multiply 6 by 8 ,48, push that back in the stack.
         stack = [48]

Done!  the result is at the top of the stack.
  • You may want to watch this video for an additional example:




Your assignment


  • Write a program that reads postfix expressions from the input (there may be several lines of input), and for each one prints out the result.
  • The numbers will always be integers
  • The operators may be +, -, * or /. 10 2 / results in 5. 10 2 - results in 8.
  • Call your program Hw4_1.java, and submit it to Moodle.
  • You can assume for this problem that the expressions will always be error free.


Tip


  • To convert a string to an integer, you can use this approach:
int num = Integer.parseInt( "1234" );
Look up the documentation here.


  • When you develop your program, make it print the contents of the stack every time it parses a word (operator or number). Here is an example of the debugging output generated by the solution program. The first line is the user input, the last line is the normal output, and all the lines starting with "stack" are debugging output that should be removed from the final program.
5 6 7 + - 8 1 + *
stack: [5]
stack: [5, 6]
stack: [5, 6, 7]
stack: [5, 13]
stack: [-8]
stack: [-8, 8]
stack: [-8, 8, 1]
stack: [-8, 9]
stack: [-72]
-72

Testing information


  • You may want to put several expressions in a text file, say, expressions.txt, and test your program this way:
javac Hw4_1.java
java Hw4_1  < expressions.txt
  • Some expressions and their results:


Postfix expression Result

3 5 +

8

3 5 + 7 +

15

2 8 + 3 11 + *

140

1 2 3 4 + + +

10

100 3 /

33

5

5


  • If you had stored the above expressions in the expressions.txt file, then your program would have output:
8
15
140
10
33
5


Problem #2


  • This problem is an extension of Problem #1. Store your program in a file called Hw4_2.java.
  • This time we assume that the expressions may have errors in them. Several types of errors are possible:
  • The numbers may not be integers, but doubles.
  • The postfix notation may not be correct. This can stem from several reasons:
  1. Incorrect expressions do not end up evaluating to just one number. For example, the expression "3 5" is incorrect, since it is missing an operator. There would be 2 numbers left in the stack at the end of its evaluation. Similarly, "3 5 6 +" is incorrect.
  2. It may be possible to get an operator when the stack contains fewer than 2 numbers at the top. In this case we can't pop 2 numbers to operate on. That would be an error as well.
  3. The operation to perform may not result in a valid number (division by 0).
  • When your program discovers an error, it should print the word "ERROR" in all-caps, and stop. The error message should contain one word only. No extra spaces.


  • Test your program thoroughly and submit it to Moodle.


Problem #3


Several faculty at Smith (including myself) are interested in simulating the extend with which a human population gets infected by a virus. One idea is to carry out a simulation on a small scale, for example using the population of students, faculty and staff on campus, and generate a model of all the connections people make during the day, moving around. This way, if we assume that one person arrives on campus carrying a deadly virus, we can figure how many people he or she makes contact with on Day 1, then how many more people these contacts make on Day 2, etc. A data visualization would indicate the extent and speed with which the campus population would get infected.

We could test this by creating a mobile app that could be uploaded to the data phones of volunteers who would go about their regular business everyday, and, at the end of the day, upload a file of their whereabouts that day to a server. The server would then take all possible pairs of files, and see if their two owners were close to each other during the past day, and for how long.

The format of such file would be simple: a simple text file containing 3 numbers per line: 

time latitude longitude
time latitude longitude
...

where time is a number of second since midnight, and latitude and longitude the geographical location of the phone at that time, as recorded by its GPS.

For example, assume that Volunteer 1 uploads this (very simplified) location file: 

 0   10 20
 1   10 20
 2   10 30
 3   10 30
 4   10 50
 5   10 70
 6   10 90
 7   10 90
 8   10 90
 9   10 90
 10  10 90

We see that at Time 1 she's at Location (10, 20), and then moves in a straight line until Time 6, where she reaches Location (10, 90) where she remains until Time 10.

Assumes that we have another volunteer, Volunteer 2, who uploads this file: 

 0  100 200
 1  100 200
 2    90 180
 3    80 150
 4    60 110 
 5    30  90
 6    12  90
 7    11  90
 8    0  50
 9    0  40
 10   0  10


We see that at Times 6 and 7 the two were in close contact. This is because the distance between Points (10, 90) and (12,90) is very small, and so is the distance between Points (10, 90) and (11, 90). So the two volunteers were "close" to each other for 2 time units.

Your Assignment


  • Write a program called Hw4_3.java.
  • Your program will get 4 pieces of information from the command line.
  • A minimum distance under which two people will be said to be close enough that the virus can spread from one to the other.
  • A minimum amount of time they have to be within the minimum distance for the virus to spread from one to the other.
  • The name of a data file containing the locations of Volunteer 1
  • The name of another data file containing the locations of Volunteer 2.


For reference, this is how the solution program gets this information from the command line: 

                // get the command line arguments
                int minDist = Integer.parseInt( args[0] );
                int minTime = Integer.parseInt( args[1] );
                String file1 = args[2];
                String file2 = args[3];


Data Limitations


  • For this assignment you can assume that the time stamps will always start at 0, and that there will never be gaps in the time stamps. So the list of time stamps will always be consecutive numbers.


Example


  • Here is an example of how you would run your program if you wanted to see if two volunteers associated with two location files location1.txt and location2.txt, were ever within 2 distance units of each other for at least 3 time units.
          java Hw4_3  2 3  location1.txt  location2.txt
In this case, the program must read the location data from a file called location1.txt, and location data from another file called location2.txt. The program will store the location data in 2 different lists, one list for each file. Then the program scans both lists and computes the distance between points that have the same time stamp. The distance is computed as 


  distance = Math.sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) );


where xi is the second number on a line of the location files, and yi the third number.

  • Your program will then compute the length of time (number of lines, consecutive or not) during which the two volunteers are close to each other. If this number is greater than or equal to the second number given on the command line, the program will output the word "CONTACT" on the screen. If the number of lines (consecutive or not) is less than the minimum amount of time, the program outputs the word "NOT".


Example


% cat locations1.txt
0 10 20 
1 10 20 
2 10 30 
3 10 30 
4 10 50 
5 10 70 
6 10 90 
7 10 90 
8 10 90 
9 10 90 
10 10 90 

% cat locations2.txt
0 100 200 
1 100 200 
2 90 180 
3 80 150 
4 60 110  
5 30 90 
6 12 90 
7 11 90 
8 0 50 
9 0 40 
10 0 10

% javac Hw4_3.java
% java Hw4_3  2 1  locations1.txt locations2.txt 
CONTACT

%  java Hw4_3 2 2  locations1.txt locations2.txt 
CONTACT

% java Hw4_3 2 3   locations1.txt locations2.txt 
NOT


Recommendations


First, make your program work correctly when the minimum time period is 1 time unit. This is the easiest to implement. You just need to have 1 line in both list where the two users are less than the minimum distance away from each other to have contact.

Making your program work for longer than 1 time unit is harder and more challenging. I am not expecting everybody to accomplish this. Programs that work well for 1 time unit as the minimum time will get a grade of at least 50/100.


...






Retrieved from "http://dominiquethiebaut.com/dftwiki3/index.php?title=CSC212_Homework_4_2014&oldid=23418"