Sunday 18 November 2012

Entity Relationship Diagram for managing University PhD students and their research projects


Question Source

Book: 
DATABASE MANAGEMENT SYSTEMS

Author:
Raghu Ramakrishnan
Johannes Gehrke

Scenario


Consider the following information about a university database:
  • Professors have an SSN, a name, an age, a rank, and a research specialty.
  • Projects have a project number, a sponsor name (e.g., NSF), a starting date, an ending date, and a budget.
  • Graduate students have an SSN, a name, an age, and a degree program (e.g., M.S. or Ph.D.).
  • Each project is managed by one professor (known as the project’s principal investigator).
  • Each project is worked on by one or more professors (known as the project’s co-investigators).
  • Professors can manage and/or work on multiple projects.
  • Each project is worked on by one or more graduate students (known as the project’s research assistants).
  • When graduate students work on a project, a professor must supervise their work on the project. Graduate students can work on multiple projects, in which case they will have a (potentially different) supervisor for each one.
  • Departments have a department number, a department name, and a main office.
  • Departments have a professor (known as the chairman) who runs the department.
  • Professors work in one or more departments, and for each department that they work in, a time percentage is associated with their job.
  • Graduate students have one major department in which they are working on their degree.
  • Each graduate student has another, more senior graduate student (known as a student advisor) who advises him or her on what courses to take.

Design and draw an ER diagram that captures the information about the university. Use only the basic ER model here; that is, entities, relationships, and attributes. Be sure to indicate any key and participation constraints.

ERD

Entity Relationship Diagram for managing University PhD students & their research projects

Entity Relationship Diagram for Airport Management


Question Source

Book: 
DATABASE MANAGEMENT SYSTEMS

Author:
Raghu Ramakrishnan
Johannes Gehrke

Scenario

Computer Sciences Department frequent fliers have been complaining to Dane County Airport officials about the poor organization at the airport. As a result, the officials decided that all information related to the airport should be organized using a DBMS, and you have been hired to design the database. Your first task is to organize the information about all the airplanes stationed and maintained at the airport. The relevant information is as follows:
  • Every airplane has a registration number, and each airplane is of a specific model.
  • The airport accommodates a number of airplane models, and each model is identified by a model number (e.g., DC-10) and has a capacity and a weight.
  • A number of technicians work at the airport. You need to store the name, SSN, address, phone number, and salary of each technician.
  • Each technician is an expert on one or more plane model(s), and his or her expertise may overlap with that of other technicians. This information about technicians must also be recorded.
  • Traffic controllers must have an annual medical examination. For each traffic controller, you must store the date of the most recent exam.
  • All airport employees (including technicians) belong to a union. You must store the union membership number of each employee. You can assume that each employee is uniquely identified by a social security number.
  • The airport has a number of tests that are used periodically to ensure that airplanes are still airworthy. Each test has a Federal Aviation Administration (FAA) test number, a name, and a maximum possible score.
  • The FAA requires the airport to keep track of each time a given airplane is tested by a given technician using a given test. For each testing event, the information needed is the date, the number of hours the technician spent doing the test, and the score the airplane received on the test.

Draw an ER diagram for the airport database. Be sure to indicate the various attributes of each entity and relationship set; also specify the key and participation constraints for each relationship set.

ERD

Entity Relationship Diagram for Airport Management (Brief)

Entity Relationship Diagram for Medical Scenario


Question Source

Book: 
DATABASE MANAGEMENT SYSTEMS

Author:
Raghu Ramakrishnan
Johannes Gehrke

Scenario


The Prescriptions-R-X chain of pharmacies has offered to give you a free lifetime supply of medicine if you design its database. Given the rising cost of health care, you agree. Here’s the information that you gather:
Patients are identified by an SSN, and their names, addresses, and ages must be recorded.
  • Doctors are identified by an SSN. For each doctor, the name, specialty, and years of experience must be recorded.
  • Each pharmaceutical company is identified by name and has a phone number.
  • For each drug, the trade name and formula must be recorded. Each drug is sold by a given pharmaceutical company, and the trade name identifies a drug uniquely from among the products of that company. If a pharmaceutical company is deleted, you need not keep track of its products any longer.
  • Each pharmacy has a name, address, and phone number.
  • Every patient has a primary physician. Every doctor has at least one patient.
  • Each pharmacy sells several drugs and has a price for each. A drug could be sold at several pharmacies, and the price could vary from one pharmacy to another.
  • Doctors prescribe drugs for patients. A doctor could prescribe one or more drugs for several patients, and a patient could obtain prescriptions from several doctors.
  • Each prescription has a date and a quantity associated with it. You can assume that, if a doctor prescribes the same drug for the same patient more than once, only the last such prescription needs to be stored.
  • Pharmaceutical companies have long-term contracts with pharmacies. A pharmaceutical company can contract with several pharmacies, and a pharmacy can contract with several pharmaceutical companies. For each contract, you have to store a start date, an end date, and the text of the contract.
  • Pharmacies appoint a supervisor for each contract. There must always be a supervisor for each contract, but the contract supervisor can change over the lifetime of the contract.

 Draw an ER diagram that captures the preceding information. Identify any constraints not captured by the ER diagram.

ERD

Entity Relationship Diagram for Hospital and Pharma Company Management

Entity Relationship Diagram for Music Company


Question Source

Book: 
DATABASE MANAGEMENT SYSTEMS

Author:
Raghu Ramakrishnan
Johannes Gehrke

Scenario

Notown Records has decided to store information about musicians who perform on its albums (as well as other company data) in a database. The company has wisely chosen to hire you as a database designer (at your usual consulting fee of $2500/day).
  • Each musician that records at Notown has an SSN, a name, an address, and a phone number. Poorly paid musicians often share the same address, and no address has more than one phone.
  • Each instrument used in songs recorded at Notown has a unique identification number, a name (e.g., guitar, synthesizer, flute) and a musical key (e.g., C, B-flat, E-flat).
  • Each album recorded on the Notown label has a unique identification number, a title, a copyright date, a format (e.g., CD or MC), and an album identifier.
  • Each song recorded at Notown has a title and an author.
  • Each musician may play several instruments, and a given instrument may be played by several musicians.
  • Each album has a number of songs on it, but no song may appear on more than one album.
  • Each song is performed by one or more musicians, and a musician may perform a number of songs.
  • Each album has exactly one musician who acts as its producer. A musician may produce several albums, of course.
Design a conceptual schema for Notown and draw an ER diagram for your schema. The preceding information describes the situation that the Notown database must model. Be sure to indicate all key and cardinality constraints and any assumptions you make. Identify any constraints you are unable to capture in the ER diagram and briefly explain why you could not express them. 

ERD

Entity Relationship Diagram for Music Company Database

Sunday 23 September 2012

Chat Application in Java

This program was developed to demonstrate the functioning of a multi-threaded server in Java. The application consist of two parts.
  1. A muti-threaded server
  2. A client User Agent
There will be one instance running of the Server program and there can be multiple instances running of the client program, communicating with each other through the server program.

Here is the code.

ChatServer.java

import java.net.*;
import java.io.*;

class ChatServer
{
 static ServerSocket ss;
 static Socket cs;
 static ChatClients[] ct = new ChatClients[10]; 
 
 
 public static void main(String[] args)
 {
  try
  {
   int port = Integer.parseInt(args[0]);
   ss = new ServerSocket(port);

   while(true)
   {
    cs = ss.accept();
  
    for(int i=0; i<ct.length; i++)
    {
     if(ct[i]==null)
     {
      ct[i] = new ChatClients(cs, ct);
      System.out.println("A new client has been connected. Client's ID is : " + i);
      break;
     }
    }

   }  
   
  }
  catch(Exception e)
  {
   e.printStackTrace();
  }
 }  
}

class ChatClients implements Runnable
{

 Socket cs = null;
 DataInputStream is = null;
 PrintStream os = null;
 ChatClients[] ct;
 
 ChatClients(Socket s, ChatClients[] t)
 {
  cs = s;
  ct=t;
  new Thread(this).start();
 }

 public void run()
 {
  try
  {
   is = new DataInputStream(cs.getInputStream());
   os = new PrintStream(cs.getOutputStream());

   os.println("Enter your name : ");
   String name = is.readLine();

   os.println("Hello "+name+" to our chat room.\nTo leave enter /quit in a new line."); 
   
   //Send everyone I have joined

   for(int i=0; i<ct.length; i++)
   {
    if(ct[i]!=null && ct[i]!=this)
     ct[i].os.println(name + " has entered the chat room.");
   }

   //Send msgs
   while(true)
   {
    String msg = is.readLine();

    if(msg.startsWith("/quit"))
     break;

    for(int i=0; i<ct.length; i++)
    {
    if(ct[i]!=null && ct[i]!=this)
     ct[i].os.println("<" + name + "> " + msg);
    }
   }

   //Send everyone I am leaving
   for(int i=0; i<ct.length; i++)
   {
    if(ct[i]!=null && ct[i]!=this)
     ct[i].os.println(name + " is leaving the chat room.");
   }


   //close connection
   os.println("**Bye");

   for(int i=0; i<ct.length; i++)
   {
    if(ct[i]==this)
    {
     ct[i] = null;
     System.out.println("Client ID " + i + " has left the chat room");
     break;
     
     
    }
   }

   is.close();
   os.close();
   cs.close();

    
  }
  catch(Exception e)
  {
   e.printStackTrace();
  }
 }
}

ClientApp.java

import java.io.*;
import java.net.*;

class ClientApp implements Runnable
{

 static Socket cs = null;
 static PrintStream os = null;
 static DataInputStream is = null;
 static BufferedReader br = null;
 static boolean closed = true;  

 public static void main(String[] args)
 {
  try
  {
   int port = Integer.parseInt(args[1]);

   cs = new Socket(args[0], port);

   is = new DataInputStream(cs.getInputStream() );
   os = new PrintStream(cs.getOutputStream());
   br = new BufferedReader(new InputStreamReader(System.in));

   closed=false;

   //Now start thread for readin server responses
   new Thread(new ClientApp()).start();


   //you can write till the connection is not closed from servers end

   while(!closed)
   {
    os.println(br.readLine());    
   }

   is.close();
   os.close();
   cs.close();   
  }
  catch(Exception e)
  {
   e.printStackTrace();
  }  
 }

 public void run()  //this is for keep on reading response from server
 {
  try
  {
   String responseMsg = null;

   while ((responseMsg = is.readLine())!=null)
   {
    System.out.println(responseMsg);
 
    if(responseMsg.startsWith("**Bye"))
     break;    
   }

   closed = true;
  }
  catch(Exception e)
  {
   e.printStackTrace();
  }
 }
}

How to execute ?

  1. Copy the server code and save the file with name ChatServer.java
  2. Copy the client application code and save the file with name ClientApp.java
  3. Compile both the files >javac ChatServer.java and  >javac ClientApp.java 
  4. Start the server program and pass it a command line argument, a number specifying the port on which server process will execute. >java ChatServer 1111 , here 1111 is the port number.
  5. Start a client program and pass command line arguments the URL to which you wish to connect (here localhost) and the port number on which the server process in running (in our case 1111) >java ClientApp localhost 1111
  6. Specify your name and join the chat room.
  7. Use step 5 & 6 to start many more instances (users) of the client application.

Chat Application Snapshot

Wednesday 11 July 2012

C# Paper Solution for TYIT (Programs)

October 2004

1. Given a list of marks ranging from 0 to 100. Write a C# program to compute and print number of students who have obtained marks
1)in the range 81 to 100
2)in the range 61 to 80
3)in the range 41 to 60
4)in the range 0 to 40.

using System;

class Demo
{
 public static void Main(string[] args)
 {
  int dis=0, I=0, II=0, fail=0;

  for(int x=0; x<args.Length; x++)
   if (int.Parse(args[x]) > 80)
    ++dis;
   else if (int.Parse(args[x]) > 60 )
    ++I;
   else if (int.Parse(args[x]) > 40 )
    ++II;
   else 
    ++fail;
  
  Console.WriteLine ("\nNumber of students in the range 81 to 100 - " + dis);
  Console.WriteLine ("\nNumber of students in the range 61 to 80 - " + I);
  Console.WriteLine ("\nNumber of students in the range 41 to 60 - " + II);
  Console.WriteLine ("\nNumber of students in the range 0 to 40 - " + fail);

 }
}

Output (Passing Arguments through command line)

2. Write a method Prime that returns true if argument is a prime number and returns false otherwise?

using System;

public class Demo
{
 public static bool Prime(int num)
 {
  for (int i=2; i<num; i++)
   if (num % i == 0)
    return false;
  return true; 
 }

 public static void Main()
 {
  Console.WriteLine ("Enter a number - ");
  int x = int.Parse (Console.ReadLine());
  if (Prime(x))
   Console.WriteLine (x + " is a prime number.");
  else
   Console.WriteLine (x + " is not a prime number.");
 }
}



3. Define an interface power that contains three methods viz.
i) to calculate the square of the given number
ii) to calculate cube of the given number
iii) to calculate power of 'm' raised to 'n'
Define a class demo which implements this interface.
Write a main method to check your code?

using System;

interface Power
{
 int square (int m);
 int cube  (int m);
 int pwr (int m, int n);
}

class Demo : Power
{
 public int square (int m)
 {
  return m*m;
 }

 public int cube (int m)
 {
  return m*m*m;
 }

 public int pwr (int m, int n)
 {
  int r=m;

  if (n!=0)
  {
   for (int i=1; i<n; i++)
    m*=r;
   return m;
  }
  else 
   return 0;
 }
}

class Test
{ 
public static void Main()
 {
  Console.Write ("Enter a number - ");
  int num = int.Parse(Console.ReadLine());

  Console.Write ("Enter the power value - ");
  int x = int.Parse(Console.ReadLine());

  Demo obj = new Demo();
  Console.WriteLine("Square of " + num + " is - " +  obj.square(num));
  Console.WriteLine("Cube of " + num + " is - " +  obj.cube(num));
  Console.WriteLine(num + "^" + x + " is - " +  obj.pwr(num,x));
 }
}

4. Write a program that will take 10 integer numbers from command line and then print all the numbers divisible by 5 and 7. Also print sum of all those numbers?

using System;

class Demo
{
 public static void Main(String[] arg)
 {
  int sum = 0;
 
  Console.WriteLine ("\nNumbers divisible by 5 or 7 -");
  for (int i=0; i<arg.Length; i++)
   if ((int.Parse(arg[i]) % 5 == 0) || (int.Parse(arg[i]) % 7 == 0))
   {
    Console.WriteLine (arg[i]);
    sum+=int.Parse(arg[i]);
   }
  Console.WriteLine ("\n\nSum = " + sum); 

 }
}


5. Write a Program that will read the value of 'x' and evaluate the value of 'y' as follows.
y=1 for x>0
y=0 for x=0
y=-1 for x<0
using else if statement?

using System;

class Demo
{
	public static void Main()
	{
		int x;
	
		Console.Write ("\nEnter the value of x -");
		x = int.Parse(Console.ReadLine());
		
		if (x>0)
			Console.WriteLine("y = 1");
		else if (x==0)
			Console.WriteLine("y = 0");
		else if (x<0)
			Console.WriteLine("y = -1");

	}
}


6. Write a program to convert the given temperature in Fahrenheit to Celsius.
[Formula: C = (F-32)/1.8]

using System;

class Demo
{

	public static void Main()
	{
		Console.Write("Enter the Fahrenheit Value - ");
		double F = double.Parse(Console.ReadLine());

		double C = (F-32)/1.8;

		Console.WriteLine("Celsius - " + C);
	}
}


7. Write a class Date that includes data member day, month and year and methods that could implement the following tasks.
i)Read a date from Keyboard
ii)DisplayDate a Date
iii)Increment a date by one day
iv)Compare two dates to see which is greater.

using System;

class Date
{
	private int day;
	private int month;
	private int year;

	public void ReadDate()
	{
		Console.WriteLine (" *** Enter the Date ***");
		Console.Write("Day - ");
		day = int.Parse(Console.ReadLine());
		Console.Write("Month - ");
		month = int.Parse(Console.ReadLine());
		Console.Write("Year - ");
		year = int.Parse(Console.ReadLine());
	}

	public void DisplayDate()
	{
		Console.WriteLine(day + "-" + month + "-" + year);
	}

	public static void Compare(Date d1, Date d2)
	{
		if (d1.year>d2.year)
		{
			Console.WriteLine("Greater Date is - "); 
			d2.DisplayDate();
		}
		else if (d1.year==d2.year)
		{
			if (d1.month>d2.month)
			{
				Console.WriteLine("Greater Date is - ");
				d2.DisplayDate();	
			}
			else if (d1.month == d2.month)
			{
				if (d1.day>d2.day)
				{
					Console.WriteLine("Greater Date is - ");
					d2.DisplayDate();	
				}
				else if (d1.day == d2.day)
					Console.WriteLine("Both the dates are equal.");
				else
				{
					Console.WriteLine("Greater Date is - ");
					d1.DisplayDate();	
				}
			}
			else
			{
				Console.WriteLine("Greater Date is - ");
				d1.DisplayDate();
			}
		}
		else
		{
			Console.WriteLine("Greater Date is - " );
			d1.DisplayDate();
		}
	}

	public static void Incr(Date d1)
	{
		d1.day++;

		if (d1.day==29)
		{
			if (d1.month==2)
			{
				if (d1.year%4 != 0 && d1.year%100 !=0)
				{
					d1.day=1;
					d1.month++;
				}
			}
		
		}
		else if (d1.day==30)
		{
			if (d1.month==2)
			{
				if (d1.year%4 == 0 && d1.year%100 ==0) 
				{
					d1.day=1;
					d1.month++;
				}
			}
		}
		else if (d1.day==31)
		{
			if(d1.month==2 || d1.month==4 || d1.month==6 || d1.month==9 || d1.month==11)
			{
					d1.day=1;
					d1.month++;
			}
		}

		else if (d1.day==32)
		{	
			d1.day=1;
			d1.month++;
		
			if(d1.month==13)
			{
				d1.month=1;
				d1.year++;
			}	
		}
	}
}

class Test
{
	public static void Main()
	{
		Date d1 = new Date();
		Console.WriteLine("Enter 1st Date - \n");
		d1.ReadDate();
		d1.DisplayDate();

		Date d2 = new Date();
		Console.WriteLine("\n\nEnter 2nd Date - \n");
		d2.ReadDate();
		d2.DisplayDate();

		Console.WriteLine ("\nResult - \n");
		Date.Compare(d1,d2);

		Console.Write("\n\nIncrementing 1st date by 1 day - ");
		Date.Incr(d1);
		d1.DisplayDate();		

		Console.Write("\n\nIncrementing 2nd date by 1 day - ");
		Date.Incr(d2);
		d2.DisplayDate();		
	}
}

April 2005

8. Write a program that prints the following format.

#####
 ####
  ###
   ##
    #


using System;

class Style
{
	public static void Main()
	{
		for(int i=0; i<5; i++)
		{
			for(int s=0; s<i;s++)
			{
				Console.Write(" ");
			}
			
			for(int j=5; j>i; j--)
			{
				Console.Write("#");
			}
			Console.WriteLine();
		}
	}
}

9. Write a program to convert the temperature in Fahrenheit (starting from 98.5 to 102 in steps of 0.1) to Celsius using the formula C = (F-32)/1.8 and display the values in tabular form?

using System;

class Style
{
	public static void Main()
	{
		Console.WriteLine("Fahrenheit ---- Celsius");

		for(double F=98.5; F<=102; F=F+0.1)
		{
			Console.WriteLine("{0:F1} -------- {1:F2}" , F, ((F-32)/1.8)); 
		}
	}
}

10. Write a program to print the following Floyd's triangle.
1
2 3
4 5 6
7 8 9 10
............
..............
79..............91


using System;

class Floyd
{
	public static void Main()
	{
		int c=1;
		for(int i = 0; i<14; i++)
		{
			for(int j=0; j<i; j++)
			{
				Console.Write(c+ " ");
				c++;
			}
			Console.WriteLine();
		}
			
	}
}


October 2005

11. Write a program to print the following output.
    1
   2 2
  3 3 3
 4 4 4 4
5 5 5 5 5 


using System;

class Demo
{
	public static void Main()
	{
		for(int i=1; i<=5; i++)
		{
			for(int s=5; s>i; s--) //loop for space
				Console.Write(" ");
			for(int j=1; j<=i; j++)
				Console.Write(i + " ");
			Console.WriteLine();
		}
		
	}
}

12. Develop a program that prompts the user to input name, door number, street, city and pincode and stores them in the address record designed as a structure and display them in appropriate manner.

using System;

struct Address
{
	public string name, door_number, street, city, pincode;
}

class Demo
{
	public static void Main()
	{
		Address adr;
		Console.WriteLine("### Enter your details ###\n");
		Console.Write("Name - ");
		adr.name = Console.ReadLine();
		Console.Write("Door Number - ");
		adr.door_number = Console.ReadLine();
		Console.Write("Street - ");
		adr.street = Console.ReadLine();
		Console.Write("City - ");
		adr.city = Console.ReadLine();
		Console.Write("Pincode - ");
		adr.pincode = Console.ReadLine();

		Console.WriteLine("\n\n### Your Address is ###\n");
		Console.WriteLine(adr.name);
		Console.WriteLine(adr.door_number +", " + adr.street + ", ");
		Console.WriteLine(adr.city + "-" + adr.pincode);
	}
}

13. Write a program to print the following Pascal's triangle.
Hint: If we denote the rows by i and the columns by j, then any element (except the boundary elements) in the triangle is given by P[ij] = P[i-1,j-1] + p[i-1,j]?
1
1 1
1 2 1
1 3 3  1
1 4 6  4  1
1 5 10 10 5 1


using System;

class Demo
{
	public static void Main()
	{
		int n, i, j, c; 

		Console.Write("Enter an integer bound > "); 
		n = Convert.ToInt32(Console.ReadLine()); 

		for (i = 0; i < n; i++) 
		{ 
			c = 1; 
			for (j = 0; j <= i; j++) 
			{ 
				Console.Write(c + " "); 
				c = (c * (i - j)) / (j + 1); 
			} 
			Console.WriteLine(); 
		} 
	}
}

14. Write a program that accepts two double type numbers from the user and display addition, subtraction, multiplication, division and modulous of those two numbers?

using System;

class Demo
{
	public static void Main()
	{
		double a,b;
		Console.Write("Enter num 1 - ");
		a = double.Parse(Console.ReadLine());
		Console.Write("Enter num 2 - ");
		b = double.Parse(Console.ReadLine());
		Console.WriteLine("\nAddition = {0:f2}", (a+b));
		Console.WriteLine("Subtraction = {0:f2}", (a-b));
		Console.WriteLine("Multiplication = {0:f2}", (a*b));
		Console.WriteLine("Division = {0:f2}", (a/b));
		Console.WriteLine("Modulous = {0:f2}", (a%b));
	}
}

15. Write a program to add and subtract two complex numbers using operator overloading.

using System;

class Complex
{
	private int rel;
	private int img;

	public Complex()
	{
		rel=0;
		img=0;
	}	

	public Complex(int r, int i)
	{
		rel = r;
		img = i;
	}

	public void show()
	{
		Console.WriteLine(rel + " + " + img + "i");
	}

	public static Complex operator + (Complex c1, Complex c2)
	{
		Complex c3 = new Complex();
		c3.rel = c1.rel + c2.rel;
		c3.img = c1.img + c2.img;
		return c3;
	}

	public static Complex operator - (Complex c1, Complex c2)
	{
		Complex c3 = new Complex();
		c3.rel = c1.rel - c2.rel;
		c3.img = c1.img - c2.img;
		return c3;
	}

}

class Demo
{
	public static void Main()
	{
		Complex c1 = new Complex(2,3);
		c1.show();

		Complex c2 = new Complex(4,4);
		c2.show();

		Complex c3 = c1 + c2;
		Console.WriteLine("-------------------------------");
		Console.Write("\nAddition (c1 + c2) = ");
		c3.show();

		c3 = c2 - c1;
		Console.Write("\nSubtraction (c2 - c1) = ");
		c3.show();
	}
}

April 2006


16. Create class named Double. This class contains three double numbers. Overload +,-,*, / operators so that they can be applied to the objects of class Double. Write a C# program to test it?

using System;
class Double
{
	double x, y, z;
	public Double()
	{
		x=0;
		y=0;
		z=0;
	}
	public Double(double a, double b, double c)
	{
		x=a;
		y=b;
		z=c;
	}
	public void show()
	{
		Console.WriteLine("x = {0:F2}", +x);
		Console.WriteLine("y = {0:F2}", +y);
		Console.WriteLine("x = {0:F2}", +z);
	}
	public static Double operator + (Double d1, Double d2)
	{
		Double d3 = new Double();
		d3.x = d1.x + d2.x;
		d3.y = d1.y + d2.y;
		d3.z = d1.z + d2.z;
		return d3;
	}
	public static Double operator - (Double d1, Double d2)
	{
		Double d3 = new Double();
		d3.x = d1.x - d2.x;
		d3.y = d1.y - d2.y;
		d3.z = d1.z - d2.z;
		return d3;
	}
	public static Double operator * (Double d1, Double d2)
	{
		Double d3 = new Double();
		d3.x = d1.x * d2.x;
		d3.y = d1.y * d2.y;
		d3.z = d1.z * d2.z;
		return d3;
	}
	public static Double operator / (Double d1, Double d2)
	{
		Double d3 = new Double();
		d3.x = d1.x / d2.x;
		d3.y = d1.y / d2.y;
		d3.z = d1.z / d2.z;
		return d3;
	}
}

class Demo
{
	public static void Main()
	{
		Double d1 = new Double(10.095,12.93,14.982);
		Double d2 = new Double(23.893,24.84,23.940);

		Console.WriteLine("d1 ##### ");
		d1.show();
		Console.WriteLine("\nd2 ##### ");
		d2.show();

		Double d3 = new Double();
		d3 = d1+d2;
		Console.WriteLine("\nd1+d2 ##### ");
		d3.show();

		d3 = d2-d1;
		Console.WriteLine("\nd2-d1 ##### ");
		d3.show();

		d3 = d2*d1;
		Console.WriteLine("\nd2*d1 ##### ");
		d3.show();

		d3 = d2/d1;
		Console.WriteLine("\nd2/d1 ##### ");
		d3.show();
	}
}

17. Write a void type method that takes two integer type value parameters and one integer type out parameter and returns the product of two parameters through the out parameter. Write a C# program to test it's working?

using System;

class Demo
{

	public static void Product(int a, int b, out int c)
	{
		c = a*b;
	}

	public static void Main()
	{
		int res;
		Product(10,20,out res);
		Console.WriteLine("10 * 20 = " +res);
	}
}

18. Create a class Example to hold one integer value. Include a constructor to display a message "Object is created." and a destructor to display a message "Object is destroyed." Write a C# program to demonstrate the creation and destruction of objects of example class?

using System;

class Example
{
	private int i;

	public Example()
	{
		i=0;
		Console.WriteLine("Object is created."); 
	}

	~Example()
	{
		Console.WriteLine("Object is destroyed."); 
	}
}

class Demo
{
	public static void Main()
	{
		Example e = new Example();
	}
}

19. Write your own Exception NumberNotInRange. Write a C# program that throws NumberNotInRange exception if number entered by user is not in the range 1 to 100?

using System;

class NumberNotInRange : Exception
{
	public NumberNotInRange()
	{
		Console.WriteLine("The number should be between 1 to 100.");
	}
}

class Demo
{
	public static void Main()
	{
		try
		{
			Console.Write("Enter a number - ");
			int i = int.Parse(Console.ReadLine());

			if(i<1 || i>100) throw new NumberNotInRange();
		}
		catch(Exception e)
		{
			Console.WriteLine(e);
		}
	}
}

October 2006

20. Write a program to print the following output.
*******
*** ***
**   **
*     *


using System;

class Demo
{
	public static void Main()
	{
		for(int a=0; a<7; a++)
			Console.Write("*");
		Console.WriteLine();
		for(int i=0; i<3; i++)
		{
			for(int j=3; j>i; j--)
			{
				Console.Write("*");
			}
			
			for(int s=0; s<=2*i; s++)
				Console.Write(" ");

			for(int k=3; k>i; k--)
				Console.Write("*");			
			Console.WriteLine();
		}
	}
}

21. Write a method Maximum() that takes an array as an input parameter and returns maximum and minimum values to Main(). Write a complete c# program to test the above method?

using System;

class Demo
{
	public static void Maximum(out int min, out int max, params int[] a)
	{
		Array.Sort(a);
		min = a[0];
		max = a[a.Length-1];
	}

	public static void Main()
	{
		int[] a = {10,22,23,14,5};

		int min, max;

		Maximum(out min, out max, a);

		Console.WriteLine("Minimum - " + min);
		Console.WriteLine("Maximum - " + max);
	}
}

22. Define a Time class containing following members.
-Two integer data members minutes and hours.
-Two overloaded constructors.
-One method to display the class data members.
One of the constructor takes two integer parameters to assign value to two data members and other constructor takes one integer parameter representing total number of minutes and converts it into hours and minutes. Write a complete program to verify the operation ofconstructor and the method?

using System;

class Time
{
	int mm, hh;

	public Time(int mins, int hrs)
	{
		mm = mins;
		hh = hrs;
	}

	public Time(int tmins)
	{
		mm = tmins%60;
		hh = tmins/60;
	}

	public void display()
	{
		Console.WriteLine ("The time is - " + hh + ":" + mm);
	}
}

public class Demo
{
	public static void Main()
	{
		Time t1 = new Time(44, 1);
		Time t2 = new Time(100);

		t1.display();
		t2.display();
	}
}

April 2007


23. Write a program that will read the name from the keyboard an display it on the screen. The program should throw an exception when the length of the name is more than 15 characters. Design your own exception?

using System;

class InvalidName : Exception
{
	public InvalidName()
	{
		Console.WriteLine("Invalid Name Length : The name should not be more than 15 characters in length.");
	}
	
}

class Demo
{
	public static void Main()
	{
		try
		{
			Console.WriteLine("Enter your name - ");
			string nm = Console.ReadLine();
			if(nm.Length>15) throw new InvalidName();

			Console.WriteLine("Your Name is - "+nm);
		}
		catch(Exception e)
		{
			Console.WriteLine(e);
		}
	}
}

24. Write a program to generate following triangle.
1
2 3 2
3 4 5 4 3
4 5 6 7 6 5 4
5 6 7 8 9 8 7 6 5


using System;

class Demo
{
	public static void Main()
	{
		int count;		

		for(int i=1; i<=5; i++)
		{
			count = i;
			for (int j=0; j=i ; k++)
			{
				Console.Write(count + " ");
				count --;
			}
				
			Console.WriteLine();
		}
	}
}

25. Write a method that computes the sum of digits of a given integer number. Write a program to test the above method?

using System;

class Number
{
	public int Sum(int num)
	{
		int n = num;
		int sum = 0;

		while(num>1)
		{
			n = num%10;
			num = num / 10;
			sum = sum + n;
		}

		return sum;
	}
}

class Demo
{
	public static void Main()
	{
		Number obj = new Number();

		Console.Write("Enter a number - ");

		int a = int.Parse(Console.ReadLine());
		Console.WriteLine("\n Sum of Digits is - " + obj.Sum(a));
	}
}

26. Given are two 1 dimensional arrays which are in sorted order. Write a program to merge them into a simple sorted array 'C' that contains every item from array 'A' and 'B' in ascending order?

using System;
class Demo
{
	public static void Main()
	{
		int[] A = {1,3,5,7,9};
		int[] B = {0,2,4,6};
		int[] C = new int[A.Length+B.Length];

		for(int i=0; i<A.Length; i++)
			C[i] = A[i];

		for(int i=A.Length, j=0; j<B.Length; i++, j++)
			C[i] = B[j];

		Console.WriteLine("\nElements of Array C Before Sorting - ");

		foreach(int a in C)
		{
			Console.Write(a + " ");
		}

		for(int i=0; i<C.Length; i++)
		{
			for(int j=0; j<C.Length; j++)
			{
				if(C[i]<C[j])
				{
					int temp = C[i];
					C[i] = C[j];
					C[j] = temp;	
				}
			}	
		}
		Console.WriteLine("\n\nElements of Array C After Sorting - ");
		foreach(int a in C)
		{
			Console.Write(a + " ");
		}
	}
}

27. Write a program to overload binary ‘*’ and unary ‘-‘ for the class having three integer data members.

using System;

class Dimension
{
	private int x, y, z;

	public Dimension(int x1, int y1, int z1)
	{
		x=x1;
		y=y1;
		z=z1;
	}

	public static Dimension operator * (Dimension d1,Dimension d2)
	{
		Dimension d3 = new Dimension(0,0,0);
		d3.x = d1.x * d2.x;
		d3.y = d1.y * d2.y;
		d3.z = d1.z * d2.z;
		return d3;
	}

	public static Dimension operator - (Dimension dim)
	{
		dim.x = -dim.x;
		dim.y = -dim.y;
		dim.z = -dim.z;
		return dim;
	}

	public void display()
	{
		Console.WriteLine ("x = " + x + ", y= " + y + ", z = " + z);
	}
}

public class Test
{
	public static void Main()
	{
		Dimension dim1 = new Dimension(1,2,3);
		Dimension dim2 = new Dimension(10,20,30);

		Console.WriteLine ("\nDimension dim1 - ");
		dim1.display();

		Console.WriteLine ("\nDimension dim2 - ");
		dim2.display();

		Dimension dim3 = dim1*dim2;

		Console.WriteLine ("\ndim1 * dim2 = ");
		dim3.display();

		Console.WriteLine ("\n-dim3 = ");
		dim3=-dim3;

		dim3.display();
	}
}

28. Create a class named Integer to hold two integer values. Design a method Swap that could take two Integer objects as parameters and swap their contents. Write a Main program to implement class Integer and method Swap?

using System;

class Integer
{
	int x, y;
	
	public Integer()
	{
		x=0;
		y=0;
	}
	public Integer(int a, int b)
	{
		x=a;
		y=b;
	}

	public static void Swap(ref Integer I1, ref Integer I2)
	{
		Integer temp = new Integer();

		temp.x = I1.x;
		I1.x = I2.x;
		I2.x = temp.x;

		temp.y = I1.y;
		I1.y = I2.y;
		I2.y = temp.y;
	}

	public void show()
	{
		Console.WriteLine("x = " + x);
		Console.WriteLine("y = " + y);
	}
}

class Demo
{
	public static void Main()
	{
		Integer I1 = new Integer(2,4);
		Integer I2 = new Integer(1,3);

		Console.WriteLine("\n ----- Before Swapping ----- ");

		Console.WriteLine("I1 - ");
		I1.show();

		Console.WriteLine("\nI2 - ");
		I2.show();

		Integer.Swap(ref I1, ref I2);

		Console.WriteLine("\n ----- After Swapping ----- ");

		Console.WriteLine("I1 - ");
		I1.show();

		Console.WriteLine("\nI2 - ");
		I2.show();
	}
}

29. Define a exception called "NoMatchException" that is thrown when a string is not equal to "TYBSCIT". Write a program tht uses this exception?

using System;

class NoMatchException : Exception
{
	public NoMatchException()
	{
		Console.WriteLine("Error : String not matched.");
	}
}

class Demo
{
	public static void Main()
	{
		try
		{
			Console.Write("Enter a message - ");
			string msg = Console.ReadLine();

			if (msg!="TYBSCIT") throw new NoMatchException();
		}
		catch (Exception e)
		{
			Console.WriteLine(e);
		}
	}
}

April 2008


30. Write a program to create a class called ‘Point’ that has two integer member variables to represent the x and y coordinates of a point. Include as operator method for unary operator ‘++’ to increment a Point object?

using System;

class Point
{
	private int x;
	private int y;

	public Point (int x1, int y1)
	{
		x=x1;
		y=y1;
	}

	public void show()
	{
		Console.WriteLine ("x = " + x + " ,y = " + y);
	}

	public static Point operator ++ (Point p)
	{
		p.x = ++p.x;
		p.y = ++p.y;
		return p;
	}
}

class Test
{
	public static void Main()
	{
		Point pt = new Point (3,6);
		Console.Write("The co-ordinates of point pt is ");
		pt.show();
		pt++;
		Console.Write("The co-ordinates of point pt after pt++ is ");
		pt.show();		
	}
}


31. A bank charges commission on the issue of Demand Drafts at the following rates.
DD Amount        Commission
Upto Rs. 500         Rs. 10
Rs. 501 to Rs. 1000         Rs. 15
Rs. 1001 to Rs. 5000         Rs. 25
Rs. 5001 to Rs. 10000 Rs. 30
Above Rs. 10000 Rs. 3 for every Rs. 1000
Write a program which accepts DD amount from the terminal and calculate the commission payable and print it along with the DD amount?

using System;

class Bank
{
	public static void Main()
	{
		Console.Write("Enter DD Amount - ");
		double amt = double.Parse(Console.ReadLine());

		double comm;

		if(amt<=500)		
			comm=10;
		else if(amt<=1000)
			comm=15;
		else if(amt<=5000)
			comm=25;
		else if(amt<=1000)
			comm=30;
		else
			comm = (amt/1000)*3;

		Console.WriteLine("\nAmount - {0:F2}", amt);
		Console.WriteLine("Commission - {0:F2}", comm);
		Console.WriteLine("Total - {0:F2}", (amt+comm));
	}

}

32. Write a program to create a class named AudioVideoRecord that store name of the movie, year of it's release and it's price. From this another class named SongRecord, which has a member variable for storing number of songs. Both of these classes should include appropriate constructors for the initialization of their data members and a display() method to display their data members. Test the above classes by creating object of SongRecord in Main() method?

using System;

class AudioVideoRecord
{
	private string name, year, price;

	public AudioVideoRecord(string nm, string yr, string pr)
	{
		name = nm;
		year = yr;
		price = pr;
	}	

	public void display()
	{
		Console.WriteLine ("Name - " + name);
		Console.WriteLine ("Year - " + year );
		Console.WriteLine ("Price - " + price );
	}
}

class SongRecord : AudioVideoRecord
{
	private string NumberOfSongs;
	
	public SongRecord(string nm, string yr, string pr, string nos) : base (nm,yr,pr)
	{
		NumberOfSongs = nos;
	}

	public new void display()
	{
		base.display();
		Console.WriteLine ("Number of Songs - " + NumberOfSongs );
	}

}

class Test
{
	public static void Main()
	{
		SongRecord obj = new SongRecord("MNIK", "2010", "150", "4");
		obj.display();
	}
}

33. Write a program that declares a interface with a method definition calculating the average of n numbers. Implement this interface in a class called Vehicleavg to calculate the average mileage of vehicles. Test the above class by calling average method inside Main()?

using System;

interface Avg
{
	int average(params int[] a);
}

class Vehicleavg : Avg
{
	public int average(params int[] a)
	{
		int sum=0;
		for (int i=0; i<a.Length; sum+=a[i], i++);
		return (sum/a.Length);
	}

}

class Test
{
	public static void Main()
	{
		Vehicleavg obj = new Vehicleavg();

		Console.WriteLine("Average is - " +obj.average(23,14,56,45,34,78,63,67,29,34));
	}
}

April 2009


34. Write a program that swaps any two rows of a 3 x 3 matrix. The matrix must be implemented as a two dimensional array. Accept row numbers of the rows to be swapped from the user?

using System;

class Matrix
{
	int[,] m;

	public Matrix()
	{
		m = new int[3,3];
	}

	public void store()
	{
		for (int i=0; i<3; i++)
			for (int j=0; j<3; j++)
				m[i,j] = int.Parse( Console.ReadLine());
	}

	public void show()
	{
		for (int i=0; i<3; i++)
		{
			for (int j=0; j<3; j++)
				Console.Write (m[i,j] + "   ");
			Console.WriteLine();
		}			
	}

	public void swap(int Row1, int Row2)
	{
		int[] x = new int[3];

		for (int j=0; j<3; j++)
		{
			x[j] = m[Row1,j];	
			m[Row1, j] = m[Row2, j];
			m[Row2, j] = x[j];
		}
	}
}

class Test
{
	public static void Main()
	{
		Matrix objM = new Matrix();
		Console.WriteLine ("Enter array elements - ");		
		objM.store();		
	
		Console.WriteLine ("The array is - ");
		objM.show();

		Console.Write("Enter rows to be swapped - ");
		int r1 = int.Parse(Console.ReadLine());
		int r2 = int.Parse(Console.ReadLine());
		objM.swap(--r1,--r2);

		Console.WriteLine("\nArray after swapping of rows - ");
		objM.show();
	}
	
}

35. Define a class Kilometer with a double data member distance and a constructor to initialize it. Include operator methods such that you will be able to perform the following operations.
If ((new Kilometer(22)*3)>new Kilometer(145))
      System.Console.WriteLine(“ 22 * 3 ”);
else
      System.Console.WriteLine(“ 145 “);?

using System;
class Kilometer
{
	double distance;
	public Kilometer(double d)
	{
		distance = d;
	}
	public static Kilometer operator * (Kilometer k, double d)
	{
		k.distance *= d;
		return k;
	}
	public static bool operator > (Kilometer k1, Kilometer k2)
	{
		if (k1.distance>k2.distance)
			return true;
		else
			return false;
	}
	public static bool operator < (Kilometer k1, Kilometer k2)
	{
		if (k1.distance<k2.distance)
			return true;
		else
			return false;
	}
}
class test
{
	public static void Main()
	{
		if ( (new Kilometer(22)*3) > new Kilometer(145) )
			Console.WriteLine ("22 * 3");
		else	
			Console.WriteLine (" 145 ");
	}
}

Tuesday 10 July 2012

Hashing : Introduction and Explanation

Why Indexing to Hashing?

The size of a record is very large as compared to the size of an index. In B Tree indexing, large number of indices can be accommodated on a frame. Each entry consists of Key Value + Address of the record where it is stored on disk. A B Tree node can be half full to completely full.

The structure of B Tree has to be stored somewhere on the disk. To fetch any record
  1. Perform disk access to load the root node into a frame
  2. Follow a path and traverse to particular node by recursive disk access to load a particular node
  3. Traverse through the key values to reach the desired key
  4. Read address of the record associated with the key
  5. Perform disk access for the particular address and load the record in the main memory
Hence extra space and efforts are required.

The solution is hashing. Hashing is a key-to-address mapping process. The objective is to get the address in a single calculation. Hashing gives transformation, the hash function: h (key) -> Address 
On hash function apply key values to get corresponding addresses i.e. the address of the block. Hashing saves
  • Multiple disk accesses that happens in B Tree
  • Space to store B Tree
The disk access will be only knowing the address and fetching the record.

Hashing is a way to reach a particular record in the file without scanning the entire file. A block (group of records) is usually fetched in primary memory where data is traversed sequentially. This is applicable to structures where records are stored continuously.

Prerequisite – There must be a well defined definite place where records are stored. The place is identified by address (may be a block number). The records need not to be sorted. Hashing provide us way to keep records in order (something other than sorting). The records will be divided into blocks b1, b2, b3 …

We are not going to access individual records. Block is the thing to be fetched.

h (key/5) = block number

Divide key by 5 and round to the ceiling. Therefore for records 1, 2, 3, 4, 5 the block number will be 1. E.g. 2/5 = (0.4) = 1. Hence block number 1 contains record with key value 2. In this organization within block arrangement is not important. The records can be in any order like 5, 2, 3, 1, and 4. Hence this technique is not so demanding. This hash technique pins record at particular file location.

h (key/x) = block [+ | -] k

Assumption- Key values are more or less in order.
Here we are adding or subtracting some value k from the block address.

Hash Functions:

Following are the ways to generate Hash Functions. Click on the link to learn about each method in detail.

  1. Direct Hashing
  2. Relative Addressing
  3. Division-Remainder Method
  4. Mid Square Method
  5. Folding

Collision:

Collision occurs when different key values collide on same address.
h (kwy1) -> Address 1
h (key2) -> Address1

E.g. Consider two keys -2 and 2 and h (k) = k2. As h (-2) = 4 and h (2) = 4 hence there is a collision. A bad choice of hash function will result in too many collisions. A bad hash function may result in triple collision as h (k1) -> A1, h (k2) - > A1 and h (k3) -> A1.

There is nothing as good or bad hash function at absolute point. The good or bad hash function depends on valid key values. If all the hash functions giving collisions then select the one with minimum collisions. If we get non-colliding block address then it is a good hash function.

Click here to learn about different methods to avoid collisions

With Special Thanks to,

Prof. [Ms] L. C. Nene
Lecturer,
MCA Department,
Veermata Jijabai Technological Institute,
Mumbai.

Hashing : How to Resolve Collisions


Collision occurs when
  1. Given key range is too large and a fraction of it will be used. There will be a group of valid key values close to each other, then a long invalid range, then a small group of valid keys and so on.
  2. Some kind of intelligence is provided in key (e.g. Roll Number) then entire range will never be used.

Resolving Collisions

Way 1 – Series of hash functions

If h1 (k1) = h2 (k2) then apply different hash function on key values as h2 (k1) and h2 (k2). Here they may not collide but this is not guaranteed. If again collision takes place then go for h3. Hence in this technique we need to have a series of hash function.

Way 2 – Linear Probing




Insertion
Apply hash function on key1; h (key1) -> A1 and so on. As key2 comes; h (key2) -> A1. 

Since there is a collision therefore move to next address space.
If empty as (in case of redundancy spread across) then 
        place the records with key2 
Else
	read the key value of the record stored; let the key value be keyX.
	Apply hash function on keyX.
	If h (keyX) -> A1 then
		Go to next address space and repeat the same procedure
	Else
		Go to general overflow area and place the record at the next free address space
	End If
End If

Theoretically this technique is good for insertion but searching sometimes gets very exhaustive.

Search
Let the key value of the record to be searched is keyX.

Apply hash function on keyX; h (keyX) -> AX
Go to address space AX.
If (Key of record stored at address space AX == KeyX) then
	Record found
Else
	Go to next address space.
	If (Key of record stored at this new address space == KeyX) then
		Record found
	Else
		Apply hash function on this new key value; KeyY.
		If (h (KeyY) == AX) then
			Go to next address space and repeat the same procedure
		Else
			Go to general overflow area
Traverse through the general overflow area, record by record, matching the key values, till the match is found or over flow area ends (this indicates record not found)
		End If
	End If
End If

This is called as linear probing. First searching is main area, then entire overflow area and still if record is not found then the hashing feature of quickly figuring the address of record is washed out. Too large and full overflow area will slow down the search operation and makes the search clumsy.

Deletion

If keys get deleted then there will be spaces in between. After lots of deletion or when overflow area gets full and vacancies is somewhere in main area, then put records in appropriate place and clean the general overflow area.


If there is no redundancy (i.e. empty space in main area after the key which the key of record to be placed is collided) and overflow area too is full then

  1. Increase overflow area
  2. Change the hash function (This is better option)

If hash function is changed, the file needs to be reorganized completely. At the time of reorganization the file is not made available to any process. Large file will cost a lot of time due to large number of record reorganization. Hence this task should be performed at spare time.

Way 3 – Bucketing

Bucket
A bucket is capable of holding more than one record. Within a bucket it is always a linear search. Larger buckets increase the cost of linear search. If you are certain that on an average three key values will land on same address space then define a bucket of size 3. The address will be the address of the bucket. After placing three keys if any further collision takes place 

e.g. h (key4) -> A1 then create another bucket and set the pointer of the previous bucket to this new bucket.

Now the bucket can store 6 key values. If the new bucket also gets filled then repeat the same procedure of creating new bucket and setting the pointer. Hence a bucket is like a linked list. A bucket pointing to another bucket is like a node pointing to another node.

To get a record, apply hash function on the key value, go to the bucket with the resultant address, perform linear search and fetch the record.

As we allocated space for 3 records in a bucket but it holds only 1 record (key 4) then remaining space will be wasted. Hence another approach is to define a common overflow area. Its size should be greater than individual buckets. If bucket is full then instead of allocating a new bucket, place the record in this overflow area. While searching, if a record is not found in its bucket then land in overflow area and perform linear search.

Hash Function : Folding


Two folding methods are used they are:
  • Fold shift
  • Fold boundary


5.1 Fold Shift
In fold shift the key value is divided into parts whose size matches the size of the required address. Then the left and right parts are shifted and added with the middle part.

5.2 Fold Boundary
Fold Boundary
In fold boundary the left and right numbers are folded on a fixed boundary between them and the center number. The two outside values are thus reversed.

If the need is to generate a 5 digit address then make units of 4 digits and add them which will make a 4 or 5 digit address.

If the records will be less than 999 then use 1764. If records will be near to 9999 then use 13221. Fold and achieve expected size of address space. The loading factor will be 999/1764 = 0.57

Hash Function : Mid Square Method

In this method, when they key is of big size then its square will double the number of digits; of which we select few middle digits to form the address.

Example: 
94522 = 89340304: address is 3403

Why Middle Digit?

Last few digits of a squared roll number will be matching across classes (FY, SY and TY). Hence if we consider least significant digits then there will be collisions.

If we consider most significant digits then at times most significant digits

  • Will be matching for squares of 112010001, 112010002, …
  • Will be wide apart for squares of 102010001, 1120100201, and 122010001.
Hence when you consider least significant digits, there will be collision and when most significant digits are considered there might be collision along with wasting address due to sparse. 

No square will end on 2, 3, 7, and 8. The address spaces ending on 2, 3, 7, and 8 will never be used. This is another reason why we do not consider least significant digits.

The solution is – take a key, square it, chop 2-3 digits from each end and the middle remaining past will be the address. The chance of collision is pretty less. Hence the distribution will be stable, normalize and within a narrower range.

Loading Factor:

Loading factor is number of records in a file divided by maximum number of records that can be accommodated in a file. It will be a fraction and the value will be <=1.

E.g. If 50,000 records can be stored in address range of 1 million then the LF is 0.5

The advantage is that the file can grow beyond anticipation at later point of time.

Speeds:

In this method, square and chopping goes at electronic speed + disk access will be at electronic/mechanical speed (Mechanical because there will be rotation). 

Note: Electronic speed is greater than mechanical speed.

In B Tree we have 4 disk accesses but here only one disk access. Hence speed is fast in hashing.
The disadvantage of this method is there will be collisions but we can try to reduce collisions as much as possible. Another limitation is the size of the key.

Hash Function : Division-Remainder Method


Map a key k into one of m slots by taking the remainder of k divided by m. That is, the hash function is h (k) = k mod m.

In this method, if 5,000 records then divide by 5000. The remainder will be between 0 and 4999. 

Scenario 1-

If the number of records increases then two key values will land on same address. E.g. 
  • When Key=1, then Key mod 5000 = 1
  • When Key=5001 then Key mod 5000 = 1
Hence depending on key distribution this method may fail.

Scenario 2-

In the college 3 digits are assigned for roll number for the students of each class. The roll numbers can be from 000 to 999, hence divide by 1000. When you divide roll number 1 by 1000 then remainder will be 1 (this is the address where the record of roll number 1 is stored). But roll number 1 is in FY, SY and TY. Hence there is a collision as roll number 1 of all the classes will refer to the same address on the disk. Solution to this problem can be assign unique roll numbers. If last assignment was 199 then the next admission will get roll number 200 irrespective of the class. But this will get exhausted at 999. 

It works fine with keys that are sparse and with any list size, but a list size that is a prime number produces fewer collisions than other list sizes.

Hash Function : Relative Addressing


h (key) -> Relative Address

These are very simple hashing functions which do not require any space or extra efforts. It works on dense key distribution.

For a business you considered 100 entries of customers hence allocated continuous space to store 100 records. The record for customer id 1 was placed at address 1, for customer id 2 was placed at address 2 and so on. The space with address 101 to 180 is allocated to some other file. Now the business flourishes and there is a need to enter record for customer with customer id 101.  The solution can be generating a relative address. If key = 5 then the relative address can be 205 i.e. we are pinning record at 205 with key value 5. Now if the file grows and limit reached then relocate the entire file to a new continuous location larger than the current space.

Sparse Key Distribution
It means of millions only a fraction is required. Consider designing a hash function for stored roll numbers, which will act as a key to get the address of a particular student’s record stored on the disk. The roll number consists of 9 digits. Hence theoretically we have to make provision for 109 records. The pattern of the roll number is 

Year (2 digit) + Course Code (3 Digit) + [0 – Male | 1 – Female] + Roll Number (3 digit)

  1. Out of the 109 values as approximately only 3000 students take admission in a year, hence in next 50 years 3000X50 = 150000 records will be used.
  2. As 3 digits are assigned for course code, maximum 999 courses can run in the institute which is too much beyond a possibility (as at present approximately 35 courses are running).
  3. If a roll number is assigned to a male candidate 112010040 then there can’t exist a female candidate with roll 112011040.
Hence we have to filter out the key values that will never ever be allocated. The need is to collapse.

Collapse the keys
Which keys will be blank and which will be present is not predictable (consider scenario 3). Hence there is no fixed pattern.

Hash Function : Direct Hashing

This is the simplest hash function – h (n) = n

E.g. To find record of roll number 40, h (40) will give address of the record. Address is generated using the key value. This works only when keys are densely packed i.e. every key is associated with a record. This is not a very popular hash function as it leads to dense organization. If key of a record is 5 then the record must also be placed at address 5.

Problems with direct hashing – 
  1. For a business you considered 100 entries of customers hence allocated continuous space to store 100 records. The record for customer id 1 was placed at address 1, for customer id 2 was placed at address 2 and so on. The space with address 101 to 180 is allocated to some other file. Now the business flourishes and there is a need to enter record for customer with customer id 101. According to hash function we have to place the file at address 101 but it is already occupied. Hence the file cannot grow. The solution can be Relative hashing.
  2. This scheme doesn't let you perform disk defragmentation. Hence this is not practically acceptable. 

Tuesday 3 July 2012

Working with FTP using commands

Examples

The command list is some what exhaustive. So we will see,  practically how to work with them.

After configuring FTP on Windows Server 2008, start the client machine. 
Start Command Prompt : Start -> Run -> cmd -> OK

1. Connecting to the ftp server

ftp mcitp.com
Enter username 
Enter password
.. and you are connected. Now fire the ftp commands as per your need.


2. List the files in the remote directory

ftp> ls


3. Create a remote directory


ftp> mkdir DirectoryName

4. Change the directory


ftp> cd DirectoryName

5. Check the remote directory path


ftp> pwd


6. Copy a file from the local machine to the remote machine


ftp> put FilePath




7. Copy more than one file from the local machine to the remote machine


I want to copy the all the notepad(.txt) files from my local machine to the remote machine

ftp> mput *.txt

You will be asked at the time of transferring each file. Based on your answer (y/n) the action will be performed.


8. Copy a file from the remote machine to the local machine

Before transferring the file


ftp> get FileName




.... and the file is transferred.



9. Copy more than one file from the remote machine to the local machine


Before transferring files ..


Copy the all the files from remote local machine to my local machine
(remote machine folder is /MyFolder)

ftp> get *




.... and the files are transferred.



10. Exit the FTP environment

There are two commands to exit the FTP environment.

ftp> bye


or the other command is

ftp> quit





FTP Command List & Description

Command
Description
!
Preceding a command with the exclamation point will cause the command to execute on the local system instead of the remote system.
?
Request assistance or information about the FTP commands. This command does not require a connection to a remote system.
ascii
Set the file transfer mode to ASCII (Note: this is the default mode for most FTP programs).
binary
Set the file transfer mode to binary (Note: the binary mode transfers all eight bits per byte and must be used to transfer non-ASCII files).
bye
Exit the FTP environment (same as quit). This command does not require a connection to a remote system.
cd
Change directory on the remote system.
close
Terminate a session with another system.
delete
Delete (remove) a file in the current remote directory (same as rm in UNIX).
dir
Lists the contents of the remote directory.The asterisk (*) and the question mark (?) may be used as wild cards. For example:
get
WIP
help
Request a list of all available FTP commands. This command does not require a connection to a remote system.
lcd
Change directory on your local system (same as CD in UNIX).
ls
List the names of the files in the current remote directory.
mget
WIP
mkdir
Make a new directory within the current remote directory.
mput
Copy multiple files from the local system to the remote system. (Note: You will be prompted for a "y/n" response before copying each file).
open
Open a connection with another system.
put
Copy a file from the local system to the remote system.
pwd
Find out the pathname of the current directory on the remote system.
quit
Exit the FTP environment (same as "bye"). This command does not require a connection to a remote system.
rmdir
Remove (delete) a directory in the current remote directory.

Do you like this article?