All assignments are to be submitted as text-only email or posted on the web and submitted by email
containing the URL of the
assignment to:
with absolutely no attachments. No assignments will be accepted late.
No assignments will be accepted on paper. No assignments will be accepted on diskettes.
An
assignment is late if the email is sent after the start of the class at which it is due.
The grade for the assignment will be sent back to the email address from which the
assignment email was sent. In the case of group assignments in which multiple students
are involved, one student should be the sender of the email and the other students should
be listed both in the email "CC:" list and in the body of the message.
Students should check this page frequently for updates.
Assignment #1, assigned Thursday, 1 February 2007, due Thursday, 8 February 2007.
Get your text books and bring them to the next class.
Get your notebook and start taking notes
Form a study group
Prepare a proposal for the topics from Knuth that you will handle as a seminar.
Assume you have a three dimensional set A of N points, each with an X, a Y and a
Z
coordinate, and another set B of M points, each with an X a Y and a Z coordinate.
Working with your study group design a program that will shift and rotate the set B to
get the closest possible match between the points of B and the points of A. Be prepared
to discuss what happens to running time and space requirements of your
program when N amd M get larger and larger.
Assignment #2, assigned Thursday, 8 February 2007, due Thursday, 15 February 2007.
In class on 8 February, you will have discussed the algorithmic design for
structural homology in 1, 2 and 3 dimensions. Working with your study group,
prepare a design for the data structures and methods that are needed to
support such designs. For each method, prepare an analysis of the
time and space requirements for that method using the data structures
you have defined. Be prepared to discuss.
Be sure to start you reading of Knuth. You need to be at least 1/4
of the way through the first volume by next week. Be prepared to discuss
the material you have read.
Assignment #3, assigned Thursday, 15 February 2007, due Thursday, 22 February
2007.
In class on 15 February, you will have discussed the impact of various
algorithmic design decisions on the asymptotic behavior of algorithms
for structural homology. One of the issues discussed will have been the
use of "signatures." Suppose the signature chosen is a list of the
three shortest distances in the probe point set. Working with your
study group prepare a design for the data structures and methods that are needed to
support such an approach. Design an algorithm to use those data
structures and methods to match a probe set of points to a larger set
of points and be prepared to discuss the asymptotic behavior of your
algorithm.
Continue your reading in Knuth. For next time be prepared to discuss
MIX and code in MIX for implemenetation of doubly linked lists.
Your seminar selections will have been settled. Prepare a one-page
flyer announcing your seminar. Print out a copy and post the same
information to your web page on mcs.dowling.edu.
Assignment #4, assigned Thursday, 22 February 2007, due Thursday, 1 March
2007.
You will have looked at C versions of MIX in class. Find a full
impementation on the web. Download and install in on a computer
to which you have access (e.g. mcs) and try some of the book
examples on it.
Continue your reading in Knuth. You need to be 3/4 of the way through
the first volume. Reflect on what you have read and prepare two MIX
implementations of the code to traverse all the nodes of a balanced
binary tree in which each parent has exactly 2 children. One implementation
is to use one-way links from parents to children. One implementation
is to store the tree as an array. Be prepared to discuss the
time and space requirements for traversing each type of tree
representation.
Be prepared to discuss the whether trees might be useful in the
structural homology problem.
Some of the seminar selections were not settled until the day this
assignment was given. If not yet done, prepare a one-page
flyer announcing your seminar. Print out a copy and post the same
information to your web page on mcs.dowling.edu.
Assignment #5, assigned Thursday, 1 March 2007, due Thursday, 8 March
2007.
Continue your reading in Knuth. You need to finish volume 1 and start
on volume 2. You will notice that the end of volume 1 is loaded
with answers to questions. You need to read these even more
carefully than you (hopefully) have read the text. Don't skip
over them.
Working by yourself, prepare a detailed discussion of garbage
collection written as a 5 page paper (5 pages of text in addition
to any drawings you may need). Submit that paper on paper
on 8 March.
Assignment #6, assigned Thursday, 8 March 2007, due Thursday, 15 March
2007.
Continue your reading in Knuth. You should get at least through
the first 1/4 of Volume 2.
Working by yourself, prepare a detailed discussion of
at one specific way in which random numbers might be useful
in the design of a structural homology algorithm.
Assignment #7, assigned Thursday, 15 March 2007, due Thursday, 22 March
2007.
Continue your reading in Knuth. You should get at least through
the first 1/2 of Volume 2.
Working with your classmates and working on the web find
a practical reason why it is important to have a clear understanding
of the computational complexity of factorization of large
numbers.
Assignment #8, assigned Thursday, 22 March 2007, due Thursday, 29
March
2007.
Continue your reading in Knuth. You should get at least through
the first 3/4 of Volume 2.
Working in any language you find convenient, working by
yourself, implement a piece of code that will determine as many
of the following important
facts about the system on which the code is being run as you can
implement by 12 noon on Wednesday. Run the
code, and email both the code and the output to the instructor.
You should be able to determine most of these facts, but it is
most important that you determine at least some of these
facts correctly, rather than doing an incomplete or inaccurate
job on most or all of them. You will have a chance to improve
what you do before the end of the semester, but you will
need a working version of signficant portion of this
code to do the assignment for next week.
Is integer arithmetic ones-complement, twos-complement,
signed magnitude or biased?
What is the largest non-negative integer that can be represented?
What is the negative integer of greatest magnitude that can be
represented on the machine?
What is the negative integer of greatest magnitude that can be
represented and for which its magnitude can also be represented.
What is the real number of greatest manitude that can be
represented?
What is the non-zero real number of smallest magnitude that
can be represented?
Does the representation of real number conform to IEEE 754
standards?
Is this a big-endian or a little-endian machine?
There is no class on Thursday, 5 April 2007.
Assignment #9, assigned Thursday, 29 March 2007, due Thursday, 12
April
2007.
Continue your reading in Knuth. You should get at least through
the first 1/4 of Volume 3.
Using the code you wrote for the last assignment, write
a program that will find all the roots of an arbitrary
real polynomial of degrees of as much as 7000 and test
it on polynomials with randomly generated integer
coeficients ranging from -100 to + 100. You must
compute each root to the full accuracy that the machine
you are using allows without using multi-precision
arithmetic. You must test the timing of at least
ten cases for each of the following degrees: 100, 200,
300, 400, 500, 600, ..., 6900, 7000 and using the resulting
data estimate the dependence of the time on the degree
of the polynomial. You must do all the programming work
on your own, except that you may use any part of Knuth
you wish, and you may help one-another with the general
concepts an good web references. You may use published
algorithms or share algorithms, but you must write
your own code. Email your progress to the instructor
by 12 noon Wednesday, 11 April 2007, and bring a written
report listing the code and giving the results.
Prepare a first draft of the 2 pages of notes
you will bring with you to the final and give
a paper copy to the instructor.
Assignment #10, assigned Thursday, 12 April 2007, due Thursday, 19
April
2007.
Continue your reading in Knuth. You should get at least through
the first 1/2 of Volume 3.
Based on the discussion in class of precision and scaling,
and working jointly with the other members of the class,
prepare one best version of a polynomial root finding
program for real polynomials of very high degrees.
Email your progress to the instructor
by 12 noon Wednesday, 16 April 2007, and bring a written
report listing the code and giving the results.
Prepare a second draft of the 2 pages of notes
you will bring with you to the final and give
a paper copy to the instructor. Be sure to include definitions
of terms, the steps in major algorithms and the timing
and space requirements of those algorithms.
Assignment #11, assigned Thursday, 19 April 2007, due Thursday, 26
April
2007.
Continue your reading in Knuth. You should get at least through
the first 3/4 of Volume 3.
I will be away at a meeting on the 26th. Frances Bernstein
will give you a lecture on the language Fortran.
Fortran looks like a version of C in which someone forgot
to put in the semicolons. It is a very effcient language
for numerical algorithms, especially for numerical algorithms
involving large arrays. Many classical numerical algorithms
have been written in Fortran,
and you should be able to read and understand that language
in order to extract algorithms that you may need. Before
the lecture, you are to go to the Wikipedia article on
Fortran
http://en.wikipedia.org/wiki/Fortran and the
article on Fortran features
http://en.wikipedia.org/wiki/Fortran_language_features.
The lecture will be on an older, simpler version of Fortran
that is still heavily used, but you also need to be
aware of the newer features, even though those newer features
can make modern Fortran very difficult to read.
As a check on your comprehension of what you read and the
attention you pay to the lecture, the quiz the week after
will be longer than usual and will ask several questions
about the language.
You can find Fortran programs that will be used as
examples in the lecture at
http://arcib.dowling.edu/~bernsteh/bnl_pdb_pgm_tape/
Pay particular attention to the programs bender.for
conect.for,
dstnce.for,
dgplot.for,
dihdrl.for,
phipsi.for, and
fisipl.for.
Assignment #12, assigned Thursday, 26 April 2007, due Thursday, 3
May 2007.
Finish your reading in Knuth. You are responsible for everything
in all three volumes.
Come to class with two copies of the final version of your
proposed notes on Knuth for use during the final. We will
go over these notes during class and the only changes
you make make in those notes are ones that are approved
by the instructor before the final. You are allowed 2
sides of 8 1/2 by 11 inch paper, written or printed so that it can be
read without a magnifying glass. Be sure to include all definitions
from Knuth and the steps of all major algorithms along with
notes on their time and space requirements.
Finish or redo any earlier assignments that you did not do
or for which you feel you did not give your best effort.
Final 10 May 2007: For those who are prepared and have
an approved set of
notes, there will be an in-class final examination on
Thursday, 10 May 2007. Those who will not be ready and
will be taking an incomplete must notify the instructor
in advance in person that they will not be taking the final
and will be taking an incomplete. There will be
one chance to clear this incomplete in late June and
another chance in early September. You may only take
the final once. Once you start on a version of the final,
you have to take it all the way to the end.
Each version of the final will be
different and they will get tougher and longer the more
time you take getting ready. The one of 10 May will run
from 11:30 until 2:20 and will allow you to use your notes
for the entire exam. The one in June will
take 4 hours and the one in September will take 6 hours. Both the
June and the September versions will include significant
oral examinations without use of your notes.
