Strict Standards: Declaration of Doku_Renderer_metadata::table_open() should be compatible with Doku_Renderer::table_open($maxcols = NULL, $numrows = NULL, $pos = NULL) in /home2/cp-wiki/htdocs/inc/parser/metadata.php on line 24

Strict Standards: Declaration of Doku_Renderer_metadata::table_close() should be compatible with Doku_Renderer::table_close($pos = NULL) in /home2/cp-wiki/htdocs/inc/parser/metadata.php on line 24

Warning: Cannot modify header information - headers already sent by (output started at /home2/cp-wiki/htdocs/inc/parser/metadata.php:24) in /home2/cp-wiki/htdocs/inc/actions.php on line 581

Warning: Cannot modify header information - headers already sent by (output started at /home2/cp-wiki/htdocs/inc/parser/metadata.php:24) in /home2/cp-wiki/htdocs/inc/actions.php on line 581
Table of Contents

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 and In addition, return file (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:

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.


#Problem Set 3, Problem 1
def change_first_occurrence(L, old, new):
    ##Your Code Here
def change_all_occurrences(L, old, new):
    ##Your Code Here

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:

These five functions are in file 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

The functions to be written

A skeleton of is available 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