Homework
Mar 8 2013 2:15 PM
|
Homework 8
(Six Degrees of Kevin Bacon)
Due: Friday, Mar 15, 11:30pm.
Cut-off: Sunday, Mar 17, 11:30pm (no submissions accepted after that time)
|
| Spec: |
|
| Documentation: |
|
| Provided Files: |
-
 Graph.jar (library containing provided Graph and AbstractGraph code)
- (See HW8 FAQ page if you need help understanding how to attach this JAR, and Guava, to your project.)
-
 MainKevinBacon.java (provided client program that uses your graph and Bacon finder; do not modify)
-
BaconNumberFinder.java (an unfinished "stub" version of your Part A class to use as a starting point)
-
SearchableGraph.java (an unfinished "stub" version of your Part B class to use as a starting point)
-
TestGraphFlights.java (a testing program that you can use to verify your graph path-searching algorithms)
-
TestGraphABC.java (a testing program that you can use to verify your graph path-searching algorithms)
|
| Input Files: |
-
 small.txt (input file with fewest movies for initial testing/debugging)
-
movies.txt (larger input file with more movies, for testing longer paths)
-
 imdb.zip (very large IMDb input file (28MB) to test with real data; need to unzip first)
It can be hard to run your program on such a large input file. See the FAQ page for more information about how to adjust your Java memory limits so that the entire file can be read without running out of memory. May not run successfully on older computers with less memory.
|
| Expected Output: |
|
| Links: |
-
Wikipedia:
-
(a web version of the Six Degrees program)
-
(neat!)
|
Mar 1 2013 2:15 PM
|
Homework 7
(Sort Detective)
Due: Friday, Mar 8, 11:30pm.
Cut-off: Sunday, Mar 10, 11:30pm (no submissions accepted after that time)
|
| Spec: |
|
| Provided Files: |
-
SortDetective.jar (executable program for Part A that lets you test the sorting algorithms)
- (See HW7 FAQ page if you need help understanding how to run this JAR program.)
-
ArrayMethods.java (utility methods for creating arrays to sort in Part B; do not modify)
-
Quicksort.java (an unfinished "stub" version of your Part B class to use as a starting point)
|
| Example Output: |
-
answers.txt
(here is an example of the kind of contents this file should have; your actual file should contain the sorting algorithms in the order in which you believe they are arranged for your Student ID, from #1-10)
-
explanation.txt
(here is an example of the kind of contents this file should have (partial); your actual file should contain a more complete description for each of the ten sorting algorithms)
|
| Links: |
-
Wikipedia:
,
,
,
,
,
,
,
,
,
-
-
-
-
|
Feb 22 2013 2:15 PM
|
Homework 6
(The Rotating Dead)
Due: Friday, Mar 1, 11:30pm.
Cut-off: Sunday, Mar 3, 11:30pm (no submissions accepted after that time)
|
| Spec: |
|
| Provided Files: |
-
Map.java (map ADT interface for you to implement in Part A; do not modify)
-
AbstractTreeMap.java (the superclass that your tree map class should extend)
-
TreeMap.java (an unfinished "stub" version of your Part A class to use as a starting point)
-
TestTreeMap1.java (a testing program you can use to verify your
HashMap class for Part A)
-
TestTreeMap2.java (a testing program you can use to verify your
HashMap class for Part A)
-
Set.java (map ADT interface for you to implement in Part B; do not modify)
-
TreeSet.java (an unfinished "stub" version of your Part B class to use as a starting point)
-
TestTreeSet1.java (a testing program you can use to verify your
HashSet class for Part B)
-
HvZMain.java (the main client program that performs the console and file input/output; do not modify) (changed from HW4 version; re-download)
-
HvZSimulation.java (a HvZT simulation; do not modify) (changed from HW4 version; re-download)
|
| Expected Output: |
|
| Links: |
|
Feb 8 2013 2:15 PM
|
Homework 5
(The Even-More-Amazing Heap)
Due: Friday, Feb 15, 11:30pm.
Cut-off: Sunday, Feb 17, 11:30pm (no submissions accepted after that time)
|
| Spec: |
|
Provided Files
(Part A): |
-
Please re-download all support files, even the ones that have the same names as in HW3, because they have changed.
-
Main.java (the main client program that performs the console and file input/output; do not modify)
-
Maze.java (represents a 2-D maze to explore; do not modify)
-
GraphicalMaze.java (a graphical animated representation of a 2-D maze; do not modify)
-
GraphicalMazeComparison.java (displays two graphical mazes side-by-side)
-
Solver.java (interface for your
PriorityQueueSolver.java to implement in Part A; do not modify)
-
PriorityQueueSolver.java (an unfinished "stub" version of your Part A code that you can use as a starting point)
Provided Files
(Part B): |
|
Input Files
(Part A): |
-
Please re-download all input files, even the ones that have the same names as in HW3, because they have changed.
-
maze1.txt,
maze2.txt,
maze3.txt,
maze4.txt,
maze5.txt,
maze6.txt,
maze7.txt,
maze8.txt,
maze9.txt
|
| Expected Output: |
|
| Links: |
|
|
Feb 1 2013 2:15 PM
|
Homework 4
(HashMaps vs. Zombies)
Due: Friday, Feb 8, 11:30pm.
Cut-off: Sunday, Feb 10, 11:30pm (no submissions accepted after that time)
|
| Spec: |
|
| Provided Files: |
-
HvZMain.java (the main client program that performs the console and file input/output; do not modify)
-
HvZSimulation.java (a HvZT simulation; do not modify)
-
Map.java (map ADT interface for you to implement in Part B; do not modify)
-
TestMap1.java (a testing program you can use to verify your
HashMap class for Part B)
-
HvZPlayer.java (a mostly-finished "stub" version of your Part A HvZ player class to use as a starting point)
-
HashMap.java (an unfinished "stub" version of your Part B class to use as a starting point)
|
| Expected Output: |
-
hvz1,
hvz2,
hvz3
-
TestMap1
( with extra debug info)
-
(Since your hash codes probably won't match ours exactly, the printed output of the various hash sets/maps will probably come out in a different order.
Check the "ignore order of lines/characters" boxes in the comparison tool to use a more forgiving matching algorithm.)
|
| Links: |
|
Extra Credit
(optional)
myzombies.txt: |
You can optionally turn in a text file named myzombies.txt containing your own data file for a HvZ zombie simulation of your own creation, in the same format as the provided data files. To receive credit, you must submit a valid file that can run in the provided main program successfully. Your file should not be just a copy or slightly-changed copy of one of the provided input files; it should be your own work. If you submit this text file with acceptable contents, you will get +1 free late day for use on this assignment or a future assignment.
|
Jan 25 2013 2:15 PM
|
Homework 3
(The Amazing Deque)
Due: Friday, Feb 1, 11:30pm.
Cut-off: Sunday, Feb 3, 11:30pm (no submissions accepted after that time)
|
| Spec: |
|
| Provided Files: |
-
Main.java (the main client program that performs the console and file input/output; do not modify)
-
Maze.java (represents a 2-D maze to explore; do not modify)
-
GraphicalMaze.java (a graphical animated version of the 2-D maze to explore; do not modify)
-
MazeSolver.java (an unfinished "stub" version of your Part A code that you can use as a starting point)
-
Deque.java (interface for your
ArrayDeque to implement in Part B; do not modify)
-
ArrayDeque.java (an unfinished "stub" version of your Part B code that you can use as a starting point)
-
TestDeque.java (a testing program you can use to verify your
ArrayDeque class)
|
| Expected Output: |
|
| Links: |
|
Extra Credit
(optional)
mymaze.txt: |
You can optionally turn in a text file named mymaze.txt containing your own data file representing a 2-D maze of your own creation, in the same format as the provided data files. To receive credit, you must submit a valid file (rectangular in shape, consisting only of proper characters such as # S E ' ', etc.). Your file should not be just a copy or slightly-changed copy of one of the provided input files; it should be your own work. If you submit this text file with acceptable contents, you will get +1 free late day for use on this assignment or a future assignment.
|
Jan 18 2013 2:15 PM
|
Homework 2
(Star Chart)
Due: Friday, Jan 25, 11:30pm.
Cut-off: Sunday, Jan 27, 11:30pm (no submissions accepted after that time)
|
| Spec: |
|
| Provided Files: |
-
DrawingPanel.java (graphical library to draw figures in a window; do not modify)
-
Main.java (the main client program that performs the console and file input/output; do not modify)
-
Star.java (an unfinished "stub" version of your code that you can use as a starting point)
-
StarChart.java (an unfinished "stub" version of your code that you can use as a starting point)
-
TestStar.java (a testing program you can use to verify your
Star class before implementing StarChart)
|
| Expected Output: |
-
console:
run #1,
run #2,
run #3
-
console: expected console output from
TestStar testing program
-
graphical:
 initial,
big dipper,
w/ star names,
at size 600x300,
graphical:
many constellations,
w/ star names,
graphical:
supernova on Polaris and Cyg Eta,
graphical:
supernova by coordinates (-0.137298 -0.564679, and 0.983035 0.019313)
-
(If you started the assignment early, and your graphical output is mostly perfect but has slight errors around the left edge of the Cygnet constellation, please re-download stars.txt and try again.)
-
-
(The provided DrawingPanel also has a File → Compare to Web File... feature to check your graphical output from your
draw method.)
|
| Links: |
|
| Guava: |
Installing Guava in Eclipse:
- Download Guava JAR archive from
- Attach Guava to your Eclipse project. Right-click the project in the left side Package Explorer, and choose Build Path → Add External Archives ...
- In the box that pops up, browse to the Guava JAR and select it.
- in your code, you can now import the Guava collections:
import com.google.common.collect.*;
Installing Guava in jGRASP:
- Download Guava JAR archive from
- Click Settings → PATH/CLASSPATH → Workspace.
- A dialog box pops up. Click the CLASSPATHS tab.
- Another box pops up. Click New. Click Browse.
- Now a file browser pops up. Go find the location of your Guava .jar file and select it.
- Click OK until you're back at your code.
- in your code, you can now import the Guava collections:
import com.google.common.collect.*;
|
Jan 11 2013 11:59 PM
|
Homework 1
(Stable Marriage)
Due: Friday, Jan 18, 11:30pm.
Cut-off: Sunday, Jan 20, 11:30pm (no submissions accepted after that time)
|
| Spec: |
|
| Provided Code: |
-
Main.java (the main client program that performs the console and file input/output; do not modify)
-
MatchMaker.java (an unfinished "stub" version of your code that you can use as a starting point)
-
SimpleTest.java (a separate testing program that you can use to test details of your code to see if they work)
|
| Expected Output: |
|
| Links: |
|
Extra Credit
(optional)
couples.txt: |
You can optionally turn in a text file named couples.txt containing your own data set of men and women and their preferences, in the same format as the provided data files. To receive credit, you must have an equal number of men and women, at least 3 men and 3 women, and the data must be valid (every line in proper format, every man/woman must have every member of the opposite list in their preferences list, etc.). Your file should not be just a copy or slightly-changed copy of one of the provided input files. If you submit this text file with acceptable contents, you will get +1 free late day for use on this assignment or a future assignment.
|
Textbook
Our textbook for CSE 373 this quarter will be the following:
Weiss, Mark A. Data Structures and Algorithm Analysis in Java (3rd Edition). ISBN 0132576279.
Students can purchase the textbook from the UW Bookstore, which is our recommended place to purchase this textbook.
The book can also be ordered online from Amazon or other online retailers.
The textbook is also available for temporary loan at the
(you can see whether or not it is currently available by clicking the link).
The book is listed as being required for the course.
But problems and assignments will not be assigned out of the book.
Despite this, it may be useful.
The book describes lecture topics in more detail; most lectures will contain suggested book reading to help understand the topic.
Also, exams in this course will be open-book, so it will be advantageous to own the book for use as a reference during exams.
Previous editions of this textbook might be usable but it will be up to you to find the corresponding reading sections, and some might be missing.
This document and its content are copyright © Marty Stepp, 2013. All rights reserved.
Any redistribution, reproduction, transmission, or storage of part or all of the contents in any form
is prohibited without the author's expressed written permission.
Home
Lectures
Homework
Sections
Exams
Forum
Grades
Links
How to set up your computer to work at home
Homework Survey
(give us anonymous feedback about how you felt about a particular assignment)
Practice-It! online Java practice tool
Turn in HW8
Specification
Output Comparison Tool
initial
big dipper
w/ star names
at size 600x300
many constellations
w/ star names
supernova on Polaris and Cyg Eta
supernova by coordinates