Plagiarism
Each year, especially in first-year courses, the University prosecutes a significant number of students for Academic Offences.
You must familiarize yourself with the University's
Code of Behaviour on Academic Matters.
The work you submit must be your own. In particular, you may not show any part of your assignment work
(including any rough work) to another student nor may you look at any student's assignment work
(including any rough work). The safest approach is not to discuss the assignment with anyone except
the course instructors and TAs. You are however encouraged to discuss the rest of the course material
with anyone.
Many students who commit an offence by showing their assignment work to another student report that they
thought (incorrectly) that the work would not be copied or mimiced,
thought (incorrectly) that they were being `nice', or felt pressured into it.
Many students who commit an offence by looking at someone else's work or having someone help them write the assignment
say that they did so out of panic shortly before the assignment was due, because they had never faced an academic
situation where they hadn't completed an assignment. While it is hard to think straight when you are panicing,
a better course of action is to contact us about your situation.
Some students who commit an offence thought it couldn't hurt, because they were going to get zero anyway.
But the University is aware of this, and usually makes the penalty for plagiarizing an assignment more than just zero on the assignment.
Assignment 4
New Due Date: Monday Apr 9, 5pm
Solutions
MeasuredData.java.
Tree.java.
FileWalker.java.
MapPanel.java.
TreeToStringTester.java.
Purpose
Practice with trees, generics and recursion, and make a tool to visualize hierarchical data.
MeasuredData
Write a generic class MeasuredData for storing a piece of data and a size.
Make it generic in the type of data.
Provide exactly one constructor, taking a piece of data and a long for the size (in that order).
Provide getData and getSize methods to return the data and the size, respectively.
Override toString to return a string with the toString of the data (use "null" if the data is null)
followed by a colon, a space and the size. Small hint for simplicity: "" + x produces "null" if x is null, otherwise produces the toString of x.
Each method above has only one reasonable (and fairly obvious) choice of return type and parameter(s).
Tree
Write a generic class Tree for non-empty trees, with its nodes / roots-of-subtrees each containing data.
Make it generic in the type of data
(don't make any assumptions about the type of data: in fact in FileWalker you'll use two different types for the data).
The trees have unlimited branching factor, and the child Trees have an order.
You may use java.util.LinkedList to store the children.
Provide a no-argument constructor (or simply rely on the default constructor) that creates a one-element Tree.
Provide setRootData and getRootData methods for getting and setting the root data.
This is the root data of this (sub)tree, not any larger tree that it might inside of as a subtree.
Provide a method addChildTree that adds a given Tree as the last child of this Tree.
Provide a method childTreeIterator that returns an Iterator< ...something... > returning the child Trees in order.
Override toString to return the toStrings of the data in this entire (sub)tree
(use "null" for any data that is null),
with each piece of data on a new line, indented 2 * depth spaces, in preorder following the order of the children:
root of this (sub)tree
first child of root
first child of first child
...
last child of first child
...
second child of root
...
...
last child of root
...
This is the data in this entire (sub)tree, but not any larger tree that it might be inside of as a subtree.
Use System.getProperty("line.separator") at the end of each line (including the last one) to separate the lines.
Hint: for toString, make a recursive helper method that has the indentation as a parameter.
Hint: it's simplest to not have separate classes for trees and nodes!
There are two reasons we've encountered for wrapping list/tree nodes:
represent empty (null is inconvenient for the user as a representative of empty: why?),
and hide structure the user doesn't care about (e.g. tree structure in a BST is an implementation issue).
But below the user will be interested in the tree structure.
So since we've specified the trees are non-empty (and empty ones aren't needed below),
you have no need for the complication of a wrapper class.
Each method above (except the suggested helper method) has only one reasonable (and fairly obvious) choice of return type and parameter(s)
(especially now that we've pointed out that the Tree class works well as the node class too, and emphasized a few more details).
FileWalker
Write a class FileWalker with methods for representing part of a file system as a tree.
Recall that most file systems are arranged as trees. Non-empty directories (aka folders) are internal nodes, containing `child' files and directories.
Files and empty directories are the leaves.
Java uses java.io.File to represent both directories and non-directories.
In the methods below, use isDirectory() to determine whether a File is a directory, and listFiles() to get the child Files of a directory.
Provide a static method fileTree that takes a java.io.File f and returns a Tree of the Files `under' f.
The root of the returned tree contains f. No particular ordering of a directory's children is required.
Consider it a precondition that the files under f form a tree (i.e. there are no shortcuts/links) and are accessible without security violations nor other IO problems.
But no particular exception is required if the files violate that condition.
Provide a static method measure that takes a Tree of Files in the form returned by fileTree,
and returns a Tree of MeasuredData of Files with the same files and the same structure,
but annotated with sizes. For non-directory Files consider the size to be just the length().
For directory Files consider the size to be the sum of the sizes of its children returned by listFiles().
Hint: we didn't suggest any recursive helper methods because the two methods are best done without any.
Each method above has only one reasonable (and fairly obvious) choice of return type and parameter(s).
MapPanel
Complete class MapPanel to provide a visual representation of Trees of MeasuredData that
have the property that the size of each subtree's root data is the sum of the sizes of its childrens' root data.
The entire panel represents the root of the tree.
The panel is divided up into columns representing the root's children in order:
one column for each child, with width proportional to the size of the corresponding child's data.
The columns are divided up into rows representing the children of the subtree the column represents:
one row for each child of that subtree, with height proportional to the size of the corresponding child's data.
This continues recursively. Each row of a column is a box representing a subtree (a grandchild of the root).
The box (instead of the whole panel) is divided up using the subtree (instead of the whole tree). Etc.
To represent the columns/rows, draw a line between them: red for vertical lines separating columns,
blue for horizontal lines separating rows. See the starter code for an example of drawing a colored line,
and where to add code.
Hint: make a static recursive helper method with parameters describing the box to work on, and call it from paintComponent.
Data that's small relative to the size of the root data might result in boxes 0 or 1 pixel wide/tall,
with lines drawn on top of each other. That's okay (it's impossible to avoid).
But the drawing should not overflow the panel, and large data should be seen to take up the correct proportion of the panel's area
(though again 1 pixel rounding is okay, and impossible to avoid).
Testing
Write a tester for Tree's overridden toString.
Restrictions
Do not add any public methods or variables other than the ones required.
Do not alter MapPanel except to add private methods, change the code inside paintComponent, add imports, and add comments.
Documentation
Write javadoc documentation for all the classes, and their public methods.
Include any preconditions, and throw appropriate exceptions for preconditions that are violated and easily checked.
Assignment 3
Solution.
Due Date: Friday Mar 23, 5pm
In this assignment you will implement a variant of a linked list that allows skipping more than one element
at a time when accessing elements by index.
Each node contains a piece of data and references to the previous and next node.
In this way it's a normal doubly-linked list.
But a subset of them contain references to each other that provide a second way to move through the list.
These nodes can be thought of as breaking the list into "chunks" of (usually) more than one node.
Each of the special nodes is the front of a "chunk", and has a reference to the special node at the front
of the previous and next chunks. The first node (if there is one) of the entire list starts the first chunk.
The first node of each chunk also stores how many elements are in that chunk.
Each list is constructed with a maximum chunk size.
To keep the chunks from becoming a lot smaller (on average) than this size,
no two adjacent chunks may both be less than the maximum chunk size (i.e. one or both must have size equal to the maximum chunk size).
This still gives enough flexibility that adding and removing only need to work on adjacent chunks.
The node class is here: do not alter it in any way.
Complete class ChunkedList using the above approach.
Use the front instance variable to refer to the front of your list:
we have made it public to more easily test that your implementation maintains the chunk size restrictions.
For the specification of the non-constructor methods, see the Java API for ArrayList or LinkedList.
For a bad argument to the constructor, throw an IllegalArgumentException.
Use the chunks appropriately to reduce the number of nodes traversed. And in case the spirit of the exercise isn't clear:
it's to practice the low-level implementation of linked structures, so using other list-like classes to help is not allowed
(i.e. don't use arrays, java.util.ArrayList, java.util.LinkedList, etc, and don't define other list classes).
You may add private instance variables and helper methods.
Write a javadoc comment for your constructor. You do not need to provide Javadoc comments for the other methods.
Also, write a JUnit test class ChunkedListTester to properly test the methods of ChunkedList.
Be sure also to test that they throw the appropriate exceptions.
How to approach the assignment
- Read the
ArrayList or LinkedList API for their add/remove/get/size methods.
- Experiment with some
ArrayLists or LinkedLists to confirm your understanding
of how their add/remove/get/size methods work from the user's perspective, and so how they should work in ChunkedList.
- Both
ArrayList and LinkedList represent a list, and so does ChunkedList.
If you're still unclear on the difference between use and implementation in programming, get clear on that:
why does Java have both ArrayList and LinkedList that both seem to do the same thing?
Why is there a List interface? Why did we make Stack and Queue interfaces?
And notice that a user of ArrayList doesn't work with arrays, nor does a user of LinkedList work with nodes.
Similarly, a user of ChunkedList doesn't work with chunks.
In particular, your test cases should work if you literally replace "ChunkedList" everywhere with "java.util.ArrayList"
(which also has a constructor taking an integer that only affects the internal behaviour).
- Now that you know what, you can turn to how. Write
get, using the chunks efficiently.
- Carefully plan your
add and remove: they can be done as efficiently as get.
For a linked list of chunks where pairs of chunks have (together) 1+max to 2max elements,
the user expects at least that get/add/remove is O( index / max )
(max isn't treated as a constant, since the user can vary it in the constructor to affect the efficiency).
In fact add/remove can be done by adding only constant time to the time for get (not even multiplying the time by a constant).
- Do not try to do a full analysis of the efficiency of combinations of
add/get/remove: that's difficult (impossible?) to do well
without knowing more about what the user is going to do (lots of adds vs gets, lots of adds near the back, etc).
Just stick to the spirt of a "chunked linked list": use existing chunks to skip elements where possible (the chunked aspect),
and make only local changes (the linked list aspect) when changes are necessary. Also notice that you are maintaining previous
and next links, which can improve the efficiency in certain ways.
- The real spirit of the assignment is of course pedagogical: to develop your planning skills and master linking, while still letting
us autotest and mark a couple of hundred assignments with the resources we have.
What to document
-
We considered having you write the javadoc for
get/add/remove/size in your own words,
and given the number of students who don't find the Java API documentation precise enough, maybe we should have.
But for those students who read the API and only imagine the correct interpretation, it might be hard to reword and make more precise.
So as stated, you don't have to javadoc those methods, but it would be a good exercise to try to write it in your own words
and clearly enough that it answers the questions other students (or you) had before experimenting with and ArrayList/LinkedList.
- Javadoc your constructor.
- For this assignment you almost certainly worked out some things before or during coding that don't appear explicitly in your code.
Your methods are probably somewhat long (though be sure to look for ways to shorten them, e.g. by pulling repeated code out of
ifs,
making helper methods, removing redundant code, etc), and the reader needs some guidance to understand them.
So include some internal comments.
- Document your test cases. You will have picked them for various reasons (see below), and the reader wants to know.
Testing
Test the ChunkedList methods.
Think about how you wrote your code, choosing test cases that will end up testing all the code paths (each line gets tested by at least one test case).
It would be a good idea (we will likely do it!), but not required,
to call a helper method after each test that checks that the chunk sizes satisfy the constraints,
and anything else that might not be noticeable publically (e.g. if you don't use the previous links, they might fail without you noticing).
Assignment 2
Due Date: Tuesday, Mar 6th, 5pm
Specification.
All three instructors monitor and answer questions on the bulletin board.
But if necessary, Prof. Jansen is the authority for any interpretations or clarifications on A2.
Assignment 1
Solutions.
NEW Due date: Tuesday, Feb 6th, 5pm
Submission Instructions
Submit your .java files (the "Specification" describes which ones) electroncially:
- UTSC
- Submit with command:
submit -N A1 csca48s <filenames>.
- StG
- Submit through CDF.
- UTM
- Submit through the UTM Submit System.
Specification
Assignment Specification.
Starter Code:
Some sample test code, also illustrating the toString format.
Assignment 0 (+ Week 3 Exercise)
Solutions.
NEW Due date: Thursday, Jan 25th, 5pm
Submission Instructions
- UTSC
- Please submit your A0 in the appropriate CSCA48 drop box on the 6th floor of the S-Wing.
- StG
- Please submit your stapled A0 with the signed cover page to the CSC 148 drop box in BA 2220 (also accessible through 2210; you will need your T-Card to get in) any time before the due time.
- UTM
- TBA
Purpose
This review assignment is mainly about carefully tracing code,
a skill important in understanding other's code and debugging one's own code.
Successful programmers debug by tracing their code, not fiddling with it by trial-and-error.
As the programs you write become more complex, the difference in productivity between tracing
and trial-and-error starts to become very significant (there is an interesting article
Hitting the High Notes by Joel Spolsky
that discusses programmer productivity: see the portion from "But I still haven't proven anything" to "5:1 or 10:1 productivity differences between programmers").
The particular code below is similar to code we will discuss in the course,
and tracing it will prepare you to understand our more high-level discussions
(and make sure you can trace the code to understand the low-level details).
Question 1: Loops
For each of the following snippets of code, give the number of times method m() is called,
with a brief explanation.
Assume that a and b are nonnegative integers.
Snippet A
for (int i = a; i < a*a; ++i) {
m();
}
int i = 0; int j = a;
while (i <= j) {
++i;
m();
--j;
}
Snippet B
For this one, first we define a method m1:
public static void m1(int a) {
for (int i = 0; i <= a*a; ++i) {
m();
}
}
Now the snippet:
m1(a*a);
Snippet C
for (int i = a; i != a + b; i += 2) {
for (int j = a/2; j > 0; --j) {
for (int k = 1; k < a; ++k) {
m();
}
}
}
Snippet D
for (int i = 0; i < a; ++i) {
for (int j = 148; j < i; ++j) {
m();
}
}
Question 2: Arrays and Indices
Part A
Complete the body of the following method, as indicated by the comment:
class Q2 {
/** Sort the 'partially sorted' array 'p' into nondecreasing order.
Requires: 0 <= i <= p.length and 'p' consists of two sorted pieces
p[0..i-1] and p[i..p.length-1] in nondecreasing order.
@param p partially sorted array.
@param i starting index of second sorted piece of p. */
public static void sortTogether(int[] p, int i) {
int i0 = 0;
int i1 = i;
int[] temp = new int[p.length];
int t = 0;
while (i0 < i && i1 < p.length) {
if (p[i0] < p[i1]) {
temp[t] = p[i0];
++i0;
} else {
temp[t] = p[i1];
++i1;
}
++t;
}
// FILL IN THIS PART.
// Use arraycopy (perhaps more than once) to complete
// the method. Do not use any more loops.
}
}
Part B
Give a clear and simple description of the number of times the body of the while loop
in sortTogether executes, based on the elements in p.
Someone should be able to quickly and easily determine the number by looking at the elements and
using your description, without thinking about the code at all. Briefly justify your answer.
Question 3: Visualizing Objects
Draw diagrams clearly showing the variables, objects and their relationships when the following program is run.
Include one diagram for each change in state. Do not show the variable args.
Each variable must be represented by a small box with its type and name.
Inside each variable must be its value: in the case of a reference/address you must make one up
or else use arrows to refer to objects.
Each object must be represented by a box, with its address in the upper left corner if you are using addresses,
and its instance variables inside.
Here's an example with addresses, and one with arrows,
which should be very similar (if not identical) to what you saw in A08/108.
Regardless of the details of the particular term you took A08/108, you discussed all the information in the diagram:
the difference between variables, primitive values, references and objects, that objects come from a particular class
(not important in this question) and that objects contain their instance variables (we didn't show the instance
variables of the String object, since we don't know its implementation: instead we wrote down something
meaningful about its data). At St. George, Prof. Campbell drew many diagrams like this in 108, the 108 textbook has ones with even more information,
and Prof. Baumgartner reviewed them and has used them a number of times already this term.
class Q3 {
private Q3 q;
private int i;
private Q3(int i) { this.i = i; }
public static void main(String[] args) {
Q3 q = new Q3(0);
q.q = new Q3(1);
q.q.q = new Q3(2);
q.q.q.q = new Q3(3);
Q3 c = q;
while (c.i != 1) {
c = c.q;
}
Q3 d = new Q3(4);
d.q = c.q;
c.q = d;
q = c;
}
}
|
