Lab 4

Submit the following:

• A list of which problems you have solved, with links to the corresponding Kattis submissions.
• A short statement of who did what.

(Getting Accepted on Kattis is a necessary but not sufficient condition for passing a lab task, see General Lab Instructions for more details)

Hint: in C++ in particular but also Java it is useful to use iterators to represent vectors/sets/etc.  For an example of this for the longest increasing subsequence task, see here. An advantage of this approach is that the function does not require the input to be stored in some specific container type, you can use arrays, vector, list, or whatever other container type has the operations needed in the function.

Note that the API suggestions below are to be interpreted as pseudo code, you should translate them to your favorite language as you see fit.

Required time complexity means that your algorithm should have this time complexity.  In some cases it might be possible to pass the Kattis tests with a slower algorithm, but if you do so, you might still get points deducted when presenting your labs.

Hashing

Task 4.1: Substring hashes (1p)

Implement a data structure which given a string can produce good hashes of substrings of the string.

API suggestion:

A class where the constructor takes a string, and where the instances have a member function query(index L, index R) taking left and right endpoint of a substring to hash.

Required time complexity: O(n) time for the constructor for a string of length n, and O(1) time to answer queries.

Problem ID on Kattis: hashing Links to an external site.

Geometry

For this lab you will need to implement a class for working with 2-dimensional points (vectors).  The class should provide all common operations on points, e.g.

• coordinate-wise addition/subtraction
• multiplication/division by scalar
• scalar product
• cross product
• distances
• angles

It will probably be useful for you to allow different data types for the coordinates (in particular the ability to choose between ints and doubles) using templates/generics.  Note however that for some functionality, e.g. angles, one wants the return values to be doubles regardless of coordinate type.

Polygons

Task 4.2: area of simple polygon (1p)

Write a method to compute the area of a (simple) polygon.

API suggestion:
double polygon_area(point[])

Required time complexity: O(n).

Problem ID on Kattis Links to an external site.: polygonarea Links to an external site..

Task 4.3: point inside polygon (1p)

Write a method to check if a point lies inside a (simple) polygon.

API suggestion:
int inside_poly(point p, point[] poly)
where the function would return -1, 0, or 1 depending on whether the point is outside, on the boundary, or inside, the polygon.

Required time complexity: O(n).

Problem ID on Kattis Links to an external site.: pointinpolygon Links to an external site..

Lines and line segments

Task 4.4: Line segment intersection (1p)

Write a method to find the intersection point of two line segments.  It should identify if there is no intersection, if the intersection is a single point, or if the intersection is a line segment (i.e., if the two input segments are parallel and overlapping).

API suggestion:
point[] intersect(pair<point, point>, pair<point, point>)
where the returned vector would have 0, 1 or 2 elements depending on the dimension of the intersection.

Problem ID on Kattis Links to an external site.: segmentintersection Links to an external site..

Task 4.5: Line segment distance (1p)

Write a method to compute the distance between two line segments (i.e, the shortest distance between any point in the first segment and any point in the second segment)

API suggestion:
double segment_dist(pair<point, point>, pair<point, point>)

Problem ID on Kattis Links to an external site.: segmentdistance Links to an external site..

Point sets

Task 4.6: closest pair of points - average case (1p)

Write a method to find a closest pair of points in a point set.  It should have expected running time O(n log n) under the assumption that the input points are uniformly distributed in a subsquare of R². You don't need to be able to prove that your algorithm has the expected running time.

API suggestion:
int[2] closest_pair(point[])
Where the method returns the indices for a pair of points at minimum distance from each other.

Problem ID on Kattis Links to an external site.: closestpair1 Links to an external site..

Task 4.7: closest pair of points - worst case (1p)

Write a method for the same problem, with worst case time complexity O(n log n).

Problem ID on Kattis Links to an external site.: closestpair2 Links to an external site..

Task 4.8: convex hull (1p)

Write a method to compute the convex hull of a point set.  It should handle degenerate point sets (e.g., all points lying on a line).

API suggestion:

point[] convex_hull(point[])
where the returned array contains the points on the hull in order (either clockwise or counter-clockwise). Sometimes it may be more useful to return an int[] containing the indices for the points in the hull.

Required time complexity: O(n log n).

Problem ID on Kattis Links to an external site.: convexhull Links to an external site..

Task 4.9: maximum number of colinear points (1p)

Write a method that given a point set finds a maximum subset of colinear points (i.e., a subset of points all lying on a single line). It is enough if you find the maximum number of points in such a set.

API suggestion:

int number_of_colinear(point[])

Required time complexity: O(n² log n).

Problem ID on Kattis Links to an external site.: maxcolinear Links to an external site..