Description
Consider an online meeting app or friendship recommender system which recommends meetings to people based
on their geographical convenience, e.g. they walk / bike / travel on common routes within the city. They have a
road network in the form of a graph �(�, �), where � = {1, … , �} is the set of vertices denoting endpoints of
road segments, and � ⊆ � × � is the set edges denoting the road segments. The company also maintains a set of
paths � = {�1, … , �2}, one corresponding to each of the � users. Each path is a sequence of adjacent vertices,
and of arbitrary length. A path denotes the actual road segments which the user travels by: �4 = (�1, … , �67
). Note
that vertices can be repeated in the paths.
For recommendation, the company tries to find the maximal common subpath, between the paths �4 and �8
taken by two users � and �, and recommends users sharing a higher length of path to each other for meeting. Given
a path � = (�1, … , �6), a subpath is another path � = (�1, … , �=), � ≤ �, such that �4 = �1, … , �4A=B1 = �=
for some �. A maximal common subpath � between two paths � and �, satisfies:
• � is a subpath of both � and �.
• There is no other common subpath of � and � with length strictly larger than �.
Task 1:
The first task is to write a program which takes as input two such paths in the following format, read from an
input file:
Where, m and n are the lengths of each path.
The program outputs a maximal common subpath.
Algorithm 1: Marks: 10
This problem is similar to longest common substring problem
(see: https://en.wikipedia.org/wiki/Longest_common_substring_problem)
One way solve it is using a dynamic programming based algorithm, which solves the problem by calculating the
length of longest common subpath between prefixes of the two paths. Hence, �(�,�) is the length of longest
common subpath between the prefixes of paths �1, … , �4 and �1, … , �8.
One can see that if �4 = �8, then �(�,�) = �(� − 1,� − 1), else �(�,�) = 0. For more details, see section 15.4 in
the book by Cormen et al.
Algorithm 2: Marks: 10
The second way of solving this problem is using a rolling string hashing function, similar to the one used in Rabin
and Karp algorithm. The overall scheme is:
1. Pick a length �, and hash all �-length subpaths from both paths (� and �) into a hashtable and find the pairs
of subpaths which collide. This can be done in Θ(� + �) time. Check that these subpaths are actually
same and return a match.
2. Repeat the above step for all lengths �, and return a subpath of highest length.
Hashing algorithm: Rolling hash for a string �1, … , �6, can be computed as: ∑ �4� 6 4
4M1 ��� �, where p is a prime
and d is the alphabet size (in this case the total number of vertices).
Task 2: Marks: 10
In the second task, you are given a set of such paths. You have to find a maximal common subpath, which is
common to all the input paths. The input format is:
…
Where, the number of paths is �, and each path is of length n1, n2, …, nH.
Algorithm:
Use the hashing-based approach described in Algorithm 2 of Task 1. However, in Step 1 return a match only if
sub-paths from � paths have been matched in a hash bucket.
Submission:
Submit 3 c source files for: task 1 algorithm 1, task 1 algorithm 2, and task 2, respectively. Write your name and
roll number in a comment at the top of the file along with compilation instructions. The program should read all
input from a file and the name of the file should be first argument. You can assume that maximum number of
vertices and maximum length of each path is 1000, and maximum number of users is 100.
Marks will be given for more understandable (logical order of functions, naming of variables, etc.), maintainable
(proper comments) and concise (no code duplication) programs.