Sample IC Programs

We encourage students to write their own programs, but we provide here a few to get people started:

• Quicksort
• Sieve
• Matrix multiply

Quicksort.ic

class Quicksort {
    int[] a;
    
    int partition(int low, int high) {
	int pivot = a[low];
	int i = low; 
	int j = high;
	int tmp;

	while (true) { 
	    while (a[i] < pivot) i = i+1;
	    while (a[j] > pivot) j = j-1;
	    
	    if (i >= j) break;
	    
	    tmp = a[i];
	    a[i] = a[j]; 
	    a[j] = tmp;
	    i = i+1;
	    j = j-1;
	} 
	
	return j;
    }

    void quicksort(int low, int high) {
	if (low < high) {
	    int mid = partition(low, high);
	    quicksort(low, mid);
	    quicksort(mid+1, high);
	}
    }

    void initArray() {
	int i = 0;
	while(i < a.length) {
	    a[i] =  Library.random(a.length*2);
	    i = i+1;
	}
    }

    void printArray() {
	int i = 0;

	Library.print("Array elements: ");
	while(i<a.length) {
	    Library.printi(a[i]);
	    Library.print (" ");
	    i = i+1;
	}
	Library.print("\n");
    }

    void main(string[] args) {
	int n;

	if (args.length != 1) {
	    Library.println("Unspecified array length");
	    Library.exit(1);
	}

	n = Library.stoi(args[0],0);
	if (n<=0) {
	    Library.println("Invalid array length");
	    Library.exit(1);
	}
	a = new int[n];

	initArray();
	printArray();
	quicksort(0, n-1);
	printArray();
    }
}

Sieve.ic

class Sieve {

  int[] num;

  void initArray() {
    int i = 0;
    while (i < num.length) {
      num[i] = i;
      i=i+1;
    }
  }

  void sieveAll() {
    int i = 2;
    while (i < num.length) {
      sieve(i);
      i=i+1; 
    }
  }

  void sieve(int n) {
    int i = 2*n;
    while (i < num.length) {
      num[i] = 0;
      i=i+n;
    }
  }

  void printPrimes() {
    int i = 2;
    Library.print("Primes less than ");
    Library.printi(num.length);
    Library.print(": ");
    while (i < num.length) {
      if (num[i] != 0) {
        Library.printi(num[i]);
        Library.print(" ");
      }
      i=i+1;
    }
  }


  void main(string[] args) {
    int n;

    if (args.length != 1) {
      Library.println("Unspecified number.");
      return;
    }

    Library.println("");
    n = Library.stoi(args[0], 0);
    if (n <= 0) {
      Library.println("Invalid array length");
      return;
    }
    num = new int[n];

    initArray();
    sieveAll();
    printPrimes();
    Library.println("");

  }

}

MatrixMult.ic

class MatrixMult {
    int[][] a, b, c;
    
    void multiply(){
    	int i, j, k;
	i = 0;
	while(i < a.length){
	    j = 0;
	    while(j < c[i].length){
	        c[i][j] = 0;
	        k = 0;
		while(k < a[i].length){
	            c[i][j] = c[i][j] + a[i][k] * b[k][j];
		    k = k + 1;
	        }
		j = j + 1;
	    }
	    i = i + 1;
	}
    }

    void initMatrix(int[][] m) {
	int i, j;
	i = 0;
	while(i < m.length){
	    j = 0;
	    while(j < m[i].length){
	    	m[i][j] = Library.random(m.length*2);
	        j = j + 1;
	    }
	    i = i + 1;
	}
    }

    void printMatrix(int[][] m) {
	int i, j;
	i = 0;
	while(i < m.length) {
	    j = 0;
	    while(j< m[i].length){
	        Library.printi(m[i][j]);
	        Library.print(" ");
	        j = j + 1;
	    }
	    Library.print("\n");
	    i = i + 1;
	}
	Library.print("\n");
    }

    void main(string[] args) {
	int m, n, p;
	int i;

	if (args.length != 3) {
	    Library.println("Invalid number of parameters.");
	    Library.exit(1);
	}

	m = Library.stoi(args[0], 0);
	n = Library.stoi(args[1], 0);
	p = Library.stoi(args[2], 0);
	if(m < 1){
	    Library.println("Invalid value for parameter `m'");
	    Library.exit(1);
	}
	if(n < 1){
	    Library.println("Invalid value for parameter `n'");
	    Library.exit(1);
	}
	if(p < 1){
	    Library.println("Invalid value for parameter `p'");
	    Library.exit(1);
	}

	a = new int[][m];
	i = 0;
	while(i < m){
	    a[i] = new int[n];
	    i = i + 1;
	}
	
	b = new int[][n];
	i = 0;
	while(i < n){
	    b[i] = new int[p];
	    i = i + 1;
	}
	
	c = new int[][m];
	i = 0;
	while(i < m){
	    c[i] = new int[p];
	    i = i + 1;
	}

	initMatrix(a);
	Library.println("Matrix A:");
	printMatrix(a);
	initMatrix(b);
	Library.println("Matrix B:");
	printMatrix(b);
	multiply();
	Library.println("Matrix C = A x B:");
	printMatrix(c);
    }
}