max_cluster(d,A)
that
takes a number d and an array A of numbers (not
necessarily integers), and returns a sequence (an array) containing
a maximal subset of the numbers in A that differ by at
most d. The output can be given in any order. Your
algorithm must have a complexity that is strictly better
than O(n2).
Submit your solution within a Python program
called max_cluster.py
that reads the value d
and the input sequence A from the standard input. The
first number is d and every other number is A.
For example, with this input 5 7 15 16 3 10 43 8 1 29 13 4.5
28
The program invokes max_cluster(5, [7, 15, 16, 3,
10, 43, 8, 1, 29, 13, 4.5, 28])
, which should return the
sequence [ 7, 3, 4.5, 8 ]
or any one of its
permutations, which the program must then print on the standard
output.
Also, analyze the complexity of max_cluster
.
Examples and testing: for the purpose of testing, this package contains input files (.in) each with a corresponding valid output file (.out). Notice that for a given input there may be many valid outputs.
Submission instructions: submit one file called exactly max_cluster.py (lowercase) through the iCorsi system. Due date is Tuesday March 21, at 10:30 CET. This is a graded assignemnt. The exercise will be discussed in class on Thursday March 23.
Write a Python function
called Submit your solution within a Python program
called Hints: notice that a trivial way to implement this
algorithm is to apply the definition of articulation point for every
vertex v, and therefore to test the connectivity
of G without v. However, there is a more
efficient solution that runs in linear time in the size of
the graph, that is O(n+m). Try to work out such a solution
yourself. If you can not find a solution after thinking about it
for at least one day, go to Problem 22-2 of the textbook (CLRS,
pages 621-622), and follow the suggested strategy, and in
particular conditions Examples and testing: for the purpose of testing,
this package contains input files for
various graphs (in directories g-100, g-1000, g-10000, and g-misc)
each with a corresponding expected set of articulation points.
Submission instructions: submit one file called
exactly articulation_points.py (lowercase) through the
iCorsi system. Due date is Tuesday May 16, at 22:00 CET. This is
a graded assignemnt.
articulation_points(G)
that takes a connected
graph G in its adjacency-list representation, and returns
an array containing the articulation points in articulation_points.py
that reads a graph from
the standard input, and then outputs all its articulation points,
one per line, on the standard output. The input graph G is
formatted as follows: the first line contains a number n
that is the number of vertices in G, then each of the
following lines consists of two numbers u and v,
separated by a space, and represents an undirected
edge (u,v) in G.
(
X)
N.
Write the best_compression(S) algorithm in a program
called stringcompress
that prints the best abbreviation
of each line read from the standard input. For example, with these
two input lines:
babababbaaaaababbbab xxxxooxxxxoThe program should output something like this:
b(ab)3b(a)5babbbab xxxxooxxxxoNotice that the string
xxxxooxxxxo
may be abbreviated
as (x)4oo(x)4o
. However, that abbreviation is not
better than the original string, which is also minimal.
Hints: think dynamic programming!
Examples and testing: Your program should be able to abbreviate this file (result), as well as this other file (slightly more complex, but shouldn't take too long either).
Submission instructions: submit one file called exactly stringcompress.py (lowercase) through the iCorsi system. Due date is Friday June 2 at 22:00 CET. This is a graded assignemnt.