Due Tuesday,
October 15.
Turn in a paper copy in class AND submit a copy electronically via the file upload webpage for is255.
(for electronic submission, please read the email sent regarding the correct format for uploading your file)
You may work with
another person on this, but you must be in the same room with them when
you work on it. I don't want people trading off on the work.
(A) Sigma Notation, Arrays, and Loops
These questions are
intended to help you understand the relationships between sigma notation,
loops (in Java and other languages), and arrays.
- For
the two series of numbers shown below, (a) write the series in sigma notation
and (b) write the computation of the series in Java code. Be sure to test your
Java code to make sure it works.
(a)
3 + 6 + 9 + 12 + 15 + 18 + 21 + 24 + 27
(b) 729 + 512 +
343 + 216 + 125 + 64 + 27 + 8 + 1
- Show
two ways of determining the length of an array in Java, using Java code. One should be O(n)
and the other should be O(1). Indicate which method is which.
- Describe how array references versus array values are related to the notion of memory
address versus values in memory. Relate this to the relationship
the two types of operands we saw in computer instructions.
(B) Algorithm Analysis
- Which function grows larger faster as m approaches infinity: 5^m
or m^5?
- Which function grows larger faster as m approaches infinity: sqrt(m) or
log(m)? (sqrt means square root)
- We know that n log(n) grows more slowly than n^2.
Why is this so?
- Say you have a long string, such as
"supercalifragilisticexpialidocious". Say you want to print out all
the substrings of this string, starting from the left, and always
retaining the substring you have printed out so far, e.g. "s", "su",
"sup", "supe", and so on. Assuming this string is of length n, how
many substrings will you print out in terms of big-O notation?
How did you arrive at this answer? (NB: You don't need to code this.)
- Now say you want to print out all substrings of this
string, where a substring consists of letters that are adjacent within
the string. Using the example above, this would include "s", "su",
"sup", "supe" ... but would also include substrings that don't
begin at the beginning, e.g., "per", "expia", and so on. How many
substrings would you need to print out, using big-O notation? How did
you arrive as this answer? (If you have to print the
same short string twice, e.g., "s", count this as two different
instances of printing.) (NB: You don't need to code this.)
(C) Pasta Primavera
Say
you are an aspiring chef who has been employed to do grunt work in a fine
San Francisco Trattoria. Mainly what you do is cut and chop all day.
One of your jobs
is to to turn long tubes of pasta into penne. Currently you take a freshly
made strip of pasta (64 inches long), lay it out on a long
counter, and using a long knife, cut it up into penne pieces that are one
inch long each (with straight edges, not slanted).
You decide you'll
work your way up by impressing the sous chef by devising clever algorithms
for chopping up the pasta more quickly.
- Describe an
algorithm that requires O(n) cuts to chop the pasta into n pieces. Describe
why it is O(n).
- Describe an
algorithm that requires O(sqrt(n)) cuts to chop the pasta into n pieces.
Describe why it is O (sqrt(n)).
- Describe an
algorithm that requires O(log n) cuts to chop the pasta into n pieces.
Describe why it is O (log n).
(D)
Programming Practice: Vectors and Reading Input from Files
This is a small programming exercise intended to give you practice
with Vectors and reading input from files. It builds on the Schedule
class from Lab 4.
Assume you've been given two text files. One contains information
about the various professors in the school, and the other contains
information about the courses being offered in the school. Your
Schedule code needs to link up the professor information to the course
information. We'll do this by first reading in the information about
the professors and storing this information in a Vector. We'll then
read in the information about the courses and store that into another
Vector. Note that a given course can be taught by either one or two professors.
The twist for this code is that we want to store objects of
type Professor in the objects representing Courses, so we'll have to
search our Vector of Professor objects each time we build a course
object to find the right Professor object.
To make this work you should make the following changes to the three
files (Schedule.java,
Course.java,
Professor.java):
- Add a getName() method to class Professor.
- Add a second contructor to class Professor that only requires a name to be passed as a parameter.
- Initialize two Vectors in class Schedule; one holds the
objects of type Professor; the other holds objects of type Courses.
- Add a method to class Schedule that reads in the info from
profs.txt, and for each line of
text, instantiates an object of type Professor, and places
this in a Vector of professors.
Hint: Use a BufferedReader object and a StringTokenizer
object with comma (,) as the separator.
- Add a second method to class Schedule that, for each line
of the file courses.txt,
- Reads in the line of text
- Looks up the appropriate professors in the Vector of
Professor objects. To make this work correctly, you must:
- Modify the constructors for class Course to accept the
name(s) of the professor(s) teaching a course and the Vector
of Professor objects.
- Add a method to class Course that searches the Professor Vector for an
object with the name passed to the constructor. If there is a match,
assign the matching object to the course's instructor variable. If
there isn't a match, create a new Professor object using the name
passed to the constructor.
- Instantiates a Course object that corresponds to the
course, using these Professor objects.
Hint: Note that a course may have one or two professors, so
this means your code has to read in the course info has to take
that variability into account.
- Add code to class Schedule that displays the information for each of the Course objects.
(Question by J. Fritch; modified by M. Hearst.)
MAH -- last modified
10/04/02