Assignment 1
Assignment 2
Assignment 3
Assignment 4
Assignment 5
Assignment 6
Extra Credit
Assignment 1: Due 9/17 before midnight
Solution
- Write a
program that outputs the number of characters, words, and lines in a
user-specified file. Use Exceptions wherever applicable. Useful link:
http://java.sun.com/j2se/1.4.2/docs/api/java/lang/String.html
- Write a
program that reads a set of integers from a user-specified file, and
determine if there are any duplicates. If so, then print the number(s) and
their locations. Otherwise print The file
contains no duplicates.
- A palindrome
is a number or a text phrase that reads the same backwards as forwards.
For example, each of the following five-digit integers is a palindrome:
12321, 55555, 45554 and 11611. Write a program that takes in a five-digit
integer and determines whether it is a palindrome by using two different
algorithms (you will put them in overloaded methods):
a)
Treat each number as a string and read the string one
character at a time
b)
Use the division and modulus operators to separate the
number into its individual digits.
Please use the following skeleton for this assignment. It is
important that the names of the class and the methods are identical to the
specification here. Name your file Assign1.java.
import java.io.*;
public class Assign1
{
// print the file stats in this
method
public
static void fileStats(String filename)
{
}
// print duplicates and their
locations in this method.
// If no duplicates, print The file contains no duplicates
public
static void detectDup(String filename)
{
}
// returns true if the input is a
palindrome, false otherwise
public
static boolean isPalindrome(String
number)
{
}
// returns true if the input is a
palindrome, false otherwise
public static boolean isPalindrome(int number)
{
}
// I will provide this part. The main will look something like
// this.
public
static void main(String [] args)
{
fileStats(“myFile.txt”);
detectDup(“myFile2.txt”);
String
num1 = “66166”;
int num2 = 66166;
System.out.println(isPalindrome(num1));
System.out.println(isPalindrome(num2));
}
}
Assignment
2: Due 9/28 before midnight
Solution
For this assignment, turn in hard-copies
only (either bring it to class, or slide it under my door).
- For
each of the following program fragments, do the following:
a. Give
a Big-O analysis of the running time. Provide some reasoning on how you arrive
at the conclusion for general case n (i.e.
summation (could be approximation for complex cases))
b. Implement
the code and run for several values of n (10, 100, 1000, 10000)
c. Compare
your analysis with the actual running times. i.e.
Check if the actual running time is as expected (from the big-O analysis on
part (a)). For example, for O(n2), you
should expect that, when the input size increases by a factor of 10, the
runtime should increase by a factor of 102 = 100 times.
To measure actual
running time of your program, you can use the following segment of code. System.nanoTime()
returns the current value of the system timer in nanoseconds. So you just
indicate when to start/stop the timing. You'll need to time each fragment
separately.
long startTime = System.nanoTime();
// put your for loop here
long stopTime = System.nanoTime();
long runTime = (stopTime-startTime) / 1000; //get run time in microseconds
System.out.println("Run time: " +
runtime);
Some of the
cases take a while to run, so it'd be a good idea for you to leave it running
overnight. If you'd like to redirect the result to an output file, simple do
this on the command line (assuming your class is called TestRunTime):
java TestRunTime > output.txt
This
will save the println’s to output.txt (or use
>> for appending).
// fragment 1
for (int i = 0; i < n; i++)
sum++;
// fragment 2
for (int i = 0; i < n; i+=2)
sum++;
// fragment 3
for (int i = 0; i < n; i++)
for
(int j = 0; j < n; j++)
sum++;
// fragment 4
for (int i = 0; i < n; i++)
sum++;
for (int j = 0; j < n; j++)
sum++;
// fragment 5
for (int i = 0; i < n; i++)
for
(int j = 0; j < n*n; j++)
sum++;
// fragment 6
for (int i = 0; i < n; i++)
for
(int j = 0; j < i; j++)
sum++;
// fragment 7
for (int i = 1; i < n; i=i*2)
sum++;
- Show
that f(n) = 3n + 10 is O(n).
- Show
that f(n) = 3n + 10 is also O(n2).
- Show
that f(n) = 2n3 + 3n + 1 is O(n3).
Assignment
3: Due 10/10 before midnight
Solution
Part I. Implement a
simple GameEntry
class as specified below. Each GameEntry object represents an entry for a video game, and
contains two fields: the score, and the name of the person earning the score.
public class GameEntry
{
private String name; //
name of the person earning this score
private int score; //
the score value
//
Constructor to create a game entry. The score should be greater than or equal
to zero. If it's
//
negative, then set it to zero.
public GameEntry(String n, int s)
{
}
//
Retrieve the name field
public String getName()
{
}
//
Retrieve the score field
public int getScore()
{
}
//
Returns a string representation of this entry (name & score)
public String toString()
{
}
}
Part II. Implement the class AllEntries as specified below. AllEntries
consists of a collection of game entries, represented as a growable array of GameEntry
objects. Users can insert/delete a game entry to/from the array. Use the
following specification. You may add any private methods to the program as you
see fit. Throw exceptions wherever appropriate.
public class AllEntries
{
//
initial capacity of array
public static final int
INIT_CAPACITY = 10;
//
number of actual entries
private int
num_entries;
// array of game entries
private GameEntry[] entries;
//
Default constructor: populate the array "entries"; initialize
// num_entries
to 0
public AllEntries()
{
}
//
Return the array entries (names & scores)
//
The format should be:
// name1 score1
// name2 score2
// : :
public String toString()
{
}
//
This method is called when the array is full and needs
to be grown.
// This
is done by:
// 1. Creating a new array of double
the capacity
// 2. Copying
everything from the old array to this new array.
// 3. Updating the
array reference.
private void growArray()
{
}
//
Insert new entry to the array. Check to see if the name already
// exists in the array. If
so, then just update the score.
// Grow
the array first if it's full.
// Update the num_entries
field.
public void insert(GameEntry e)
{
}
//
Insert new entry to the array at index i. Check to see
if the name
// already exists in the
array. If so, then just update the score. Throw
// an exception if the index
is invalid (the allowable range of indices
// is 0 to num_entries).
// Update the num_entries
field.
public void insertAt(GameEntry e, int i)
{
}
//
Delete the game entry at index i. Throw an exception
if the index is
// invalid, or if the entry
does not exist. Update the num_entries field.
// Don't
forget to shift everything following the 'hole' to the left.
public void delete(int i)
{
}
// Call the private sortBy method. YOU DON'T NEED TO MODIFY THIS ONE.
public void sortByName()
{
sortBy(1);
}
//
Call the private sortBy method. YOU DON'T NEED TO
MODIFY THIS ONE.
public void sortByScore()
{
sortBy(2);
}
//
Sort the array by the specified field:
// If field is 1 then sort by names.
// If field is 2 then sort by scores.
// Use bubble sort. Implement the modified version of bubble sort (with
// flag), for which the best
case is O(n).
private void sortBy(int field)
{
}
//
Print the top k highest scores (including the names).
//
The format should be:
// score1 name1
// score2 name2
// :
:
public void printTopK(int k)
{
}
// YOU DO NOT NEED TO MODIFY
THIS METHOD
// search for a person's
entry in the array by binary search (using
// recursion)
// Return the score of the
person if found, -1 otherwise
// this is the driver that
calls the recursive method
public int
binarySearchDriver(String n)
{
//
call bubble sort first to make sure that the array is
// sorted by names
sortBy(1);
//
call the recursive binary search method
return binarySearch(n, 0,
num_entries-1);
}
// recursive binary search
method
// return the score of the
person if found, -1 otherwise
private int
binarySearch(String n, int
low, int high)
{
}
}
Assignment
4: Due 10/30 before midnight
GameEntryList.java TestAssign4.java assign4_solution_output.txt
Revisit AllEntries
(as in the previous assignment) and implement a sorted, doubly-linked
list (GameEntryList), using the following
specification. The GameEntry class
remains unchanged, but please include it in your submission.
In this assignment you will also
be computing the union and intersection of two lists. More info about union and
intersection are given below. For the purpose of this assignment, you do not
have to worry about the scenario where you might have entries with the same
name but different scores from the two lists (i.e. you can assume that name is
a unique ID, and if two entries from different lists have the same name, then
they must have the same score).
You may add any “helper” methods
in the class that will help make your code look cleaner.
Union:
The union of two lists are all items that occur in either list (without duplicates). For example:
List A: (Adam, 10), (Betty, 20),
(John, 15)
List B: (Betty, 20), (Brian, 22),
(John, 15), (Monica, 13)
Union
of List A and List B is: (Adam, 10), (Betty, 20), (Brian, 22), (John, 15),
(Monica, 13).
Intersection:
The intersection of two lists are items that occur in both lists. For the example above, their
intersection is (Betty, 20), (John, 15)
public class GameEntryList
{
//
default constructor - construct an empty doubly linked list
public
GameEntryList()
{
}
//
check to see if the list is empty
public
boolean isEmpty()
{
}
//
clear the list
public
void makeEmpty()
{
}
//
Insert an entry. Keep the list sorted by name (increasing order).
//
If an entry with the same name already exists, update the score
//
instead of inserting it as a new entry. This allows score updating
//
of an existing entry.
public
void insertSorted (GameEntry
G)
{
}
//
Delete the entry with the specified name. Throw an exception
//
if no such entry exists
public
void delete(String name) throws NoSuchElementException
{
}
//
Return the score if the entry is in the list, -1 otherwise
public
int getScore(String name)
{
}
//
Print the content of the list
public
String toString()
{
}
//
Return true if two lists contain the same entries, false otherwise
public
boolean equals(Object rhs)
{
}
//
Return the number of entries in the list
public
int getCount()
{
}
//
Return the union of the current list and other_list
without
//
modifying either list. For the purpose of this assignment,
//
you do not have to worry about having entries with the same
//
name but different scores in the two lists.
//
Return the resulting list, which should also be sorted by name.
public
GameEntryList getUnion(GameEntryList other_list)
{
}
//
Return the intersection of the current list and other_list
without
//
modifying either list. Return the resulting list.
//
The resulting list should also be sorted by name.
public
GameEntryList getIntersection(GameEntryList other_list)
{
}
//
Return a new list that's sorted by scores in increasing order
//
(without modifying the original list). You can use any sorting
//
algorithm of your choice.
public
GameEntryList sortByScore()
{
}
//
Print the top k scores and their corresponding names
//
(do not modify the original list)
public
void printTopK(int k)
throws InvalidArgumentException
{
}
private GameEntryNode head;
private GameEntryNode tail;
private class GameEntryNode
{
private
GameEntry G;
private
GameEntryNode next;
private
GameEntryNode prev;
public
GameEntryNode(GameEntry G)
{
}
public
GameEntryNode(GameEntry G, GameEntryNode prev, GameEntryNode next)
{
}
}
}
Assignment 5: Due 11/21 before midnight
BSTMain.java input2.txt
assign5_output.txt
Implement a binary search tree for
int using
the following specifications. Only the public methods are listed; most of them
are driver methods and will need private, internal implementation version,
which you’ll need to add yourself.
Throw exceptions for the delete
methods (when the tree is empty, and when the item does not exist), but not
insertion. For insertion, do nothing if the item already exists (since you’re likely
to encounter duplicates with the merge methods).
public class BinarySearchTree
{
class BinaryNode
{
BinaryNode(int el)
{
}
int data;
BinaryNode left;
BinaryNode right;
}
// construct
an empty tree
public BinarySearchTree()
{
}
// construct a
binary tree with the root node
public BinarySearchTree(int el)
{
}
// insert el
into the tree
public void
insert(int el)
{
}
// delete el
from the tree
public void
delete(int el)
{
}
// search for el
in the BST. Return its depth.
// Return -1
if it's not found.
public int find(int el)
{
}
// find and
return the smallest item in the BST
// Return null
if the tree is empty
public int findMin()
{
}
// find and return
the biggest item in the BST
// Return null
if the tree is empty
public int findMax()
{
}
// remove the
smallest item from the BST
public void deleteMin()
{
}
// remove the
largest item from the BST
public void deleteMax()
{
}
// return the
height of the tree
public int getHeight()
{
}
// return the
number of items in the tree
public int getCount()
{
}
// merge two
trees: add the nodes from t to the current tree in
// the
pre-order order
// Ignore duplicates
public void mergePreOrder(BinarySearchTree t)
{
}
// merge two
trees: add the nodes from t to the current tree in
// the
in-order order
// Ignore
duplicates
public void mergeInOrder(BinarySearchTree t)
{
}
// merge two
trees: add the nodes from t to the current tree in
// the
post-order order
// Ignore
duplicates
public void mergePostOrder(BinarySearchTree
t)
{
}
// print the
nodes in the BST in the pre-order order using recursion
public void printPreOrder()
{
}
// print the
nodes in the BST in the in-order order using recursion
public void printInOrder()
{
}
// print the
nodes in the BST in the post-order order using recursion
public void printPostOrder()
{
}
// EXTRA
CREDIT: print the nodes in level-order (you'll need to use a queue
// for this
public void printLevelOrder()
{
}
// print the
nodes in In-Order
public String toString()
{
}
/*********************************************************************
/ Add your private
methods here
*********************************************************************/
private BinaryNode root;
}
Assignment
6: Due 12/8 before midnight
test dictionary file: words_long.txt words_short.txt
test case #1: 4x7.grid.txt 4x7.out.txt
test case #2: 50x50.grid.txt 50x50.out.txt
Write a program that, given a
dictionary of words, finds all instances of those words in a grid of letters.
This puzzle is similar to the word search puzzle, where you circle the words
horizontally, vertically or diagonally in the grid, as described in 10.1 in
Weiss (there are a total of 8 directions to read the letters from the grid).
However, in this case, you’re not given a list of words to find. You have to
find all the dictionary words in the grid. You will be given a dictionary
(list) of English words. Use a hash table to quickly check if a particular
combination of letters is a word in the dictionary. You can use any collision
resolution strategies discussed in class, but you must implement your own
(instead of using HashMap from Java API).
Ignore cases (you can assume that
everything in the grid will be in lower-cases), and consider only words that
are at least three characters long.
Files to turn in: HashTable.java and WordSearch.java
You will be given an input grid
and a dictionary file (i.e. list of words). The first line in the input grid
file is the number of rows, and the second line is the number of columns. The
grid data begins on the 3rd line. The following is an example of
what an input grid file looks like:
4
4
thiswatsoahgfgdt
which is equivalent to the data
grid shown in Figure 10.1:
t h i s
w a t s
o a h g
f g d t
Your program should take two command-line parameters: one for the
dictionary file and one for the grid file. It should output all the words found
in the grid and the total number of words found. The output format should look
something like this (note: the solution might be incomplete):
E (0, 0): this
E (0, 1): his
SE (1, 0): wad
NW (2, 2): hat
NE (3, 0): fat
NW (3, 3): that
6 words found
Extra
Credit: Due 12/12 before midnight
Dictionary.zip
Write a program that reads in a
dictionary of n-letter words from a file, accepts two more n-letter words from
the user and
finds a word ladder from one to the other using the words in the dictionary (so
your program should take 3 command-line arguments: dictionary, start word, end
word). For example, from "dog" to "cat" a possible ladder
is:
dog
dig
fig
fit
fat
cat
Note that at each step, the words only differ by one letter. Differing from the
original version of the puzzle, you are not allowed to add or remove letters
(i.e. the number of letters remains the same). You may assume that there will
be no duplicate words in the dictionary. If the start or the end word doesn’t
exist in the dictionary, manually add them to the data structure(s) you build.
You can use any data structure(s)
you've learned so far (either Java Collections API or your own implementation;
you are also allowed to use the code from the textbook).
This project consists of two
parts:
Part I (1%): Write a report describing how you would solve the
puzzle. Mention any data structures you might use, and how they are used. Be as
specific as possible. Provide Big-O analysis of the running time of your
approach, both on the building of the data structure(s) and the actual search
algorithm. You will be graded on correctness of both your design and the
analysis of time complexity.
Part II (2.5%): Implement Part I.