Hide menu

AAPS Advanced Algorithmic Problem Solving

Lab 4


Lab Assignment 4

The recommended deadline for lab 4 is 2014-05-12 kl 12:00

Read the general instructions before you start.

The suggested API below is pseudo code, you have to translate it to your favorite language in an appropriate way.

The "recommended time complexity" is what is required to pass the time requirements in Kattis. In case the task is to implement a specific algorithm you may implement any algorithm which has the same or better time complexity.

Advice: In both C++ and Java it is practical to use iterators to represent vectors, sets etc.

Task 4.1: Point Class

No Kattis problem.

Implement a class for 2 dimensional points which can also be interpreted as mathematical vectors. The class should at least support:

  • Point wise addition/subtraction
  • Multiplication/division with scalar
  • Scalar product
  • Cross product
  • Distances and angles of a vector and between points
The class will be more useful if it is possible to choose the type of the coordinates (at least int or double) using templates/generics. Observe that for some operations, such as angles, the return type is always doubles.

Task 4.2: Polygon Area (1p)

Kattis problem: polygonarea

Write a method computing the area of a (simple) polygon.

Suggested API:
double polygon_area(point[])

Recommended time complexity: O(n), where n is the number of points in the polygon.

Task 4.3: Point in Polygon (1p)

Kattis problem: pointinpolygon

Write a method determining whether a point is inside, on the border or outside a (simple) polygon.

Suggested API:
int inside_poly(point p, point[] poly)
where the function returns -1, 0 or 1 depending on whether the point is outside, on the border or inside the polygon.

Recommended time complexity: O(n), where n is the number of points in the polygon.

Task 4.4: Intersection of Line Segments (1p)

Kattis problem: segmentintersection

Write a method that finds the intersection between two line segments. The methods should be able to identify if no such intersection exists, whether it is a point, or whether it is a line segment (i.e., the two line segments are parallel and overlapping).

Suggested API:
point[] intersect(pair, pair)
where the returned vector has 0, 1 or 2 elements depending on whether no intersection exists, the intersection is a point or it is a line segment.

Task 4.5: Distance between Line Segments (1p)

Kattis problem: segmentdistance

Write a method that computes the distance between two line segments, i.e., the shortest distance between any point on the first line segment and any point on the second line segment.

Suggested API:
double segment_dist(pair, pair)

Task 4.6: Point Sets - Closest Pair of Points - Average Case (1p)

Kattis problem: closestpair1

Write a method for finding a pair of points with minimal distance in a set of points. The expected run time should be O(n log n) under the assumption that the points are uniformly distributed in a sub square of R2. You do not have to prove that your algorithm has the expected run time.

Suggested API:
int[2] closest_pair(point[])
where the method returns the indexes for a pair of points with minimal distance between them.

Recommended time complexity: The expected run time should be O(n log n), where n is the number of points in the polygon, under the assumption that the points are uniformly distributed in a sub square of R2.

Task 4.7: Point Sets - Closest Pair of Points - Worst Case (1p)

Kattis problem: closestpair2

Write a method for finding a pair of points with minimal distance in a set of points. The worst case run time should be O(n log n).

Suggested API:
int[2] closest_pair(point[])
where the method returns the indexes for a pair of points with minimal distance between them.

Recommended time complexity: O(n log n), where n is the number of points.

Task 4.8: Point Sets - Convex Hull (1p)

Kattis problem: convexhull

Write a method computing the convex hull of a set of points. The method should handle degenerated point sets, i.e., where all points are on a line.

Suggested API:
point[] convex_hull(point[])
where the method returns an array with the points on the border of the hull ordered either clockwise or counter clockwise. It can sometimes be more efficient to return an array of integers with the indexes of the points on the border of the hull.

Recommended time complexity: O(n log n), where n is the number of points.

Task 4.9: Point Sets - Maximal Set of Colinear Points (1p)

Kattis problem: maxcolinear

Write a method that computes the maximal set of colinear points in a set of points, i.e., a set of points on the same straight line. It is enough to find the maximal number of points in the set.

Suggested API:
int number_of_colinear(point[])

Recommended time complexity: Significantly better than Ω(n3), where n is the number of points.

Task 4.10: Linear Recurrences (1p)

Kattis problem: linearrecurrence

Write a method that solves linear recurrences.


Page responsible: Fredrik Heintz
Last updated: 2014-01-22