CSCI 235 Spring 2013
Data Structures and Software Design		Archived Class
Charles Cusack
Computer Science
Hope College
Main
Schedule
Grading
Gradebook
Policies
Advice
College
    Policies
Notes
Programs
Tutorials
CSCI 385
MATH 160
Others
Admin

All Homework

Homework 1

Answer the following questions based on the course website. For each one, give an answer and specify which link on the left you clicked to get the information. For instance, your answer for one might be: 

      23. Certainly (Gradebook)
Each question is worth 1 point, right or wrong.
  1. How often should you check your e-mail?
  2. How many assignments can you turn in late?
  3. At exactly what time are homework assignments due (be precise)?
  4. If you come to class 10 minutes late with your homework, will I accept it?
  5. What percentage of your grade are the exams? What percent is each exam?
  6. When are my office hours?
  7. If you get help from or work with others on an assignment, what do you need to do?
  8. Does neatness/organization of homework matter at all?
  9. Do you have to show all of your work on homework problems, whether or not the problem says so?
  10. Can you tell exactly what grade you got on any assignment in the course at any time? Can you get an idea of how your grade compares with the grade of others?
  11. If you talk about homework problems with others and are able to write down a solution but you don't fully understand it, should you include it on your homework assignment? Explain.
  12. Will I give extra credit assignments to students who are not performing well in the course?
  13. What is the reading assignment for Tuesday, January 22?
  14. How many homework assignments are there currently scheduled?
  15. What dates are you going to be in class taking an exam?
  16. Can you use you iPod, cell phone, or laptop during class?
  17. What should you do after every homework assignment is handed back?
  18. What is the earliest possible date and time you can leave Hope College at the end of the semester?
  19. If you give or take answers from classmates, the Internet, etc., what will be the result?
  20. How is learning like sports?

Homework 2

Homework 2

  1. (12 points) Answer the following questions based on the UML diagrams from the Inheritance Exercise.
    1. How many fields does Rectangle have?
    2. How many constructors does Oval have?
    3. List all of the methods on DrawingPanel that are overloaded.
    4. Are any of the fields in any of the classes accessible from outside the class? If not, how do you know? If so, list them.
    5. If Circle was a subclass of Oval, would I be able to call drawFilledShape from a method in the Circle class? Why or why not?
    6. What is the return type of the method getFilled() in Rectangle?
  2. (20 points) This exercise is adapted from exercise 8.12 from page 294 of OFWJ.
    Assume the following classes are fully implemented (details have been omitted for simplicity). 
    public class Person 
{
    String getName() {/* details omitted */};
}
public class Student extends Person 
{
     double getGPA() { /* details omitted */ };
}
public class Teacher extends Person 
{
     void giveGrade(Student s,int grade) { /* details omitted */ };
}
public class PhDStudent extends Student
{
     boolean isABD() { /* details omitted */ };
}
    Also assume we have the following code (which is error free): 
    Person p1 = new Student();
Person p2 = new PhDStudent();
Person p3 = new Person();
Person p4 = new Teacher();

PhDStudent phd1 = new PhDStudent();
Teacher t1 = new Teacher();
Student s1 = new Student();
    For each of the following, tell whether the statement is legal, will cause a compiler error, or will cause a runtime error, and briefly state why (if it is not legal). Each statement should be thought of as independent from the others.

    1. t1 = new Person();
    2. Object obj = p1;
    3. s1 = (Student) new Object();
    4. s1 = p2;
    5. double gpa = p2.getGPA();
    6. double gpa = (Student) p2.getGPA();
    7. boolean abd = ((PhDStudent) p2).isABD();
    8. t1.giveGrade(phd1,1);
    9. p3.giveGrade(s1,1);
    10. ((Teacher) p4).giveGrade( (Student) (new PhDStudent()), 1);

    (Hint: If you are having problems with any of these, see exercise 8.13).

Homework 3

The assignment in brief

  • Copy/Checkout the BlankPicture project from the SVN repository (We'll do this in class).
  • Draw a picture by modifying the PicturePanel class.
  • Commit your changes to the SVN repository from time to time. Refer to the SVN and Eclipse Examples as needed.
  • Modify index.html by changing the title and (if necessary) the width and height.
  • Fill in the MyGrade.txt file. Specify the score you think you earned in each category and briefly justify.
  • Hand in all of your java and class files (including the ones with symbols and numbers in the name), index.html, and MyGrade.txt using Webhandin under assignment 235-HW3. You can submit the files separately or put them in a zip file (with no directories--just the files) and submit that.
  • Go to the Student Solutions page and verify that your code is there and that your applet runs.
Purpose
The purpose of the first assignment is to
  • Help you refresh your memory on Java programming
  • Familiarize yourself with the Eclipse IDE (integrated development environment),
  • Learn how to use the Java API (application programming interface).
There is not a serious design component to this assignment, and at the surface it does not appear to be closely related to the main concepts of the course. However, it is meant to be a fun assignment to get you back into the swing of Java programming, and it turns out it does have a little to do with a few of the topics we will talk about.
Assignment
For this assignment you need to finish the implementation of the class PicturePanel.java that draws a picture. I will let you decide exactly what you want to draw, but be creative. You can draw a picture of yourself, your dog, a car, a park, etc. Your drawing should be a reflection of yourself. I can help you brainstorm ideas if necessary.

At a minimum, you should:

  • Have at least several dozen objects (circles, lines, text, etc.).
  • Utilize several colors.
  • Have some text, including your name in the lower right corner. Use different fonts and styles.
  • Use several loops, and at least one nested loop (That is, a loop within a loop) to draw something.
  • Use at least a few if-then-else statements.
  • Use an array, ArrayList, or another simple data structure if possible.
  • Use at least two methods.
  • React to at least 2 different mouse events. (Note: There are two sorts of mouse events: MouseEvents and MouseMotionEvents. See below for more about these.).
  • If possible, create several new classes.
The more different sorts of objects you use, the better. Your grade will be based not only on how creative you are, but how much effort you put into learning some things about the various parts of the Java API mentioned below. An assignment which meets the expectation will receive 16/20. Scoring higher than this will require you to go beyond the minimum requirements.

If you have some prior experience with Java, or learn quickly, try to make your applet fancy with animation, or adding some functionality. For instance, you can ask the viewer to input some information, and modify the drawing based on the input.

You should not use BlueJ for this project. Use Eclipse instead.

Resources
  • Several examples I and previous students wrote
    • BlankPicture The starting code. You will actually get it from elsewhere (SVN), but can also see it by following the link. This includes two classes (and perhaps a few other files which you can sefely ignore.
      • PictureApplet is the main class which allows you to run the program as an applet or application. You should not need to modify this class.
      • PicturePanel is the class that does the drawing, and you should certainly modify this one!
    • Past Solutions (including mine)
    • TimerExample A simple example of using a timer to do animation.
  • Java API
    Here are the classes that will be of most interest to you for this assignment.
    • Graphics The main class you will be interested in. You draw using the methods from this class.
    • Color A class you may be interested in if you want to create your own colors.
    • Font A class you may be interested in if you want to do anything fancy with Fonts.
    • MouseMotionListener An interface for mouse motion events
    • MouseListener An interface for mouse events
    • MouseAdapter An adapter that implements the MouseListener interface. Extend this class as a way to handle mouse events. Simply override any of the 5 methods to have it react the way you want.
    • MouseEvent The event passed to the MouseAdapter/MouseListener. Notice it allows you to determine the x and y coordinates of the mouse position, which button was clicked, etc.
  • Java Fonts A simple applet that shows you what certain fonts look like in Java. You might find it useful.
  • Google (link includes a sample search). Search for whatever you need help with. For instance "Java fonts" or "java font choices" or "java create colors", etc. When I am looking for a java class, I search for "java blah 6" (If the class is "blah") and the first hit is usually the API for that class (The "6" ensures I get the documentation for Java 6 instead of 1.4.2 or 5 or 7).
Handing it in
  • Don't forget to hand in:
    • All of your java files
    • All of your class files, including those with $s in the name.
    • index.html, modified as necessary.
    • MyGrade.txt with your self-assessment.
  • Remember to submit with Webhandin under assignment 235-HW3.
  • Go to the Student Solutions page and verify that your code is there and that your applet runs.
Grades
Grades will be based on the following chart. See the Grading page for how to interpret these categories.
CriteriaPointsDetails
Correctness10Each requirement met (8) and it runs (2)
Style6Reasonable variable/method names, methods make sense, and code formatting (2 each)
Documentation6The class, each method, and code is documented (2 each)
Learning Gains8Used classes, made an elaborate drawing, included extra events and methods (especially if it involved keyboard and other event types), used other new things (2 each)
Total30

Homework 4

The next two assignments will be related to the Foxes And Rabbits simulation. In this assignment you will add a third creature. In the next assignment you will improve the GUI. You can see an example of what a finished Homework 5 might look like by downloading and running FoxesAndRabbitsAndSasquatch.jar. (There is only 1 Sasquatch and he eats everything around him. As you can see by running this, he doesn't really affect the simulation much.)

For this assignment you will improve the Foxes And Rabbits simulation by adding another creature.

The third creature must not be another animal (i.e. it cannot be a subclass of Animal), and you should try to think of a creature that will affect the simulation in some significant way. You should perform some of the suggestions from the textbook to create an Actor class, refactor the code accordingly, and add your third creature. Some ideas for creatures include a human, a virus, a dragon, weather, fire, etc. It must act different than both the fox and the rabbit in some significant way (e.g. never dies, doesn't breed, kills everything within 1 or 2 squares (but as Sasquatch demonstrates, having one such creature is boring), kills everything in its row and column, teleports, etc.).

If you did a similar assignment to this in CSCI 225, you should implement a different sort of creature for this assignment and you should not use any of that code. You will learn more this way, and isn't that the point?

You should start with the code available at http://svn.hope.edu/CSCI/S13CSCI235/Foxes And Rabbits 3. Follow the instructions from Section 4 from SVN and Eclipse Examples to get the code. Note: This code is based on an earlier addition of the textbook and has been modified to make the next assignment easier.

Tips:

  • Use what you have learned about inheritance and polymorphism to implement this properly.
  • Do not just sit down and start programming—it will be much easier to implement if you first sit down and think about design.

For more of a challenge (and bonus points), do any of the following:

  • Make the drawing of the simulation a bit fancier. You can draw actual foxes and rabbits, or use little circles for bunnies and triangles for foxes or something similar.
  • Add a fourth creature that is significantly different than the others.

Your grade will be based on:

CriteriaPoints
Correctness10
Design10
Style/Documentation10
Total30
Bonus5

(Tentatively--this may change) Use Webhandin to hand in a zipfile called HW4.zip containing all of your java files and class files using assignment 235-H4.

Homework 5

For this assignment you will improve the Foxes And Rabbits simulation from Homework 4 by adding more buttons. The application should have the following things.

  • One button that will run 1 step of the simulation.
  • One button that will run 100 steps of the simulation.
  • One button that will run the long simulation.
  • One button and associated text field to allow the user to specify the number of steps to run.
  • One button that will reset the simulation.
  • A JMenuBar which contains
    • "File->Exit" which exits the application
    • "Help->About" which gives information about who wrote the application, etc. (use the JOptionPane.showMessageDialog method for this).

To keep the simulation from being buggy, you should disable all of the buttons while the simulation is running. Note: You can't just disable them at the beginning of the listener and re-enable them at the end because the simulation is run in a different thread and the listener will return almost immediately. But you can disable/re-enable them at the beginning and end of the run method in the thread. However, if you want to keep Reset enabled during a run so that it will stop the current simulation and reset it, you will also need a boolean field and related code in several places to deal with this.

The application should quit properly when the "X" in the upper right corner is clicked. This is properly implemented in my version of the code, but if you move the main JFrame somewhere else, you will have to make sure you copy the WindowListener code.

You should continue with your code from Homework 4. Note: In this version Simulator and SimulatorView have been slightly modified to make it a bit easier (the version in the book was not designed to make adding buttons easy). I should also point out that this code is based on an earlier addition of the textbook so the code may have other differences.

For more of a challenge (and bonus points), do any of the following:

  • Allow the user to select parameters of the simulation like board width and height, and creation probabilities. When the user hits reset, the newly generated board will be based on these parameters.
  • Allow the user to select the stats for each creature, including max age, max litter size, etc. This will require modifying the code for Rabbit and Fox, among other things.
  • Allow the user to click on the squares to place rabbits, foxes, etc. One way to do this is to have each click rotate around the options (rabbit->fox->hunter->empty->rabbit...).
  • Deal with potential errors with what the user puts in the text field.

Grading

CriteriaPoints
Correctness10
Design10
Style/Documentation5
GUI/Interface5
Total30
Bonus5

Handing it in

  1. In Eclipse, right-click on your Foxes and Rabbits 3 project and select New-->File.
  2. Enter MyGrade.txt for the File name and click Finish.
  3. Double-click on the MyGrade.txt file that you just created (It should be displayed as part of your project--probably the last thing listed). It should bring the file up in Eclipse in a text editor.
  4. In MyGrade.txt create 2 charts similar to the one from HW 3 but with the criteria for HW 4 and HW 5 (in that order). The easiest way to do this is cut and paste from the homework pages (it will convert the tables to text).
  5. Fill in the charts you just created with your self-evaluation for each project. Make sure you provide totals (out of 30) for each project.
  6. Provide a justification for your self-evaluation. This should be more than one or two sentences but less than half a page.
  7. In Windows Explorer, right click on the Foxes and Rabbits 3 folder and select Send to-->Compressed (zipped) folder.
  8. Name the zipfile whatever you wish.
  9. Use Webhandin with assignment 235-HW5 to submit the zipfile you just created.

Homework 6

  1. For each of the following, give the simplest Θ(tight) bound possible. Assume all logs are base 2 unless specified otherwise.
    (e.g. your answer should be something like Θ(n2), not Θ(263 n2-198 n + 999).
    1. 13 n2 log12(n) + n2.0001
    2. 1,000 n3 + n5 + 1,000,000 n2
    3. n11 + 5n + n101 log200(n) + 3n + 25,432,000 + 23 n + 13 n2
    4. 2n + 3n
    5. 12 n3 log(n) + 23 n2 log5(n) - 988 n + 99
    6. 12 n3 + 23 n2-988 n + 99,000,000
    7. 4n + n5
    8. 32×2log(n) +23 n
    9. (n2 log(n) + n3)(n2+n+32)(2n+3n+n2+n+1+log(n))
    10. n2log3(n)/ log5(n) + 3 n2

  2. Rank the following functions in increasing order of rate of growth. If two of them have the same growth rate, write them on the same line. Otherwise, put them one per line in increasing order of growth.
    1. n log(n)
    2. 453 n3
    3. 13 n3 + 27 n2-563 n + 67
    4. 22n
    5. n2
    6. 3n
    7. 11 n log(n2)
    8. n2.0001
    9. 4n
    10. 23 log10(n)
    11. n2 log(n)

  3. For each of the following functions, give a simple tight bound for the best-case and the worst-case running times. Briefly justify your answers (That means you do not need to give a formal proof, but justify your answer somehow.). Assume A.length=n. 
    1. int sumArray(int []A) {
    int sum=0;
    int i=0;
    while(i < A.length) {
        sum = sum + A[i];
	i++;
	if(sum>12345) {
            i=A.length;
	}
    }
    return sum;
}

    2. int computeGruhop(int []A) {
    int sum=0;
    for(int i=0 ; i < A.length ; i++) {
        for(int j=0 ; j < A.length ; j++) {
            sum = sum + A[i]*A[j];
	    if(sum==1000000) {
                i = A.length;
	    }
	}
    }
    return sum;
}

    3. int anotherSum(int []A) {
    int sum=0;
    for(int i=0 ; i < A.length ; i++) {
        for(int j=0 ; j < 100 ; j++) {
            sum = sum + A[j] + A[i];
	}
    }
    return sum;
}

    4. void HalfIt(int n) {
    while(n > 0) {
        n = n/2;
    }
}

    5. // Assume A and B are both n by n.
Matrix MatrixMultiply(Matrix A, Matrix B) {
    Matrix C;
    for(int i=0 ; i < n; i++) {
        for(int j=0 ; j < n ; j++) {
	    C[i][j]=0;
            for(int k=0 ; k < n ; k++) {
		C[i][j] += A[i][k]*B[k][j];
	    }
	}
    }
    return C;
}

Homework 7

Here is the assignment: Homework 7

Homework 8

I'm not here. You got a copy of me in class.

Homework 9

Download the following files:

The directions are in the first file.