Assignment 4
Due: 2:00 PM on Monday, April 11, 2005
Question #1 (70 marks)
Write and document a Java program that implements the
k-means clustering algorithm described in Lecture #9 relative to
a given binary-value data matrix, where Hamming distance is used
]to evaluate the distance between row-sample vectors in the matrix
and cluster-centers. Your program will take as input
the name of the file containing the matrix, the wanted number of
clusters, and the maximum number of cluster-revision iterations.
Your program will output the initial randomly-chosen cluster centers,
and at the end of each revision-round, it will output each
cluster-center, a list of the row-sample vectors associated
with that center, and the average Hamming distance from the
cluster-center to all row-samples in that cluster, as well as the
number of active clusters, i.e, clusters with associated
row-samples, and the average of the average row-sample Hamming distance
in all active clusters. An n X m data matrix with m rows
and n columns will be described by an (m + 1)-line file
in which the first line contains the values m and n and
the remaining m lines describe the row-sample vectors, where
each such line gives the number of that row-sample vector followed by
the n binary column-values in that vector.
You may assume that all all given files are formatted correctly.
As this program uses a random-number generator, final results cannot
be specified. Rather, your marker will test your submitted program
against each of the matrix data files
mat1.dat,
mat2.dat,
mat3.dat, and
mat4.dat
along the lines shown in
the following sample run typescript file.
Should yuou wish more details on how this program actually behaves,
download and run the following executable.
Question #2 (30 marks)
Trace the execution of the independent base-pairs RNA structure
prediction algorithm as described in class, i.e., no pairing of
adjacent bases, on the sequence GAGUCUCA relative to the
following free-energy functions:
- Canonical base-pairs, i.e., G-C and A-U, have score -2 and
all other base-pairs have score 1.
- G-C base-pairs have score -2, A-U base-pairs have score -1, and all
other base-pairs have score 1.
- G-C and G-U base-pairs have score -2, A-U base-pairs have score -1,
and all other base-pairs have score 1.
Fill in the provided dynamic-programming tables in file
a4_q2_tab.ps /
a4_q2_tab.pdf
(including all backpointers
for each cell) and show any one of the paths of backpointers that
indicates an optimal base-pairing as well as the optimal base-pairing
corresponding to that path.
Indicate backpointers associated with a cell in square brackets in
that cell, using -1 to denote the base-pairing recursive case and the
values of k to denote the min-k recursive case,
e.g., "[-1,1,4]".
Submission
Please hand in printed copies of your Java source code
files for Question #1 along with your answer for Question #2.
You must also submit your Java files electronically using the
submit-assignment command.
Note that each
such file must have the following comment block
at the top, where
the X's are replaced with the appropriate information. For instance,
my code for KMC.java would begin with the
following comment block:
/////////////////////////////////////////////////////////////////
// CS 4762 (Winter 2005), Assignment #4, Question #1 //
// Program File Name: KMC.java //
// Student Name: Todd Wareham //
// Login Name: harold //
// MUN #: 8008765 //
/////////////////////////////////////////////////////////////////
You do not have to develop your code on our CS departmental systems.
However, as your code will be compiled and tested on our CS departmental
systems as part of the assignment marking process,
you should ensure that your code compiles and runs correctly on at
least one of these systems.
- Apr 1, 12:40 pm
Posted Assignment #4 executable.
- Mar 17, 8:40 am
Changed due date of Assignment #4 April 11.
- Mar 16, 1:10 pm
Assignment #4 posted.
Created: March 16, 2005
Last Modified: April 1, 2005