Problem 1 ->
Write a class called BubbleSort with a method bubbleSort which bubble
sorts a sequence of Student objects as follows:
generate a random sequence of Student objects with hall number
between 1 and 7 (Note: nextInt(n) in class Random generates
a random integer betwee 0 and n-1 (not n)), and a roll number between 0
and 999 (so the type of roll number is int and not String).
Note that roll number must be unique, so no two students can have the same
roll number. Now sort the sequence such that the ordering is by increasing
hall number and for the same hall number by increasing roll number. Generate
enough students so that there are at least a few in each hall. You cannot
use an extra array while sorting.
[10]
Solution ->
import java.util.Random;
class BubbleSort{
BubbleSort(){
}
/*Bubble sorts a given StudentList object s.t the Student elements within it
are in ascending order of hall-no and roll no*/
public StudentList bubbleSort(StudentList sl){
int nitems;
Student sj, sj1;
nitems = sl.getCount();
if ( nitems > 0 ){
for(int i = nitems-1; i > 0; i-- ){
for(int j = 0; j < i; j++){
sj = sl.getithStudent(j);
sj1 = sl.getithStudent(j+1);
if ( sj.isGreaterthan(sj1) ){
swap(sl, j, j+1);
}
}
}
return sl;
}
else{
System.out.println("Error in BubbleSort: StudentList does not have element(s)");
return null;
}
}
//Swap Students in positions i and j
private void swap(StudentList sl, int i, int j){
Student stemp;
stemp = sl.getithStudent(i);
sl.setithStudent(sl.getithStudent(j) , i);
sl.setithStudent(stemp , j);
}
}
class StudentList{
static final int MAX_NO_OF_STUDENTS = 1000;
private Student std[] = new Student[MAX_NO_OF_STUDENTS];
private int nos = 0;
StudentList(){
}
StudentList(Student s){
std[nos++] = s;
}
public int getCount(){
return nos;
}
public Student getithStudent(int i){
if ( i < nos ){
return std[i];
}
else{
System.out.println("Error in StudentList: Currently, there are only " + nos +" students in the StudentList");
return null;
}
}
public boolean setithStudent(Student s, int i){
if ( i < 0 || i > nos-1 ){
System.out.println("Error in StudentList: Currently, there are only " + nos +" students in the StudentList");
return false;
}
else{
std[i] = s;
return true;
}
}
public boolean add(Student s){
if ( nos < MAX_NO_OF_STUDENTS ){
if ( isDupStudent(s) ) return false;
std[nos++] = s;
return true;
}
else{
System.out.println("Error in StudentList: List full. Cannot add more students");
return false;
}
}
public void remove(Student s){
if ( nos > 0 ){
for(int i = 0; i < nos; i++){
if ( s.equals(std[i]) ){
for(int j = i + 1;j < nos;j++)
std[j-1] = std[j];
}
}
}
else
System.out.println("Error in StudentList: No students to remove");
}
//Checks whether a student with same roll no exists
public boolean isDupStudent(Student s){
for(int i = 0;i < nos;i++)
if ( s.isEqual(std[i]) ) return true;
return false;
}
public void print(){
if ( nos > 0 ){
System.out.println("Hall No\t\tRoll No");
for(int i = 0;i < nos;i++){
System.out.print(std[i].getHallno() + "\t\t");
System.out.println(std[i].getRollno());
}
}
else
System.out.println("Error in StudentList: No elements to print");
}
}
class Student{
static final int MAX_ROLL_NO = 1000;
static final int MAX_HALL_NO = 7;
private String name;
private int rollno;
private int hallno;
private String roomno;
private String branch;
private int semester;
Student(){
Random r = new Random();
rollno = r.nextInt(MAX_ROLL_NO);
hallno = r.nextInt(MAX_HALL_NO) + 1;
}
Student(String name){
Random r = new Random();
this.name = name;
this.rollno = r.nextInt(MAX_ROLL_NO);
this.hallno = r.nextInt(MAX_HALL_NO) + 1;
}
Student(String name, String roomno, String branch, int semester){
Random r = new Random();
this.name = name;
this.rollno = r.nextInt(MAX_ROLL_NO);
this.hallno = r.nextInt(MAX_HALL_NO) + 1;
this.roomno = roomno;
this.branch = branch;
this.semester = semester;
}
Student(String name, int rollno, int hallno, String roomno, String branch, int semester){
this.name = name;
this.rollno = rollno;
this.hallno = hallno;
this.roomno = roomno;
this.branch = branch;
this.semester = semester;
}
Student(Student s){
name = s.getName();
rollno = s.getRollno();
hallno = s.getHallno();
roomno = s.getRoomno();
branch = s.getBranch();
semester = s.getSemester();
}
public String getName(){
return name ;
}
public int getRollno(){
return rollno;
}
public int getHallno(){
return hallno;
}
public String getRoomno(){
return roomno;
}
public String getBranch(){
return branch;
}
public int getSemester(){
return semester;
}
public boolean isEqual(Student s){
if ( this.rollno == s.rollno )
return true;
else
return false;
}
public boolean isLessthan(Student s){
int shn = s.getHallno();
if ( (hallno < shn) || ((hallno == shn) && (rollno < shn)) )
return true;
else
return false;
}
public boolean isGreaterthan(Student s){
int shn = s.getHallno();
int srn = s.getRollno();
if ( (hallno > shn) || ((hallno == shn) && (rollno > srn)) )
return true;
else
return false;
}
}
public class BS{
public static void main(String args[]){
StudentList slist = new StudentList();
BubbleSort bs = new BubbleSort();
for(int i = 0; i < 600; i++){
while ( !slist.add(new Student("Dummy Name")) );
}
if ( (slist = bs.bubbleSort(slist)) != null )
slist.print();
}
}
Problem 2 ->
We wish to generate the following sequences from the digits 1, 2
and 3, that consist of pairs of different adjoining non empty sequences.
So some allowed or good sequences are:
1
12
1213
12312
3212321
while here are some disallowed or bad sequences:
11
1212
32132132
etc.
The problem is: given that there is at least one good sequence of size
100 digits write a program which will generate the list of all good sequences
in increasing/alphabetical order up to and including the first sequence
of size 100. The ordering is the obvious one where 1<2<3 and the
sequences are ordered by length - so if we treat any particular sequence
as a number then it is by numerical magnitude.
Hints: 1) Stepwise refinement. 2) A bad sequence cannot be extended
to a good one but a good sequence is of size one or obtained
by extending a good sequence by a single digit.
[15]
Solution ->
class GoodSequence{
static final int MAX_DIGIT = 3;
private StringQueue sq = new StringQueue();
GoodSequence(){
}
//Intialize Q to contain digits 1,2,3...Here, only digits 1,2 and 3 are used
private void initQ(int digits){
for(int i = 1;i <= digits;i++){
Integer ival = new Integer(i);
sq.add(ival.toString());
}
}
/*Generate all good sequences of length <= seqlen in ascending order.
Uses StringQueue to hold good sequences of length k+1 while operating
on sequences of length k.*/
public void genGoodseq(int seqlen){
String tempstr;
initQ(MAX_DIGIT);
while (!sq.isEmpty()){
//Remove next good sequence from head of queue
String gstr = sq.remove();
/*Step-wise refinement. Add a digit and check whether new sequence
is good. If it is good, add it to rear of queue for later processing*/
for(int i = 1; i <= MAX_DIGIT; i++){
tempstr = new String(gstr);
Integer ival = new Integer(i);
gstr += ival.toString();
if ( isGoodseq(gstr) ){
//Terminating condition
if ( gstr.length() > seqlen ) return;
System.out.println(gstr);
sq.add(gstr);
}
gstr = tempstr;
}
}
}
/*Check whether a given sequence is good. Given a sequence of length k, the first
k-1 digits form a good sequence. If given sequence is bad, last digit has to
be involved in one of the repeating pairs. Hence suffices to check only for
sub-sequences involving last digit*/
public boolean isGoodseq(String s){
String s1, s2;
int slen = s.length();
if (slen == 1) return true;
for(int i = 1;i <= slen/2;i++){
s1 = s.substring(slen-i,slen);
s2 = s.substring(slen-2*i,slen-i);
if ( s1.equals(s2) )
return false;
}
return true;
}
}
class StringQueue{
static final int MAX_ELEMENTS = 1000;
private String q[] = new String[MAX_ELEMENTS];
private int noe;
StringQueue(){
noe = 0;
}
//Check whether queue is empty
public boolean isEmpty(){
if ( noe <= 0 )
return true;
else
return false;
}
//Add a new string to rear of queue
public void add(String s){
String sdup = new String(s);
if ( noe < MAX_ELEMENTS )
q[noe++] = sdup;
else
System.out.println("Error in StringQueue: Queue is full");
}
//Remove and return element from front of queue
public String remove(){
String result=null;
if ( noe > 0 ){
result = q[0];
//Shifting remaining elements back by one postion
for(int i = 1;i < noe;i++)
q[i-1] = q[i];
noe--;
}
else{
System.out.println("Error in StringQueue: Queue is empty");
}
return result;
}
//Print queue contents
public void print(){
if (noe > 0 && noe < MAX_ELEMENTS){
for(int i = 0; i < noe; i++){
System.out.print(q[i] + "<-");
}
System.out.println("");
}
else
System.out.println("Error in StringQueue: No elements to print");
}
}
public class Sequence{
/*There is a combinatorial explosion in trying to print for sequences of length
<= 100. Hence printing sequences of length <= 10 only.*/
static final int MAX_SEQ_LEN = 10;
public static void main(String args[]){
GoodSequence gs = new GoodSequence();
System.out.println("Good Sequences goto console, bad sequences go nowhere");
gs.genGoodseq(MAX_SEQ_LEN);
}
}