# CS 190C, Spring 2008: Problem Set 3

Posted: Friday, January 25, 2008

Due: Friday, February 1, 2008, 10pm (electronic submission via Blackboard)

The functions for each problems should be in a separate file. Name your files problem1.py and problem2.py. In addition, return file ps3_p2_lib.py (independent of any changes you made)

# Problem 1: List Changing

In functions, changes to a parameter that is passed an integer, floating point, or string argument are not seen outside the function. However, changes to list or array arguments are preserved in the argument when the function returns (see also slide 57 from 1/23 lecture).

Write a function named change_first_occurrence that takes three arguments as input:

• L: A list.
• old: A value to search for in list L
• new: A value to replace the first occurrence of old in list L

Use the code of function change_first_occurrence to generate a second function, change_all_occurrences, that takes the same three arguments and replaces all occurrences of old in list L with the value new.

Keep in mind, these functions do not need to return anything to accomplish the goal.

You need not include a main function (the code you submit will consist of the two functions and the imports needed). Use the interpreter command line to test your functions and print the results.

Example:

```#YOUR NAME
#Problem Set 3, Problem 1

def change_first_occurrence(L, old, new):

def change_all_occurrences(L, old, new):

Testing (using the interpreter) may look something like this:

```>>> myList = [1, 2, 3, 4, 5]
>>> change_first_occurrence(myList, 2, "X")
>>> print myList
[1, 'X', 3, 4, 5]
>>> change_first_occurrence(myList, 3, "X")
>>> print myList
[1, 'X', 'X', 4, 5]
>>> change_all_occurrences(myList, "X", 0)
>>> print myList
[1, 0, 0, 4, 5]```

Here is a sample file that contains some lists you can use to test your functions.

# Problem 2: Spatial Queries

Many applications on spatial data sets need queries answering spatial relationships. This problem considers 2- and 3- dimensional points given by their (x,y) and (x,y,z) coordinates, respectively, and asks you to write a number of functions for spatial queries. You are given code for a number of operations incuding reading the point coordinates from a file and visualizing the points. The specifications of the five provided functions are below:

• read_points(filename): opens and reads a specified file and generates a list consisting of all points in the file. A file will contain either 2-d or 3-d data.
• save_points(points, fname): given a list of points, the function saves them to the file named fname. These points can be read back in with read_points(fname).
• show_points(points, color=(0,1,0)): points is a list of either 2D or 3D points; show_points draws them as spheres in the active VPython window. If no color is given (i.e., no second argument is given), the spheres will be green.
• random_points(n,d): returns a list of n random points in d-dimensional space (e.g., if d=2, the points will be in 2-d space). The space that the points are placed in scales with n and d.
• show_box(p1, p2, color=(0,0,1)): given two points p1 and p2, draws a box in the active VPython window indicating the rectangle (or block) outlined by p1 and p2. If no color is given, the box will be blue. This function visualizes the points to be counted by function in_rect.

These five functions are in file ps3_p2_lib.py. You can use them without making any changes or you can change them. In either case, you need to submit this file - without changing its name - along with file problem2.py.

## The functions to be written

• distance(p, q): has two points as arguments and returns the Euclidean distance between the two points (see External Link for a definition, if needed). An argument is a list of either 2 or 3 elements.
• closest(points, q): has two arguments, a list of points and an arbitrary point q. Point q may or may not be in list points. The function returns a point p such that distance(p,q) is a minimum over all points in the list. The function should consider every point in list points to determine q.
• nearest_neighbors(points): determines, from among all points in list points, a pair of points p and q, p different from q, such that distance(p,q) is a minimum over all other distances between two points in list points. Points p and q are returned. If there is more than one pair having the same minimum distance, any pair achieving the minimum distance can be returned. The function should compute a pair giving the minimum distance by considering all possible pairs in the list.
• in_rect(points, p, q): has a list of points and two points p and q as arguments. The function needs only to work on 2-d data sets. Consider the rectangle induced by p and q (i.e., viewing them as points across each other on the diagonal of the rectangle). The function returns the number of points in list points lying inside the rectangle. The number is generated by considering every point in the list and checking whether it is inside or outside the rectangle (lying on the edge of the rectangle counts as inside).

A skeleton of problem2.py is available ps3_problem2.py You can start using the functions from the command line. Examples of data files will be available later (note that one can generate a file easily using functions random_points and save_points).

A sample main function can be found below.

```def main():
# Create a list of 100 random points
myPoints = random_points(100, 2)

# Save the points to a file
save_points(myPoints, "points.txt")

# Graph the points
show_points(myPoints, (0,1,0))

# Create some 2D points
pointA = [1.0, 0.0]
pointB = [1.0, 1.0]
pointC = [0.0, 0.0]

# Print the distance between the points
print "The distance between A and B is:", distance(pointA, pointB)

# Find the point we created that is closest to point B.
closeToB = closest(myPoints, pointB);
print "The point closes to B is:", closeToB

# Find the nearest neighbors in myPoints
pointX, pointY = nearest_neighbors(myPoints)
print "The nearest neighbors are:", pointX, "and", pointY

# highlight the points in the rectangle of pointB and pointC
show_box(pointB, pointC, (0,0,1))

# Double check the answer using in_rect
numInBox = in_rect(myPoints, pointB, pointC)
print "There should be", numInBox, "points in the box"```

If you would like to be able to test the function by running the module, but still be able to include your code as a library, use the following structure instead of a main function:

```if __name__ == '__main__':
# you can put your test program here
# the code sample above would work, without the first line```

If you are not sure about using this if statement, check out this explanation.

Comment: These functions are fundamental spatial query functions. An implementation using the approaches described above is too slow for large data sets. Efficient implementations make use of data structures that organize the points so that not every point needs to be considered in a query. Such material would be covered in a computer science course on data structures.testpoints.txt        