void printOutD(double d, int p) {
int i=0;
// handle case where d is negative
if (d < 0) {
d *= -1;
System.out.print("-");
}
// print out d to the precision specified by p
for(i=0; i<p; i++)
d *= 10;
// typecast d to an int
i = (int)(d);
// print int form of d
printOutInt(i, p-1);
System.out.println("");
return;
}
void printOutInt(int n, int p) {
if (n >= 10)
printOutInt(n/10, p-1);
if (p == 0)
System.out.print(".");
printDigit( n % 10 );
return;
}
static int ones(int n)
{
if (n < 2)
return n;
return n % 2 + ones(n/2);
}
public void permute( String str ) {
char c[];
c = str.toCharArray();
permute(c, 0, c.length-1);
return;
}
private void permute(char[] str, int low, int high) {
char [] s = new char[str.length];
char tmp;
System.arraycopy(str, 0, s, 0, str.length);
if (high == low)
System.out.println(str);
else {
for(int i=low; i<=high; i++) {
tmp = s[i];
s[i] = s[low];
s[low] = tmp;
permute(s, low+1, high);
}
}
return;
}
(a)
SumOf(i=1 to N)(2i-1) = 2 * SumOf(i=1 to N)i - SumOf(i=1 to N)1
= N(N+1) - N = N^2
(b) The easiest way to prove this is by indcution. The case N=1 is trivial.
Otherwise,
SumOf(i=1 to N+1)i^3 = (N+1)^3 + SumOf(i=1 to N)i^3
= (N+1)^3 + (N^2 * (N+1)^2)/4
= (N+1)^2 * [(N^2)/4 + (N+1)]
= (N+1)^2 * [(N^2+4N+4)/4]
= ((N+1)^2 * (N+2)^2)/(2^2)
= ((N+1)(N+2)) / 2)^2
= (SumOf(i=1 to N+1)i)^2
class Collection {
private int capacity;
private Object[] collection;
private int numFull;
Collection (int max) {
collection = new Object[max];
capacity = max;
numFull = 0;
}
public boolean isEmpty() {
return (numFull == 0);
}
public void makeEmpty(int max) {
numFull = 0;
}
public void insert (Object x) {
if (numFull < capacity) {
collection[numFull++] = x;
}
}
public void remove (Object x) {
for(int i=0; i<numFull; i++)
if (collection[i].equals(x)) {
collection[i] = collection[--numFull];
return;
}
}
public boolean isPresent (Object x) {
for(int i=0; i<numFull; i++) {
if (collection[i].equals(x))
return true;
}
return false;
}
}
2/N, 37, Sqrt(N), N, NloglogN, NlogN, Nlog(N^2), Nlog^2N, N^(1.5), N^2, N^2logN, N^3, 2^(N/2), 2^N. NlogN and Nlog(N^2) grow at the same rate.
(a) True.
(b) False. A counterexample is T1(N) = 2N, T2(N) = N, and f(N) = N.
(c) False. A counterexample is T1(N) = N^2, T2(N) = N, and f(N) = N^2.
(d) False. The same counterexample as in part (c) applies.
For all these programs, the following analysis will agree with a simulation:
According to the problem an algorithm takes .5 ms for input size 100. We would like to determine how large a problem can be solved in 1 min. We use the fact that there are 60,000 ms in 1 min.
We would like to solve for X where: ( .5 / 60000 ) = ( f(100) / f(X) ).
(a) 120,000 times as large a problem, or input size 12,000,000. You solve for
X in the following equation: ( .5 / 60000 ) = ( 100 / X).
(b) Solve for X in the following equation: ( .5 / 60000) = ( (100 log 100) /
(X log X) ). The solution is approximately 3.19 * 10^7.
(c) Solve for X in the following equation: ( .5 / 60000) = ( 100^2 / X^2).
The solution is approximately 34,641.
(d) Solve for X in the following equation: ( .5 / 60000) = ( 100^3 / X^3).
The solution is approximately 4,932.
You do not need to be concerned with constant factors because they cancel
with the ratios above.
Compute X^2, X^4, X^8, X^10, X^20, X^40, X^60, and X^62.
(a) Using public methods, a cut and paste can be done in time proportional to
the amount of cut nodes.
The following solution was written by Changbin Wang:
public static void cutAndPaste (LinkedListItr beg, LinkedListItr end,
LinkedListItr insp)
{
// Assume beg is the position before the cut beginning point.
// Advance the interator.
LinkedListItr itrtmp = beg.advance();
for( ; irttmp.current != end.current; itrtmp.advance())
{
// If the tmp iterator doesn't reach the end iterator, insert the
// the corresponding element in the other list
insp.current.next = new ListNode(itrtmp.current.element,
insp.current.next);
// Advance the temporary iterator
insp.advance();
}
// Bypass the cut part in the first list
beg.current.next = end.current.next;
}
(b) Adding a method directly to the list class allows a cut and paste to be
done in constant time. Note that there can be difficulty reforming the original
list if it is not doubly-linked; it might be better to require an iterator
prior to the cut point. Without the doubly linked list and the previous
iterator, you can use the findPrevious method, but this will make
you algorithm O(N).
//prevb is an iterator prior to the cut point, p is the paste point
public static void cutAndPaste (LinkedListItr prevb, LinkedListItr beg,
LinkedListItr end, LinkedListItr p)
{
prevb.next = end.current.next;
end.current.next = p.current.next;
p.current.next = beg.current.next;
}
The following solution, provided by Daniel R. McCarthy, uses the
findPrevious method:
public static void cutAndPaste (LinkedListItr startcut,
LinkedListItr endcut,
LinkedListItr startpaste)
{
ListNode previous = findPrevious (startcut.retrieve);
previous.next=endcut.current.next;
endcut.current.next = startpaste.current.next;
startpaste.current.next=startcut.current.next;
}
The following solution was written by Daniel R. McCarthy
public static LinkedList intersect (LinkedList list1, LinkedList list2)
{
LinkedList result = new LinkedList();
LinkedListItr trace1 = new LinkedListItr(list1.header);
LinkedListItr trace2 = new LinkedListItr(list2.header);
LinkedListItr trace3 = new LinkedListItr(result.header);
trace1.advance();
trace2.advance();
while (!isPastEnd(trace1) && !isPastEnd(trace2))
{
if (trace1.retrieve().compareTo(trace2.retrieve()) < 0)
trace1.advance();
else if (trace1.retieve().compareTo(trace2.retrieve()) > 0)
trace2.advance();
else
{
trace3.next = new Listnode(trace1.retrieve());
trace3.advance();
}
}
return (result);
}
public static int Fib(int N) {
return fib_iter(1,1,N);
}
public static int fib_iter(int a, int b, int count) {
if (count == 0)
return b;
else
return fib_iter(a + b, a, count - 1);
}
Course: W3139-002, Data Structures and Algorithm Analysis in JAVA
Professor Nieh
Homework 1, due 2/16/99
Name: Aro Osako
Email: *****@columbia.edu
SSN#: ***-**-****
----
Files submitted:
Problem 1: DecToBin.java
DecToBin_Log.txt
Problem 2: LLADT.java
LLADT_Log.txt
/DataStructures/Comparable.java
/DataStructures/Hashable.java
/DataStructures/LinkedList.java
/DataStructures/LinkedListItr.java
/DataStructures/ListNode.java
/DataStructures/MyInteger.java
###################################
Problem 1 - DecToBin
----
This program will prompt the user for an integer input, then print out the
binary equivalent of the integer.
When dealing with negative numbers, the program will utilize 2' complement
methodology.
It will only take integers for inputs.
Known Issues: entering a non-integer results in termination of program.
To Compile: Type "javac DecToBin.java" at CUNIX prompt.
To Run: After compiling, type "java DecToBin" at CUNIX prompt.
Log File: Contains several test runs of DecToBin using integers -32 to 32.
###################################
Problem 2 - LLADT (Linked List Abstract Data Type)
----
This program allows the user to manipulate a linked list in the following ways:
1. Insert: prompts for integer, then adds it to the head of the list.
2. Delete: prompts for integer, then removes its first occurence from the list.
3. Print: prints the elements contained in the list.
4. ReversePrint: prints the elements contained in the list in reverse order.
5. Swap: prompts for position, then switches element at that position with the
succeeding element.
6. Flip: reverses the order of elements in the list.
7. Quit: exits the program.
Additionally, I have provided a "Help" method that displays a more detailed
description of each command than provided in the generic menu.
It will take a single character string for input as the command (as indicated
by the options menu), then if necessary, will take an additional integer input
before executing the command.
Known Issues: entering a zero or non-integer when prompted for integer input
results in termination of the program.
To Compile: In the directory containing LLADT.java, there must exist a sub-
directory "DataStructures" containing the following files:
- Comparable.java
- Hashable.java
- LinkedList.java
- LinkedListItr.java
- ListNode.java
- MyInteger.java
All that being properly configured, type "javac LLADT.java" at
the CUNIX prompt.
To Run: After compiling, type "java LLADT" at the CUNIX prompt. Input command
as indicated by the options menu.
Log File: contains a sample run of the program.
public static void ones(int i, int carry, int a[], int count)Where
i is the number to convert to binary, carry
will be the carry bit for converting to 2's complement, a is your
array to store the bits, and count will keep track of your
current index into the array during your recursive calls. count
will be begin at zero, and be incremented before every recursive call.
It is helpful to realize the algorithm uses two different lines of recursion,
one for positive numbers and one for negative numbers. Each line having its own
base case and recursive calls. The base case for positive numbers will be when
i is equal to 1. The recursive progress toward the base
case will be obtained by dividing i by 2, where the modulus of
this division will be assigned to the countth bit of the array.
For positive numbers, the recursive call will always have a carry
bit of 0.
The recursion for negative numbers is similar, but slightly more involved,
because we must convert the number into 2's complement (which is why we
initialize the a array to all 1's for negative numbers). Our base
case now will be when i is equal to -1. When we reach the base
case we will assign to
a[count] the carry bit, which should be 0 for the
most significant bit. We still make progress toward the base case
by dividing i by 2. However, after the division we will flip the
bit in order to obtain the 1's complement (recall the procedure for converting
to 2's complement). We will add to this the carry bit from the
previous recursive call (or from the original call). If this result is not
greater than 1, we will not have a carry bit on our next recursive call. So we
assign a[count] the result of the addition and recurse on
i/2 and a 0 carry bit. Otherwise (result > 1), we
will
indeed have another carry bit, so we assign a[count]=0 and recurse
on i/2 and a 1 carry bit.
Note that for a negative number, our original method call will have a carry bit of 1. This will have the effect of taking the 1's complement of the number and adding 1 to it, which is precisely how we convert to 2's complement. When the recursion ends we print out the array starting from the the 31st (32-1) index. Here is the code for this algorithm:
import java.io.*;
public class binary{
final static int SIZE = 32;
public static void ones(int i,int carry,int a[],int count){
int rem;
if (i > 0 && i < 2) /* base case for positive i */
a[count] = i; /* i=1 since MSB should be 1 */
else if (i > 0) { /* recursive case for positive i */
a[count++] = i % 2;
ones(i / 2, 0, a, count);
}
else if (i < 0 && i > -2) { /* base case for negative i */
a[count] = carry; /* MSB should be 0 after 1's comp */
}
else if (i < 0) { /* recursive case for negative i */
rem = ((-i % 2)==1)?0:1; /* take remainder and do 1's comp */
rem += carry; /* add carry from prev bit for 2's comp */
if (rem > 1) { /* if 1's comp plus carry is 2 */
a[count++] = 0;
ones(i / 2, 1, a, count);
}
else { /* if no need to carry again */
a[count++] = rem;
ones(i / 2, 0, a, count);
}
}
}
public static void main(String args[]){
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String buff = null;
boolean exit = false;
int i=0, j, count;
int a[] = new int[SIZE];
while(!exit) {
try{
System.out.print("Please enter an integer: ");
i = Integer.parseInt(in.readLine());
exit = true;
}
catch(Exception e) { //Error Handling
System.out.println("Error. Invalid entry.\n");
}
}
count = 0;
if (i < 0) /* initialize 1's in array if neg */
for (j = 0; j < SIZE; j++)
a[j] = 1;
else
for (j = 0; j < SIZE; j++) /* initialize 0's in array if pos */
a[j] = 0;
if (i < 0)
ones(i, 1, a, count);
else
ones(i, 0, a, count);
System.out.print("The binary representation of "+i+"is:\n\t");
for (j = SIZE-1; j >= 0; j--)
System.out.print(a[j]);
System.out.println("");
}
}
import java.io.*; // A.SARAFIS
import java.util.*; // HW1 , CS3139
//It prints out the binary representation
//of an integer in 32-bit 2's complement format.
public class Binary {
private char [ ] array ;
private final static String exit = "exit";
private static String s ;
//Constructor
public Binary ( ) {
s = "" ;
array = new char [ 32 ]; //to represent a 32-bit
for (int i = 0 ; i < 32 ; i++ )
array [ i ] = '0' ;
}
public static void main (String[ ] args) throws IOException {
String input = "";
int number = 0 ;
//Create an object from Binary
Binary bi = new Binary( );
BufferedReader response = new BufferedReader
(new InputStreamReader ( System.in ) ) ;
StringTokenizer st ; // to tokenize the input
while ( !input.equals(exit)) {
System.out.println (" To Exit Type : exit " );
System.out.print ("Otherwise , enter an integer :" );
System.out.flush ( );
try {
input = response.readLine( ); //read the input into a string
st = new StringTokenizer ( input );
input = st.nextToken( ); //give back input only its 1st token
if ( input.equals ( exit ) )
System.exit(-1) ;
else {
number = Integer.parseInt (input ); //convert to int
s = bi.transformation (number ); //convert to binary
//Put the characters of s into the array
bi.intoArray ( s );
if ( number >= 0 )
bi.printArray (number ) ; //immediately
else {
bi.neg_transformation ( ) ; // that is elaborate more
bi.printArray (number ) ;
}//else
}//else
}//try
catch ( Exception e ) {
System.out.print ("That Was Not An Integer !" );
}
}//while
}//main
//Transform the int in its binary representation
//assuming it is always positive.This is as much
//recursive as I can get.
private String transformation ( int n ) {
int temp = 0 ;
if ( n >= 0 )
temp = n ;
else
temp = -n ; // so temp is always positive
if (temp >= 2 )
//reduce the problem and count the recursions
transformation ( temp/2 ) ;
//put the bin-digit into a string
s = new String ( s+temp % 2);
return s ;
}//method transformation
//In case the number input is negative
private void neg_transformation ( ) {
//1's complement
for ( int i = 0 ; i < array.length ; i++ ) {
if (array [ i ] == '0')
array [ i ] = '1' ;
else
array [ i ] = '0' ;
}//for
//add 1
if ( array [ 31 ] == '0' )
array [ 31 ] = '1' ;
else {
int x = 31 ;
while ( array [ x ] != '0' && x > 0 ) {
array [ x ] = '0' ;
x--;
}
//finish the addition
array [ x ] = '1' ;
}//else
}//method neg_transformation
private void intoArray (String t) {
for (int i = t.length( ) ; i > 0 ; i-- )
array [31-i +1] =t.charAt( t.length ( )-i );
}//method intoArray
//Print the 32-bit
private void printArray( int y ) {
System.out.println(" The binary representation of "+y);
System.out.print (" is :");
for ( int i = 0 ; i < array.length ; i++ )
System.out.print (array [ i ]);
System.out.println( );
//clean the house
for ( int i = 0 ; i < array.length ; i++ )
array [ i ] = '0';
s = "";
}
}//class Binary
File ListNode.java:
//This is the class for Nodes in a Linked List
class ListNode
{
// Constructors
ListNode( Integer theElement )
{
this( theElement, null );
}
ListNode( Integer theElement, ListNode n )
{
element = theElement;
next = n;
}
Integer element; //object which this node contains
ListNode next; //Reference to next node.
}
File LinkedListItr.java
import ListNode.*;
/*
* This is the LinkedList Iterator Class
*/
public class LinkedListItr
{
//Constructor
LinkedListItr( ListNode theNode )
{
current = theNode;
}
//Obvious, but also just tells if the Iterator is a null
//reference
public boolean isPastEnd( )
{
return current == null;
}
//Function returns element of node which Iterator points to
public Integer retrieve( )
{
return isPastEnd( ) ? null : current.element;
}
//Points Iterator to next node in list
public void advance( )
{
if( !isPastEnd( ) )
current = current.next;
}
ListNode current; // Current position
}
File: Stack.java
import java.io.*;
import java.util.*;
import ListNode.*;
// This is the Stack class. It uses a linked-list implementation
public class Stack
{
// Constructor
public Stack( )
{
topOfStack = null;
}
// Simple Boolean function
public boolean isEmpty( )
{
return topOfStack == null;
}
// "Empties" the Stack.
// Nodes will be dealt with by garbage-collector
public void makeEmpty(
{
topOfStack = null;
}
// returns the most recently added integer on the stack, without
// actually changing the stack itself.
public Integer top( )
{
if( isEmpty( ) )
return null;
return topOfStack.element;
}
// Removes the most recently added integer, does not return it,
// however. See topAndPop() function.
public void pop( ) //throws Underflow
{
if( isEmpty( ) ){
//throw new Underflow( );
}
else{ topOfStack = topOfStack.next;}
}
// Returns the most recently added integer, and removes it from
// the list.
public Integer topAndPop( )
{
if( isEmpty( ) )
return null;
Integer topItem = topOfStack.element;
topOfStack = topOfStack.next;
return topItem;
}
// Puts an integer on the stack.
public void push( Integer x )
{
topOfStack = new ListNode( x, topOfStack );
}
private ListNode topOfStack;
}
File: LinkedList.java:
import ListNode.*;
import LinkedListItr.*;
import Stack.*;
import java.io.*;
import java.util.*;
// This is the LinkedList Class
public class LinkedList
{
//Main Fxn.
public static void main (String args[]){
MenuFunction();
return;
}
// Data Attributes
private ListNode header;
private ListNode tail;
// Constructors
public LinkedList( )
{
header = new ListNode( null );
tail = header;
}
// Obvious boolean fxn.
public boolean isEmpty( )
{
return null == header.next;
}
// "Empties" the list of all its nodes.
// If the nodes are not referred to by other objects,
// they will be garbage-collected.
public void makeEmpty( )
{
header.next = null;
}
// Gives back an Iterator to the header node of the list
public LinkedListItr zeroth()
{
return new LinkedListItr(header);
}
// Gives back an Iterator to the first node in the list.
// Obviously, the reference is null if there are no nodes.
public LinkedListItr first( )
{
return new LinkedListItr( header.next );
}
//Gives back an Iterator to the last node in the list.
//Obviously, the reference is null if there are no nodes.
public LinkedListItr last()
{
return new LinkedListItr(tail);
}
// Inserts x in a new node after the one which p points to.
// If the Iterator is null, the insertion fails, no errors
// occur, however.
public void insert( Integer x, LinkedListItr p )
{
if( null != p && null != p.current )
p.current.next = new ListNode( x, p.current.next );
if(p.current == tail)
tail = tail.next;
}
// Returns an Iterator to the first instance of x in the
// list. Iterator is null if x is not found.
public LinkedListItr find( Integer x )
{
ListNode itr = header.next;
while( null != itr && !itr.element.equals( x ) )
itr = itr.next;
return new LinkedListItr( itr );
}
// Returns an Iterator to the node before the first instance of
// integer x. If x is not found, points to last element in the list.
public LinkedListItr findPrevious( Integer x )
{
ListNode itr = header;
while( null != itr.next && !itr.next.element.equals( x ) )
itr = itr.next;
return new LinkedListItr( itr );
}
// Removes the first instance of Integer x in the list
// If integer x not found, list is unchanged.
public void remove( Integer x )
{
LinkedListItr p = findPrevious( x );
if (null == p.current.next)
System.out.println("Integer: "+x+" not in list.");
else{
if(p.current.next==tail)
tail = p.current;
p.current.next = p.current.next.next;} // Deleted node
// is garbage-collected
}
// Just prints the list
public static void printList( LinkedList theList )
{
if( theList.isEmpty( ) )
System.out.print( "Empty list" );
else
{
System.out.print("Your List: ");
LinkedListItr itr = theList.first( );
for( ; !itr.isPastEnd( ); itr.advance( ) )
System.out.print( itr.retrieve( ) + ", " );
}
System.out.println( );
}
//These are all private functions that make a nice interface, and
//wrapper functions which call the real routines.
// MenuFunction() = Workhorse of the main() function
// calls a menu method, and routes the program based on that method's
// output.
private static void MenuFunction()
{
LinkedList L = new LinkedList();
String[] menuOptions= {"Insert an integer", "Delete an Integer",
"Print the List", "Print the List in Reverse Order",
"Swap Two Elements", "Reverse the Entire List",
"Exit the Program"};
boolean again = true;
while (again){
int menuchoice = GetMenuChoice(menuOptions);
switch (menuchoice){
case 1: L.Insert(); break;
case 2: L.Delete(); break;
case 3: printList(L); break;
case 4: L.PrintReverse(); break;
case 5: L.Swap(); break;
case 6: L.Reverse(); break;
case 7: again = false; break;
default: System.out.println("you chose: "+menuchoice); break;
};
}
return;
}
//Takes in array of strings, shows menu, returns number of the menu
//choice made
private static int GetMenuChoice(String [] menuOptions)
{
System.out.println("\n------------------------------------------");
System.out.println("Please choose from menu below:");
for (int i=0; imenuOptions.length))
choice = GetInteger("Type the number of the option you want: ");
return (choice);
}
//This version is just default of one below
private static int GetInteger()
{
return(GetInteger("Enter an Integer: "));
}
//Just an exception-proof integer input function
private static int GetInteger(String s)
{
BufferedReader in = new BufferedReader(new
InputStreamReader(System.in));
while(1<2){
try{
System.out.print(s);
System.out.flush();
String oneLine = in.readLine();
StringTokenizer st = new StringTokenizer(oneLine);
int i = Integer.parseInt(st.nextToken());
return (i);
}catch(Exception ioe){
System.out.println("IO error:" + ioe);
}
}
return (0);
}
//Delete and Insert are pass-through functions
private void Insert()
{
int i = GetInteger("Please type in the integer you would like to insert: ");
insert((new Integer(i)), last());
return;
}
private void Delete()
{
int i = GetInteger("Enter the integer which you would like to delete: ");
remove(new Integer(i));
return;
}
private void PrintReverse()
{
Stack s = new Stack();
LinkedListItr itr = first();
while (!itr.isPastEnd()){
s.push(itr.retrieve());
itr.advance();
}
System.out.print("Your reversed list is: ");
while (!s.isEmpty()){
Integer i = s.topAndPop();
System.out.print(i+", ");
}
}
private void Swap()
{
int i = GetInteger
("Enter the position of the node to be swapped with its successor:\n");
if(i>0){
ListNode itr = header;
while((--i>0)&&(null != itr.next)){
itr = itr.next;
}
if ((null != itr.next)&&(null != itr.next.next)){
ListNode tempItr = itr.next.next;
itr.next.next = tempItr.next;
tempItr.next = itr.next;
itr.next = tempItr;
} else {
System.out.println
("That node is nonexistent or has no successor.\nSwap failed");
}
} else{
System.out.println("That node is nonexistent or has no successor.\nSwap failed");
}
}
private void Reverse()
{
Stack s = new Stack();
LinkedListItr itr = first();
Integer tempInt;
while (!itr.isPastEnd()){
tempInt = itr.retrieve();
s.push(tempInt);
remove(tempInt);
itr = first();
}
while (!s.isEmpty()){
insert(s.topAndPop(), last());
}
}
}