Assignment 5: Algorithm analysis

Page 1 of 4
Read the instructions below carefully. The instructions must be
followed. This assignment is worth 5% of your grade. The assignment is
due on . No late assignments will be accepted.
The goal of this assignment is to learn and practice (via programming, quizzes and
algorithm analysis) the concepts that we have studies in the last couple of weeks.
This assignment has 3 parts. Each part explains what needs to be
submitted. Put all those required documents into a folder called
a5_xxxxxx. Zip that folder and submit the zip file as explained in Lab
1. In particular, the folder should have the following 6 files:
a5_week3_xxxxxx.jpg
a5_week4_xxxxxx.jpg
and
a3_part2_xxxxxx.py
a3_part2_xxxxxx.txt
and
a3_part3_xxxxxx.py
a3_part3_testing_xxxxxx.txt
For every method that you design in part 3 of this assignment you have to include the type
contract (inside a docstring -- the rest of the usual info that goes into the docstring
can be omitted for this assignment)
***************************************
PART 1 (5 points)
***************************************
You can think of Part 1 as a practice for your exam.
If you have difficulties with any of the two tests below, I suggest that you watch all the
short coursera videos that relate to the given week. In general that is a good idea.
For Part 1 of the assignment 5 do the following.
Go to https://www.coursera.org/course/programming2
(Notice the above is the 2nd coursera course.)
Click on Exercises (on left hand side).
Complete Week 3 and Week 4 exercises (by clicking Attempt Homework, like you did in
Assignment 3). Then follow the instructions from Part 1 of Assignment 3 to submit the two
images that demonstrated that you completed the two quizzes.
a5_week3_xxxxxx.jpg
a5_week4_xxxxxx.jpg
Make sure that each of the following is visible in each of your images:
1. that your name is present on the top right corner
2. that the Week number is visible
3. that the score for the last attempt is visible for that week
4. NEW (top of the page saying: "Learn to Program: Crafting Quality Code
2015-11-22, 8:52 PM
file:///Users/vida/Desktop/Dropbox/courses/python-iti1120/assignments/assignment5/assignmetn5.txt Page 2 of 4
by Jennifer Campbell, Paul Gries" so that it clear the two quizzes you completed are from
2nd coursera course and not the 1st one)
Important: Each of your photos cannot be more than 200 KB (KB not MB!! we have
limited space on the Blackboard Learn server). For me the screen
capture produced a photo of about 100KB.
Each of the tests is worth 2.5 points. You will get full 5 points for
Part 1 of the assignment, if both of your tests have 75% or more, otherwise the actual
weighted average will be used.
**********************************************
PART 2 (25 points)
**********************************************
For this part, you will be solving some problems and implementing the solutions. The idea
is to design and implement solutions that are as fast as possible, and to analyze these
solutions as well. You will submit two files:
a3_part2_xxxxxx.py contains the functions you are asked to write for each question.
a3_part2_xxxxxx.txt contains, for each function, a rough analysis of its running time when
the argument, n, or the length of the list, a, is 10,000. For example, if your function
looks like this:
def riddle(a):
s=0
for x in a:
for y in a:
s = s+ x*y
return s

Then you would write: This function has two nested for loops. The inner loop executes
10,000 times for each step of the outer loop, which also executes 10,000 times. Therefore,
this function performs roughly 10,000*10,000=100,000,000 operations. If your function uses
the sort() method to sort a, just say that this uses about about 140,000 operations (since
sort uses roughly n log_2 n operations).
In all of the questions you can assume that a is a list containing numbers.
2a) (5 points) Write a function, largest_two(a), that returns the sum of the two largest
values in the list a.
2b) (5 points) Write a function, smallest_half(a), that computes the sum of the len(a)//2
smallest values in the list a.
2c) (5 points) Write a function, median(a), that returns a value, x, such that at least
half the elements in a are less than or equal to x and at least half the elements in a are
greater than or equal to x.
2d) (5 points) Write a function, at_least_third(a), that returns a value in a that occurs
at least len(a)//3 + 1 times. If no such element exists in a, then this function returns
None.
2e) (5 points) Write a function, triple_sum(a,x), that takes a list ,a, as input and
returns True if there exists i, j and k (where i and j and k are not necessarily distinct)
such that a[i]+a[j]+a[k]=x. Otherwise it returns False. For example, if a=[1, 5, 8, 2, 6,
55, 90] and x=103, then triple_sum(a, x) would return True since
a[1]+a[2]+a[6]=5+8+90=103. If a=[-1, 1, 5, 8, 2, 6] and x=-3, triple_sum(a, x) would
2015-11-22, 8:52 PM
file:///Users/vida/Desktop/Dropbox/courses/python-iti1120/assignments/assignment5/assignmetn5.txt Page 3 of 4
return True since a[0]+a[0]+a[0]=-1+ -1 + -1 = -3. If a=[-10,2] and x=-18, triple_sum(a,
x) would return True since a[0]+a[0]+a[1]=-10+-10+2=18. If a=[1, 1, 5, 8, 2, 6] and
x=1000 would return False, since there are not indices i, j and k such that
a[i]+a[j]+a[k]=1000.
*****************************************
PART 3 (40 points)
*****************************************
For this part, I provided two files, called a5_part3_xxxxxx.py and
a3_part3_testing_given.txt
File a5_part2_xxxxxx.py already contains a class Point that we developed in class. For
this part, you will need to develop and add two more classes to a5_part2_xxxxxx.py: class
Rectangle and class Canvas.
To understand how they should be designed and how they should behave, you must study in
detail the test cases provided in a3_part3_testing_given.txt. These tests are your main
resource in understanding what methods your two classes should have and what their input
parameters are. I will explain few methods below in detail, but only those whose behaviour
may not be clear from the test cases.
As in Assignment 1 and Assignment 2, for part 3 of this assignment you will need to also
submit your own text file called a3_part3_testing_xxxxxx.txt demonstrating that you tested
your two classes and their methods (in particular, demonstrating that you tested them by
running all the calls made in a3_part3_testing_given.txt)
Details about the two classes:
=====
Class Rectangle represents a 2D (axis-parallel) rectangle that a user can draw on a
computer screen. Think of a computer screen as a 2D map where each position has an x and a
y coordinate.
The data that each object of type Rectangle should have (and that should be populated in
the constructor, i.e., __init__ method of the class Rectangle) are:
* two Points: the first point representing the bottom left corner of the rectangle and the
second representing the top right corner of the rectangle; and,
* the color of the rectangle
Note that the two points (bottom left and top right) completely determine (the axis
parallel) rectangle and its position on the map. There is no default rectangle.
(see drawings_part3.pdf file for some helpful illustrations)
The __init__ method of Rectangle (that is invoked by the constructor Rectangle) will take
two objects of class Point as input and a string for the color). You may assume that the
first point (sent to the constructor, i.e. __init__) will always have smaller than or
equal x coordinate than the x coordinate of the second point and smaller than or equal y
coordinate than the y coordinate of the second point.
*****
Class Rectangle should have 13 methods. In particular, in addition to the constructor
(i.e. __init__ method) and three methods that override python's object methods (and make
2015-11-22, 8:52 PM
file:///Users/vida/Desktop/Dropbox/courses/python-iti1120/assignments/assignment5/assignmetn5.txt Page 4 of 4
your class user friendly as suggested by the test cases), your class should contain the
following 9 methods:
get_bottom_left, get_top_right, get_color, reset_color, get_perimeter, get_area, move,
intersects, and contains.
Here is a description of three of those methods whose job may not be obvious from the test
cases.
* Method move: given numbers dx and dy this method moves the calling rectangle by dx in
the x direction and by dy in the y-direction. This method should not change directly the
coordinates of the two corners of the calling rectangle, but must instead call move method
from the Point class.
* Method intersects: returns True if the calling rectangle intersects the given rectangle
and False otherwise. Definition: two rectangles intersect if they have at least one point
in common, otherwise they do not intersect.
* Method contains: given an x and a y coordinate of a point, this method tests if that
point is inside of the calling rectangle. If yes it returns True and otherwise False. (A
point on the boundary of the rectangle is considered to be inside).
********
Class Canvas represents a collection of Rectangles. It has 8 methods. In addition, to the
constructor (i.e. __init__ method) and two methods that override python's object methods
(and make your class user friendly as suggested by the test cases), your class should
contain 5 more methods:
add_one_rectangle, count_same_color, total_perimeter, min_enclosing_rectangle, and
common_point.
Here is a description of those methods whose job may not be obvious from the test cases.
* The method total_perimeter: returns the sum of the perimeters of all the rectangles in
the calling canvas. To compute total perimeter do not compute a perimeter of an individual
rectangle in the body of total_perimeter method. Instead use get_perimeter method from the
Rectangle class.
* Method min_enclosing_rectangle: calculates the minimum enclosing rectangle that contains
all the rectangles in the calling canvas. It returns an object of type Rectangle of any
colour you prefer. To find minimum enclosing rectangle you will need to find the minimum x
coordinate of all rectangles, the maximum x coordinate for all rectangles, the minimum y
coordinate and the maximum y coordinate of all rectangles.
* Method common_point: returns True if there exists a point that intersects all
rectangles in the calling canvas. To test this (for axis parallel rectangles like ours),
it is enough to test if every pair of rectangles intersects (according to a Helly’s
theorem http://en.wikipedia.org/wiki/Helly's_theorem).
***
Finally recall, from the beginning of the description of this assignment that each of your
methods should have a type contract.