Chapter 1

 

import java.awt.*;

import java.util.*;

import java.io.*;

 

public class Class1

{

     public static void main (String[] args)throws IOException

    {

        while(true)

        {

            BufferedReader input=new BufferedReader(new InputStreamReader(System.in));

            String s=input.readLine();

            System.out.println(s.length());

            }

                                               

     }

}

 

Fig 1.10 Java program to count number of input characters.

 

 

public class  ListNode{

            Object data;

            ListNode next;

ListNode(Object o, ListNode nextNode)

{

            data=o;

            next=nextNode;

}

 

Fig 1.14 Java program of node class(A macro for defining list cells).

 

 

 

 

 

 

 

 

 

 

 

Chapter 2

 

public static void SelectionSort( int A[], int n )

            {

                        int i, j, small, temp;

                        for( i = 0; i <A.length-1; i++ )

                        {

                                    small = i;

                                    for( j = i+1; j < A.length; j++ )

                                    {

                                                if( A[j] < A[small] )

                                                            small = j;

                                    }

                                    temp = A[small];

                                    A[small] = A[i];

                                    A[i] = temp;

                        }

            }

 

Fig 2.2 A Java program for Iterative selection sort.

 

 

import java.io.*;

import java.util.StringTokenizer;

public class Class1

{

    private static String input;

    static int[] array;

    private static int no=0;

    public static void main (String[] args) throws IOException

   {

            BufferedReader in=new BufferedReader(new InputStreamReader(System.in));

            String input = in.readLine();

                       

            StringTokenizer tokens = new StringTokenizer(input);

            array = new int[tokens.countTokens()];

                                    while(tokens.hasMoreTokens()){

                                                array[no++] = Integer.parseInt(tokens.nextToken());

                                    }

                       

                        printarray( array );

                        SelectionSort( array, array.length );

                        System.out.println();

                        printarray( array );

                        System.in.read();

            }

           

            public static void printarray( int A[] )

            {

                        for( int i = 0; i < A.length; i++ )

                                    System.out.println( A[i] );

            }

           

            public static void SelectionSort( int A[] )

            {

                        int i, j, small, temp;

                        for( i = 0; i < A.length-1; i++ )

                        {

                                    small = i;

                                    for( j = i+1; j < A.length; j++ )

                                    {

                                                if( A[j] < A[small] )

                                                            small = j;

                                    }

                                    temp = A[small];

                                    A[small] = A[i];

                                    A[i] = temp;

                        }

            }

}

Fig 2.3 A sorting program using selection sort in Java

 

for (i = 0; i < A.length -1; i++) {

                        small = i ;

                        for(j = i+1; j< A.length; j++)

                              if(A[j]<A[small])

                                    small = j;

                        temp = A[small];

                        A[small] = A[i] ;

                        A[i] = temp;

}

Fig 2.11 The body of the SelectionSort function.

 

 

 

 

 

 

 

 

 

 

BufferedReader input = new BufferedReader( new InputstreamReader( System.in ) );

int n = Integer.parseInt(input.readLine());

i = 2;

fact = 1;

while ( i <= n ) {

            fact = fact * i ;

            i++;

}

System.out.println( fact );

 

Fig 2.13 Factorial program fragment in Java.

 

 

sum = 0;

BufferedReader = new BufferedReader( new InputstreamReader( System.in ) );

int x = Integer.parseInt(input.readLine());

while ( x >= 0) {

            sum = sum + x ;

            BufferedReader = new BufferedReader( new InputstreamReader( System.in ) );

int x = Integer.parseInt(input.readLine());

}

 

Fig 2.14 Summing a list of integers terminated by a negative integer.

 

 

public static void fact(int n)

{

            if (n<=1)

                 return  1;

            else

                 return n*fact(n-1);

}

 

Fig 2.19 Recursive function to compute n! for n => 1. in Java

 

 

 

 

 

 

 

 

 

 

 

 

public void recSS( int A[], int i)

{

            int j, small, temp;

            if (i< A.length – 1){  //basis is when i=A.length-1,in which case the function

                                                //returns without changing A. Induction follows

                        small = i;

                        for(j = i + 1; j<A.length; j++)

                                    if (A[j]<A[small])

                                                small = j;

                        temp= A[small];

                        A[i] =temp;

                        recSS (A, i+1, A.length);

            }

}

 

Fig 2.22 Recursive selection sort

 

 

public class  LIST{

            int element;

            LIST next;

LIST(int o, LIST nextNode)

{

            element=o;

            next=nextNode;

}

 

 

public LIST merge(LIST list1, LIST list2)

{

            if (list1= =null)

                        list2;

            else if (list2 = = null)

                        list1;

            else if(list1.element<=list2.element){

                        list1.next=merge(list1.next, list2);

                        list1;

            }

            else{

                        list2.next = merge(list1, list2.next);

                        list2;

            }

}

 

Fig 2.24 Recursive merge

 

public LIST split (LIST list)

{

            LIST pSecondCell = new LIST;

 

            if (list = = null)

                        return null;

            else if (list.next  = = null)

                        returm null;

            else {

                        pSecondCell = list.next;

                        list.next =pSecondCell.next;

                        pSecondCell.next = split (pSecondCell.next);

                        return pSecondCell;

            }

}

 

Fig 2.27 Splitting a list into two equal pieces.

 

public LIST MergeSort(LIST list)

{

            LIST SecondList = new LIST;

           

            if (list = = null)

return null;

            else if (list.next = = null)

return list;

            else{

                        SecondList = split(list);

                        merge (MergeSort(list), MergeSort (SecondList));

            }

}

 

Fig 2.29 The mergesort algorithm

 

 

 

 

 

 

 

 

 

public class ms {

 

    public static void main(String args[]) {

      int[] x = {7,6,8,5,9,10,0,4,1,2,3};

      Cell list1 = makelist(x,0);

      printlist(list1);

      list1 = mergesort(list1);

      printlist(list1);

    }

 

    static Cell makelist(int[] arry,int loc) {

      Cell temp;

      if (loc >= arry.length) return null;

      else {

          temp = new Cell();

          temp.element = arry[loc++];

          temp.next = makelist(arry,loc);

      }

      return temp;    

    }

 

    static void printlist(Cell list){

      if (list == null) System.out.println();

      else  {

          System.out.print(list.element + " , ");

          printlist(list.next);

      }

    }

 

    static Cell mergesort(Cell list1) {

      //      System.out.print("Mergsort: "); printlist(list1);

      Cell list2 ;

      if (list1 == null) return null;

      else {

          if (list1.next == null) return list1;

          else {

            list2 = split(list1);

            return merge(mergesort(list1),mergesort(list2));

          }

      }

    }

 

    static Cell merge(Cell list1, Cell list2) {

      //      System.out.print("Merging : "); printlist(list1);

      //      System.out.print("  and   : "); printlist(list2);

      if( list1 == null) return list2;

      else {

          if( list2 == null) return list1;

          else {

            if (list1.element <= list2.element) {

                list1.next = merge(list1.next,list2);

                return list1;

            }

            else {

                list2.next = merge(list1,list2.next);

                return list2;

            }

          }

      }

    }

     

    static Cell split(Cell list){

      Cell list2;

      if (list == null) return null;

      else {

          if (list.next == null) return null;

          else {

            list2 = list.next;

            list.next = list2.next;

            list2.next = split(list2.next);

            return list2;

          }

      }

    }

 

}

 

class Cell {

    public int element;

    public Cell next;

}

 

Fig 2.32 Two recursive functions, sum and find0

 

static int sum (Cell l)

            if (l == null) return 0 ;

            else return l.element + sum(l.next);

}

 

static boolean find0(Cell l) {

            if (l == null) return false;

            else if (l.element == 0) return true;

            else return find0(l.next);

}

 

CHAPTER3

 

small = i ;

for (j= i+1;j < A.length; j++)

            if (A[j] < A[small])

                        small = j;

 

Fig 3.1 Inner loop of selection sort.

 

 

 

 

 

public static int PowerofTwo( int n)

{

            int i ;

 

            i = 0;

            while ( n%2 = = 0) {

                        n = n/2 ;

                        i++ ;

            }

            return i ;

}

Fig 3.5 Counting factors of 2 in a positive integer n.

 

BufferedReader = new BufferedReader( new InputstreamReader( System.in ) );

int n = Integer.parseInt(input.readLine());

for ( i =0; i<n; i++)

            for (j =0; j<n; j++)

                        A[i] [j] = 0;

 for ( i =0; i<n; i++)

            A [i] [i] = 1;

 

Fig 3.7 Program fragment to make A an identity matrix.

 

for ( i =0; i<A.length-1; i++) {

            small = i ;

            for(j = i + 1; j<A.length; j++)

                        if (A[j]<A[small])

                                    small = j;

            temp= A[small];

            A[i] =temp;

}

 

Fig 3.8 Selection Sort fragment.

 

if (A[1][1] = = 0)

            for (i = 0; i<n; i++)

                        for (j = 0; j<n; j++)

                                    A[i][j] = 0;

else

            for (i = 0; i<n; i++)

                        A[i][i] =1;

 

Fig 3.9 Example of an if-else selection statement

 

 

i = 0 ;

while ( x ! =A[i] )

            i++;

 

Fig 3.10 program fragment for linear search.

 

for (i=0; i< A.length-1; i++)

            for (j = i+1; j< A.length; j++)

                        for (k= i; k< A.length; k++)

                                    A[j] [k] = A[j] [k] – A[i] [k] * A[j] [i] / A[i] [i] ;

 

Fig 3.18 Program for Exercise 3.7.2

 

 

import java.io.*;

import java.util.StringTokenizer;

public class Class1                                      check this out later

{

    private static String input;

    static int[] array;

    private static int no=0;

    public static void main (String[] args) throws IOException

   {

            BufferedReader in=new BufferedReader(new InputStreamReader(System.in));

            String input = in.readLine();

                       

            StringTokenizer tokens = new StringTokenizer(input);

            array = new int[tokens.countTokens()];

                                    while(tokens.hasMoreTokens()){

                                                array[no++] = Integer.parseInt(tokens.nextToken());

                                    }

                       

                        printarray( array );

                        SelectionSort( array, array.length );

                        System.out.println();

                        printarray( array );

                        System.in.read();

            }

 

 

Fig 3.17

 

 

 

 

 

for ( i = 1; i <= n; i++ ) {

            m = 0;

            j = i;

            while ( j%2 = = 0 ) {

                        j = j / 2;

                        m ++;

            }

}

 

Fig 3.19 Program for Exercise 3.7.3

 

 

public static void prime ( int n )

{

            int i = 2;

            while ( i * i <= n)

                        if (n%i = = 0 )

                                    return FALSE;

                        else

                                    i++;

            return TRUE;

}

 

Fig 3.20 Program for Exercise 3.7.4

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

import java.io.*;

import java.util.*;

 

public bar (int x, int n);

public foo (int x, int n);

 

 

public class main( )

{

 

            int a, n ;

            BufferedReader = new BufferedReader( new InputstreamReader( System.in ) );

int n = Integer.parseInt(input.readLine());

 

a = foo ( 0, n) ;

System.out.print ( bar (a, n));

}

 

public static void bar ( int x, int n)

{

            int i ;

 

            for (i = 1; i<=n; i++)

                        x += i ;

            return x ;

}

 

public static void foo ( int x, int n)

{

            int i ;

 

            for (i = 1; i<=n; i++)

                        x += bar(i , n);

            return x ;

}

 

Fig 3.21 Program illustrating nonrecursive function calls.

 

public static int fact(int n)

{

            if (n <= 1)

                        return 1;

            else

                        n*fact(n-1);

}

Fig 3.23 Program to compute n!

public static int fibonacci (int n)

{

            if (n<=2)

                        return 1;

            else

                        return fibonacci(n-1) + fibonacci(n-2);

}

 

Fig 3.24 Java function computing Fibonacci numbers.

 

public static LIST merge(LIST list1, LIST list2)

{

            if (list1 = = null)

return list2;

            else if (list2 = = null)

                        return list1;

            else if (list1.element <= list2.element) {

                        list1.next = merge(list1.next,list2)

                        return list1;

            }

            else {

                        list2.next = merge(list1, merge list2.next);

                        return list2;

            }

}

 

Fig 3.25 The function merge

 

public static LIST split (LIST list)

{

            LIST pSecondCell = new LIST( );

 

            if (list = = null)

                        return null;

            else if (list.next = = null)

                        return null;

            else {

                        pSecondCell = list.next;

                        list.next = pSecondCell.next;

                        pSecondCell.next = split(pSecondCell.next);

                        return pSecondCell;

            }

}

 

Fig 3.27 The function split.

 

public static LIST MergeSort(LIST list)

{

            LIST SecondList = new LIST( );

 

            if (list = = null)

                        return null;

            else if (list.next = = null)

                        return list;

            else{

                        SecondList = split(list);

                        Return merge(MergeSort(list), MergeSort(SecondList));

            }

}

 

Fig 3.28 The mergesort algorithm.

 

if (i < A.length-1) {

            small = i ;

            for (j = i+1 ; j< A.length; j++)

                        if (A[j] < A[small] )

                                    small = j ;

            temp = A[small];

            A[small] = A[i] ;

            A[i] = temp ;

            RecSS( A, i+1);

            }

}

 

Fig 3.29 Recursive selection sort.

 

 

Chapter4

 

c = 1;

for (i = n; i > n-m; i--)

            c *= i;

for (i=2 ; i <= m; i++)

            c /= i;

 

Fig 4.9 Code to compute (n/m)

 

 

 

 

 

 

public static int choose(int n, int m)

{

 

            int n, m ;

 

            if (m < 0 | | m > n ) {

                        System.out.println( “invalid input”);

                        return 0 ;

            }

            else if ( m == 0 | | m = = n)

                        return 1;

            else

                        (choose(n-1, m-1) + choose(n-1, m));

}

 

Fig 4.10 Recursive function to compute (n/m).

 

public BOOLEAN find (int x, int A[ ] )

{

            int i ;

 

            for (i = 0; i < A.length; i++)

                        if( A[i] = = x )

                                    return TRUE;

            return FALSE;

}

 

Fig 4.23 Finding an element x in an array A of size n.

 

 

Chapter 5

 

public class TreeNode

{

            Object element;

            TreeNode firstChild;

            TreeNode nextSibling;

}

 

Node declaration for tree.

 

 

 

 

 

 

 

public class pNode

{

            char letter;

            int isword;

            pNode leftmostChild;

pNode rightSibling;

}

 

public class pNode seek( char let, pNode n)

{

            c = n.leftmostChild;

            while ( c!= null)

                        if(c.letter = = let)

                                    break;

                        else

                                    c = c.rightSibling;

            return c;

}

 

Fig 5.12 finding a child for a desired letter.

 

public void preorder(pNode n )

{

            pNode c ;

            System.out.print(n.nodeLabel ) ;

            while ( c != null ){

                        preorder(c);

                        c = c.rightSibling ;

            }

}

 

Fig 5.15 Preorder traversal function.

 

public void postorder(pNode n)

{

            pNode c ;

 

            c = n.leftmostChild ;

            while(c != null ) {

                        postorder(c) ;

                        c = c.rightSibling ;

            }

            System.out.print( n.nodeLabel) ;

}

Fig 5.17 Recursive postorder function

public void computeHt(pNode n)

{

            pNode c ;

 

            n.height = 0 ;

            c = n.leftmostChild ;

            while ( c != null ){

                        computeHt(c) ;

                        if (c.height >= n.height)

                                    n.height = 1+c.height ;

                        c = c.rightSibling ;

            }

}

 

Fig 5.22 Procedure to compute the height of all the nodes of a tree.