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.

Problems on Kattis: https://kth.kattis.com/courses/DD2458/popup25/assignments/fecsmu/problems Links to an external site.

Note! The lab description below might have additional requirements that need to be fulfilled.  In some cases it might be possible to pass the Kattis tests with a slower algorithm, or Kattis might not test all required functionality.  If you do not fulfill the requirements given below you might still get points deducted when presenting your labs.

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 on Kattis: hashing

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).

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).

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 on Kattis: segmentintersection

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 on Kattis: segmentdistance

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 on Kattis: closestpair1

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 on Kattis: closestpair2

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).

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).