Cloud Computing - Characteristics, Service Models & Deployment Models

Cloud computing is a model for enabling ubiquitous, convenient, on-demand network access to a shared pool of configurable computing resources (e.g., networks, servers, storage, applications, and services) that can be rapidly provisioned and released with minimal management effort or service provider interaction. This cloud model is composed of five essential characteristics, three service models, and four deployment models.

Visual Model of Cloud Computing

Essential Characteristics:

On-demand self-service: A consumer can unilaterally provision computing capabilities, such as server time and network storage, as needed automatically without requiring human interaction with each service provider.

Broad network access: Capabilities are available over the network and accessed through standard mechanisms that promote use by  heterogeneous thin or thick  client platforms (e.g., mobile phones, tablets, laptops, and workstations).

Resource pooling: The provider’s computing resources are pooled to serve multiple consumers using a multi-tenant model, with different physical and virtual resources dynamically assigned and reassigned according to consumer demand. There is a sense of location independence in that the customer generally has no control or knowledge over the exact location of the provided resources but may be able to specify location at a higher level of abstraction (e.g., country, state, or datacenter). Examples of resources include storage, processing, memory, and network bandwidth.

Rapid elasticity: Capabilities can be elastically provisioned and released, in some cases automatically, to scale rapidly outward and inward commensurate with demand. To the consumer, the capabilities available for provisioning often appear to be unlimited and can be appropriated in any quantity at any time.

Measured service: Cloud systems automatically control and optimize resource use by leveraging a metering capability at some level of abstraction appropriate to the type of service (e.g., storage, processing, bandwidth, and active user accounts). Resource usage can be monitored, controlled, and reported, providing transparency for both the provider and consumer of the utilized service.

Service Models:

Software as a Service (SaaS): The capability provided to the consumer is to use the provider’s applications running on a cloud infrastructure. The applications are accessible from various client devices through either a thin client interface, such as a web browser (e.g., web-based email), or a program interface. The consumer does not manage or control the underlying cloud infrastructure including network, servers, operating systems, storage, or even individual application capabilities, with the possible exception of limited  userspecific application configuration settings.

Platform as a Service (PaaS): The capability provided to the consumer is to deploy onto the cloud infrastructure consumer-created or acquired applications created using programming languages, libraries, services, and tools supported by the provider. The consumer does not manage or control the underlying cloud infrastructure including network, servers, operating systems, or storage, but has control over the deployed applications and possibly configuration settings for the application-hosting environment.

Infrastructure as a Service (IaaS):  The capability provided to the consumer is to provision processing, storage, networks, and other fundamental computing resources where the consumer is able to deploy and run arbitrary software, which can include operating systems and applications. The consumer does not manage or control the underlying cloud infrastructure but has control over operating systems, storage, and deployed applications; and possibly limited control of select networking components (e.g., host firewalls).

Deployment Models:

Private cloud: The cloud infrastructure is provisioned for exclusive use by a single organization comprising multiple consumers (e.g., business units). It may be  owned, managed, and operated by the organization, a third party, or some combination of them, and it may exist on or off premises.

Community  cloud: The cloud infrastructure  is  provisioned for exclusive use by  a specific community of consumers from organizations that  have shared concerns (e.g., mission, security requirements,  policy, and compliance considerations). It may be  owned, managed, and operated by  one or more of the organizations in the community, a third party, or some combination of them, and it may exist on or off premises.

Public cloud: The cloud infrastructure is provisioned for open use by the general public. It may be owned, managed, and operated by a business, academic, or government organization, or some combination of them.  It exists on the premises of the cloud provider.

Hybrid cloud: The cloud infrastructure is a  composition of two or more  distinct  cloud infrastructures (private, community, or public) that remain unique entities, but are bound together by standardized or proprietary technology that enables  data and application portability (e.g., cloud bursting for load balancing between clouds).

References:

• The NIST Definition of Cloud Computing
• Cloud Computing @ Wikipedia
• Who Else Wants to Understand the 3 Types of Cloud Computing?

Written by Munia Balayil

GATE 2013 Materials - Books, Solved Question Paper Banks & Guides

Snapdeal has discounts running on GATE 2013 preparatory materials - Guides, 10 Years Solved Question Banks etc. It is available at the following location

Snapdeal - Competitive Exam Books: Buy Entrance Exams Preparation Books Online

Written by Code Blocks

Prim's Algorithm - Minimum Cost Spanning Tree problem

"Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm was developed in 1930 by Czech mathematician Vojtěch Jarník and later independently by computer scientist Robert C. Prim in 1957 and rediscovered by Edsger Dijkstra in 1959. Therefore it is also sometimes called the DJP algorithm, the Jarník algorithm, or the Prim–Jarník algorithm." - Wikipedia

1. MST_PRIM(G, cost, root)
2.   for each vertex u ∈ V[G]
3.     do Key[u] <- ∞
4.        Pred[u] <- NIL
5.   Key[root] <- 0
6.   Q <- V[G] // create a priority queue of the vertices
7.   while Q ≠ φ
8.     do u <- EXTRACT_MIN(Q)
9.       for each v ∈ Adj[u]
10.        do if v ∈ Q & (cost(u,v) < Key[v])
11.          then Pred[v] <- u
12.               Key[v] <- cost(u,v)

Key[v] -> minimum weight of any edge connecting v to a vertex in the tree

Pred[v] -> parent of v in the tree

Q -> min priority queue of all the vertices that are not in the tree

Initially, A = { (v, Pred[v]) : v ∈ V - {root} - Q }
Finally, A = { (v, Pred[v] : v ∈ V - {root} } // Q is empty

References :

• Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (Available @ Flipkart)

Written by Munia Balayil

Kruskal's Algorithm - Minimum Cost Spanning Tree Problem

"Kruskal's algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component)." - Wikipedia

1. MST_KRUSKAL(G, cost)
2.   A -> φ
3.   for each vertex v ∈ V[G]
4.     do MAKE-SET(v)
5.   sort the edges of E into non-decreasing order by weight
6.   for each edge (u,v) ∈ E taken in non-decreasing order by weight
7.     do if FIND-SET(u) ≠ FIND-SET(v)
8.       then A <- A ∪ { (u,v) }
9.         UNION(u,v)
10.  return A

MAKE-SET(x) -> creates a new set (tree) whose only
member is x (creates disjoint sets)

UNION(x,y) -> unites the dynamic sets that contain x & y, 
say Sx & Sy into a new set that is the union of these two sets 
Sx & Sy are assumed to be disjoint prior to this operation

FIND-SET(x) -> return a pointer to the representative of the set
containing x (here the root of the tree to which it belongs to)

References :

• Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (Available @ Flipkart)

Written by Munia Balayil

Birthday Paradox Simulation in C

/* Given a group of n people how to calculate the probability that m people among them have the same birthday without using a formula*/

#include<stdio.h>
#include<stdlib.h>

int main()
{
  int i, n, m, rand_birthday, j, a;
  int *array = NULL, c, k, t;
  float count = 0.0, trial = 1.0, prob, percent;
  
  printf("\nEnter the number of people in a room:");
  scanf("%d", &n);
  printf("\nEnter the number of people whose birthday ");
  printf("needs to be on the same day:");
  scanf("%d", &m);
  printf("\nEnter the no. of trials:");
  scanf("%d", &t);

  // Dynamically allocate memory for n elements
  array = (int *)calloc(n, sizeof(int));

  while(trial <= t)
  {
    for(i = 0; i < n; i++)
    {
      rand_birthday = gen_rand();
      array[i] = rand_birthday;
    }
    printf("\nRandom birthdays are : \n");
    for(i = 0; i < n; i++)
      printf(" %d ", array[i]);
    printf("\n");
  
    // Sorting the birthdays
    for(i = 0; i < n; i++)
    {
      for(j= i + 1; j < n; j++)
      {
        if(array[i] > array[j])
        {
          a = array[i];
          array[i] = array[j];
          array[j] = a;
        }
      }
    }

    printf("\nRandom birthdays(sorted) are : \n");
    for(i = 0; i < n; i++) 
      printf(" %d ", array[i]);
    printf("\n");

    // Check for the same birthdays
    i = 0; j = 1; 
    while(j < n)
    {
      c = 1;
      if(array[i] != array[j])
      {
        i++;
        j++;
      }
      else
      {
        for(k = j; ((k < n) && (array[i] == array[k])); k++)
          c++;
        i = k;
        j = k + 1;
        if(c >= m)
        {
          count++;
          break;
        }
      }
    }
    trial++;
  }

  // Calculate the probability
  printf("\ncount = %f, \ntrials = %f\n", count, trial);
  prob = (count/trial);
  printf("Probability of getting %d same birthdays", m);
  printf(" among %d people is %f", n, prob);
  percent = prob * 100;
  printf(" = %f percentage\n", percent);

  return 0;
}

int gen_rand(void)
/* returns random number in range of 0 to 364 */
{
   int n;
   n=rand() % 365;
   return(n);
}

Written by Munia Balayil

Minimum Distance Triplet in C

//Program : Given 3 arrays, find the triplet (containing one element from 
//each array) with the minimum distance. The distance of a triplet (a,b,c) 
//is defined as max(|a-b|, |b-c|, |c-a|)

#include<stdio.h>

int main()
{
  int n1, n2, n3, i, j, k, max, triplet_dist, trip_dist;
  int a1[10], a2[10], a3[10], triplet[3];

  // Input the 3 arrays
  printf("Enter the sizes of the 3 matrices\n");
  scanf("%d %d %d", &n1, &n2, &n3);
  printf("Enter the elements of the first array\n");
  for(i = 0; i < n1; i++)
    scanf("%d", &a1[i]);
  printf("Enter the elements of the second array\n");
  for(i = 0; i < n2; i++)
        scanf("%d", &a2[i]);
  printf("Enter the elements of the third array\n");
  for(i = 0; i < n3; i++)
        scanf("%d", &a3[i]);
  
  // Initialization of min distance
  triplet_dist = 9999;

  // Compute min distance of triplet
  for(i = 0; i < n1; i++)
    for(j = 0; j < n2; j++)
      for(k = 0; k < n3; k++)
      {
        // find out the distance of the triplet
        max = abs(a1[i] - a2[j]);
        if(abs(a2[j] - a3[k]) > max)
          max = abs(a2[j] - a3[k]);
        if(abs(a1[i] - a3[k]) > max)
          max = abs(a1[i] - a3[k]);
        
        // If the distance found is less than the already found min 
        // distance, update triplet array and triplet distance
        if(max < triplet_dist)
        {
          triplet_dist = max;
        }
      }

  // Print the min distance triplets
  printf("The minimum distance is %d\n", triplet_dist);
  printf("The min distance triplets are:\n");
  trip_dist = 9999;
  for(i = 0; i < n1; i++)
    for(j = 0; j < n2; j++)
      for(k = 0; k < n3; k++)
      {
        // findout the distance of the triplet
        max = abs(a1[i] - a2[j]);
         if(abs(a2[j] - a3[k]) > max)
           max = abs(a2[j] - a3[k]);
         if(abs(a1[i] - a3[k]) > max)
           max = abs(a1[i] - a3[k]);

         if(max == triplet_dist)
         {
           printf("(");
           printf("%d %d %d", a1[i], a2[j], a3[k]);
           printf(")");
           printf("\n");
         }
      }

  return 0;
}

Written by Munia Balayil

GATE 2013 - Comprehensive Information

Graduate Aptitude Test in Engineering (GATE) is an all India examination that primarily tests the comprehensive understanding of various undergraduate subjects in Engineering and Technology. GATE is conducted jointly by the Indian Institute of Science and seven IITs (IIT Bombay, IIT Delhi, IIT Guwahati, IIT Kanpur, IIT Kharagpur, IIT Madras and IIT Roorkee) on behalf of the National Coordination Board – GATE, Department of Higher Education, Ministry of Human Resource Development (MHRD), Government of India.

The GATE score of a candidate reflects the relative performance level of a candidate. The score is used for admissions to various post-graduate programmes (eg. M.E., M.Tech, direct Ph.D.) in Indian higher education institutes with financial assistance provided by MHRD and other Government agencies. The score may also be used by Public sector units for employment screening purposes.

Dates of Examination Online: 20th January 2013 (Sunday) Offline: 10th February 2013 (Sunday)	What is New in GATE 2013 ? Online papers: AE, AG, AR, BT, CE, CH, CY, GG, MA, Mn, MT, PH, TF, XE, and Xl Offline papers: CS, EC, EE, in, ME, and Pi
Application Fee ₹1200 for General/OBC male applicants ₹600 for SC/ST/PD male applicants There is no application fee for female applicants The application fee is not refundable	Application Deadlines Commencement of online application: 1st September 2012 (Saturday) Last date for: Submission of online application (website closure): 30th September 2012 (Sunday) Receipt of application with supporting documents at gate offices: 8th October 2012 (Monday)

Download GATE 2013 Brochure -- Download GATE 2013 Poster

Useful Links:

• GATE 2013 - Important Dates
• GATE 2013 - Eligibility Criteria
• GATE 2013 - How to Apply ?
• GATE 2013 - Online Application Interface/Login [Application will start on September 1st, 2012 t 00.01 hrs]
• GATE 2013 - State-wise Exam Centers [Google Maps]
• GATE 2013 - New Formula for GATE Score
• GATE 2013 - Results [Results will be announced on March 15, 2013 at 10:00 hrs]

What’s New in GATE 2013?

• 15 subject papers will be conducted by an ONLINE computer based test: AE, AG, AR, BT, CE, CH, CY, GG, MA, MN, MT, PH, TF, XE, and XL.
• Female candidates  are exempted from paying the application fee.
• All candidate related information and grievance redressal will be available in a single GATE Online Applicant Interface.
• Soft copies of photograph and signature must be uploaded during online application (This is in addition to sending recent photograph of applicant with signed application).
• A new formula will be used for calculating the GATE score.
• Biometric information (Photograph and fingerprint) may be captured on the day of the examination for randomly selected candidates.

Important Points for GATE 2013

• Application Process: For GATE 2013,  candidates need to register and fill the application ONLINE only by accessing the zonal GATE websites of IISc and seven IITs. The application process is complete only when a print out of the filled ONLINE application with the candidate’s signature and a good quality photo affixed in the appropriate place is received by the respective GATE office along with necessary documents, if any, on or before 8 October 2012. Please note that application forms are NOT available for sale anywhere.
• Downloadable Admit Card: Admit cards are NOT sent by mail anymore. Admit cards can only be downloaded from the zonal GATE websites from 5th December 2012 onwards. Bring the admit card to the test center along with at least one original (not photocopied / scanned copy) and valid (not expired) photo identification.
• Use of black ink ball point pen for Offline exams:  Candidates should use only black ink ball point pen for darkening of the bubbles in the OMR sheet. Since bubbles darkened by the black ink ball point pen cannot be erased, candidates should darken the bubbles in the OMR sheet very carefully (be sure before darkening).
• Numerical answer type questions in ONLINE papers: In the ONLINE papers, the question paper will consist of questions of multiple choice type and questions of numerical answer type. For multiple choice type questions, each question will have four choices for the answer. For numerical answer type questions, each question will have a number as the answer. Each online paper will have 15 or more marks worth of questions requiring numerical answers where possible.
• Pre-final year students:  Pre-final year students are NOT eligible to write GATE 2013. For details, refer to eligibility for GATE examination.

Information courtesy: IITB Gate 2013 Website.

Written by Code Blocks

GATE 2013 - State-wise Exam Cities

The centers for online exam papers are different from the centers for offline exam papers.  First determine if the paper of your choice is to be conducted online or offline, and check for a city in the state of your choice.  Also seen in the table is the Zonal GATE Office (Either of the IITs or IISc).  This Zonal office will be your point of contact for any enquiries regarding your exam center.

Online Exam Cities (click to use Google Maps)

View GATE Online Exam Cities in a larger map

Offline Exam Cities (Click to use Google Maps)

View GATE Offline Exam Cities in a larger map

List of exam cities

State	Exam Mode	City	Zonal GATE Office
Andhra Pradesh	ONLINE	Ananthapur, Hyderabad, Kurnool, Secunderabad	IISc
		Kakinada, Vijayawada,Visakhapatnam	IITKGP
		Bapatla, Guntur, Kadapa,Nellore, Tirupati, Warangal	IITM
	OFFLINE	Ananthapur, Hyderabad, Kurnool, Mahabubnagar, Secunderabad	IISc
		Bhimavaram , Eluru ,Kakinada, Machilipatnam,Rajahmundry, Srikakulam, Tadepalligudem,Vijayawada,Visakhapatnam	IITKGP
		Bapatla, Chittoor, Gudur,Guntur, Kadapa, Karimnagar, Khammam, Kothagudem, Manchiryal, Nalgonda,Nellore, Ongole, Tenali, Tirupati,Warangal	IITM
Arunachal Pradesh	ONLINE	-
	OFFLINE	Itanagar	IITG
Assam	ONLINE	Guwahati, Jorhat, Silchar, Tezpur	IITG
	OFFLINE	Guwahati, Jorhat, Silchar, Tezpur	IITG
Bihar	ONLINE	Patna	IITG
	OFFLINE	Bhagalpur,Patna	IITG
Chattisgarh	ONLINE	Bilaspur,Raipur	IITKGP
	OFFLINE	Bilaspur,Raipur	IITKGP
Delhi	ONLINE	Delhi	IITD
	OFFLINE	Delhi Central, Delhi East, Delhi North, Delhi South, Delhi West	IITD
Goa	ONLINE	-
	OFFLINE	Goa	IITB
Gujarat	ONLINE	Ahmedabad,Rajkot,Surat, Vadodara	IITB
	OFFLINE	Ahmedabad, Mahesana,Rajkot,Surat, Vadodara	IITB
Haryana	ONLINE	Faridabad, Gurgaon	IITD
		Hisar, Kurukshetra, Rohtak	IITR
	OFFLINE	Faridabad, Gurgaon	IITD
		Hisar, Kurukshetra, Rohtak, Yamunanagar	IITR
Himachal Pradesh	ONLINE	Hamirpur, Shimla	IITR
	OFFLINE	Hamirpur, Shimla	IITR
Jammu & Kashmir	ONLINE	Jammu	IITR
	OFFLINE	Jammu	IITR
Jharkhand	ONLINE	Dhanbad	IITG
		Jamshedpur,Ranchi	IITKGP
	OFFLINE	Dhanbad	IITG
		Jamshedpur,Ranchi	IITKGP
Karnataka	ONLINE	Belgaum, Bengaluru, Davengere, Hassan, Hubli, Mangalore, Manipal, Mysore, Surathkal	IISc
		Gulbarga	IITB
	OFFLINE	Bagalkot ,Belgaum, Bengaluru, Davangere, Hassan, Hubli, Mangalore, Manipal,Mysore, Surathkal	IISc
		Gulbarga	IITB
Kerala	ONLINE	Kanjirappally, Kannur, Kollam, Kottayam,Kozhikode, Palakkad, Thrissur	IISc
		Ernakulam, Thiruvananthapuram	IITM
	OFFLINE	Alappuzha (Aleppy), Chengannur, Kanjirappally, Kannur, Kollam, Kothamangalam, Kottayam, Kozhikode, Palakkad, Thrissur	IISc
		Ernakulam, Thiruvananthapuram,	IITM
Madhya Pradesh	ONLINE	Indore,Ujjain	IITD
		Bhopal,Gwalior,Jabalpur	IITK
	OFFLINE	Indore,Ujjain	IITD
		Bhopal,Gwalior,Jabalpur, Saugar (Sagar, MP)	IITK
Maharashtra	ONLINE	Ahmednagar,Amravati,Aurangabad, Jalgaon,Kolhapur,Mumbai (Central Line),Mumbai (Western Line), Nagpur, Nanded, Nashik, Navi Mumbai, Pune (City),Pune (Pimpri Chinchwad), Sangli, Solapur, Thane	IITB
	OFFLINE	Ahmednagar, Akola, Amravati, Aurangabad, Bhusawal, Gondia, Jalgaon, Kolhapur, Latur, Lonavala, Loni, Mumbai (Central Line), Mumbai (Western Line), Nagpur, Nanded, Nashik, Navi Mumbai, Pandharpur, Pune (City), Pune (Pimpri Chinchwad), Sangli, Satara, Shegaon, Solapur, Thane, Wardha	IITB
Manipur	ONLINE	Imphal	IITG
	OFFLINE	Imphal	IITG
Orissa	ONLINE	Bhubaneswar,Cuttack,Rourkela, Sambalpur	IITKGP
	OFFLINE	Balasore, Berhampur,Bhubaneswar,Cuttack,Rourkela, Sambalpur	IITKGP
Puducherry	ONLINE	Puducherry	IITM
	OFFLINE	Puducherry	IITM
Punjab	ONLINE	Amritsar, Bathinda,Chandigarh, Jalandhar,Patiala	IITR
	OFFLINE	Amritsar, Bathinda,Chandigarh, Jalandhar,Ludhiana,Patiala	IITR
Rajasthan	ONLINE	Ajmer,Bikaner, Jaipur,Jodhpur,Kota,Udaipur	IITD
	OFFLINE	Ajmer, Alwar,Bikaner, Jaipur,Jodhpur,Kota, Sikar,Udaipur	IITD
Sikkim	ONLINE	—-
	OFFLINE	Gangtok	IITG
Tamil Nadu	ONLINE	Chennai, Chidambaram,Coimbatore,Madurai,Salem, Thanjavur, Tiruchirapalli, Tirunelveli,Vellore	IITM
	OFFLINE	Chennai North, Chennai South, Chidambaram,Coimbatore, Dindigul,Madurai, Nagercoil,Salem, Thanjavur, Tiruchirapalli, Tirunelveli,Vellore	IITM
Tripura	ONLINE	Agartala	IITG
	OFFLINE	Agartala	IITG
Uttar Pradesh	ONLINE	Agra,Aligarh,Allahabad,Bareilly,Kanpur,Lucknow,Varanasi	IITK
		Ghaziabad,Meerut, Muzaffarnagar, Noida	IITR
	OFFLINE	Mathura	IITD
		Agra,Aligarh,Allahabad,Bareilly,Gorakhpur,Jhansi,Kanpur,Lucknow, Sultanpur,Varanasi	IITK
		Bijnor,Ghaziabad,Meerut, Muzaffarnagar, Noida	IITR
Uttarakhand	ONLINE	Dehradun, Haldwani, Roorkee	IITR
	OFFLINE	Dehradun, Haldwani, Haridwar, Roorkee, Srinagar	IITR
West Bengal	ONLINE	Asansol,Durgapur, Kalyani, Siliguri	IITG
		Kharagpur, Greater Kolkata (North), Greater Kolkata (South)	IITKGP
	OFFLINE	Asansol,Durgapur, Kalyani, Siliguri	IITG
		Kharagpur, Kolkata	IITKGP

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

GATE Previous Years Question Papers can be accessed @ http://www.codeblocks.info/p/gate-computer-sciencecs-previous.html

Information courtesy: IITB Gate 2013 Website.

Written by Code Blocks

GATE 2013 - How to Apply ?

Before Applying, candidates are advised to go through the preliminary requirements given in this website and FAQ or download the GATE 2013 Brochure and read it carefully.

All candidates have to apply ONLINE. Details of the application fee and the steps in the application process are given below. The application fee is non-refundable.

Category	Application Fee
General/OBC-NC (Male Applicants)	₹ 1200/-
SC / ST / PD* (Male Applicants)	₹ 600/-
Female Applicants	₹ 0/- (Exempted)

Filling the Online Application

1. GATE Online Applicant Interface (website) can be accessed using this link.
2. You must first register yourself, by providing a valid email address.  Choose this carefully to be the one you check frequently, as all communications to you from the GATE offices will be sent to this address (Do not use anybody else’s email address; Only one person can register with one email address).
3. Upon registration, an email will be sent with a link. You will be required to choose a password when you click on the link.  Choose a password that is not easily guessable (should not be, for example: your name, DOB, 12345, asdf, etc.), so as to ensure that the data you provide is not accessible to any person other than yourself.
4. Next you will see an application form to be filled in.  Keep the following information ready:
• Personal information
• Communication Address (Important: PIN Code)
• Eligibility Degree Details (College address, PIN Code of College)
• GATE paper, Choice of GATE examination cities
• High quality image of  your photograph conforming to these requirements
• Good quality image of your signature (in .jpeg format) conforming to requirements similar to photograph
• Optional: PDF/JPEG files of supporting documents (Eligibility & Category Certificates) (max file size: per file 0.5 MB; see more details below in section ‘supporting documents’)
• Optional: Your Netbanking login and password to make the application fee payment (only for Male applicants).
5. Fill in the necessary data in the online application form following instructions given there. Upload the required soft copies of photo and signature.
6. Optional: You may upload PDF files of supporting documents conforming to the eligibility (except principal’s certificate) and category requirements given below in section Supporting Documents
7. You will have to select one of the two payment option (details given below) while filling the online form.
8. The GATE Online Applicant Interface allows you to enter data, “Save” partially filled form, “Logout”, and resume filling in by logging in again.
9. Once you finally submit the application, no further changes to the application can be made by the applicant.
10. Applicants who have selected online payment option will follow the instructions given below for online netbanking in payment section and complete payment process. Those who have selected challan payment option will directly proceed to the next step.
11. You will then see a link to “Print Application Form”.  You have to download a PDF file from this link and print it. It will contain four pages as mentioned below
• Page 1: Instructions and Address slip where you need to send hard copy
• Page 2-3: Two copies of application form with bottom part showing certificate to be signed by principal (if need be)
• Page 4: Optional page for applicants who select “bank challan” mode of payment. This page will contain 3 copies of challan to be processed with bank

Supporting Documents

Applicants have an option to upload supporting documents online.  Please make sure that the max file size permitted to upload per file is 0.5 MB. For scanning the documents please use the following setting

1. Resolution: 200 dpi
2. Color mode: 256 colors
3. File format: PDF or JPEG

Eligibility Documents

Eligibility criteria and necessary supporting documents can be found here

SC/ST/PD Certificate

1. Only male applicants who claim to be in any of the category SC/ST/PD have to produce valid documentary evidence, to qualify for the reduced fee.
2. Female applicants need not provide any SC/ST certificate, as the fee is exempted.
3. However, if any female applicant requests a scribe to assist writing the exam, a PD certificate has to be provided.

More information on Application Fee payment options & mailing the documents to GATE Office can be found here.

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

GATE Previous Years Question Papers can be accessed @ http://www.codeblocks.info/p/gate-computer-sciencecs-previous.html

Information courtesy: IITB Gate 2013 Website.

Written by Code Blocks

GATE 2013 - Eligibility Criteria

Only the following categories of candidates are eligible to appear for GATE 2013.  Necessary supporting documents must be submitted ONLINE or by post during the submission of the application form for the exam.  Please read this carefully and make sure that your year of qualification is not later that what is specified below.

Qualifying Degree (Short)	Qualifying Degree/Examination (Descriptive)	Description of Eligible Candidates	Year of qualification cannot be later than	Copies of Certificates to be submitted
				Passed in the year 2012 or earlier	Expected to complete in 2013 or later
B.E./B.Tech/B.Arch	Bachelor’s degree in Engineering/Technology/Architecture (4 years after 10+2/Post B.Sc./Post-Diploma)	4th year or Completed	2013	Degree Certificate / Provisional Certificate / Course Completion Certificate	Certificate from Principal (See below)
MSc./M.A./MCA equivalent	Master’s degree in any branch of Science / Mathematics / Statistics / Computer Applications or equivalent	Final year or Completed	2013	Degree Certificate / Provisional Certificate / Course Completion Certificate (pertaining to Masters degree)	Certificate from Principal (See below)
Int. M.E./M.Tech or DD (after 10+2 or Diploma)	Integrated Master’s degree programs or Dual Degree programs in Engineering / Technology (Five year programme)	4th/5th Year or Completed	2014	Degree Certificate / Provisional Certificate / Course Completion Certificate	Certificate from Principal (See below)
Int. M.E/M.Tech (Post BSc)	Post-BSc Integrated Master’s degree programs in Engineering / Technology (Four year programme)	2nd/3rd/4th year or Completed	2015	Degree Certificate / Provisional Certificate / Course Completion Certificate	Certificate from Principal (See below)
Professional Society Examinations (equivalent to B.E/B.Tech/B.Arch)	B.E/B.Tech equivalent examinations, of Professional Societies, recognized by MHRD/UPSC/AICTE (e.g. AMIE by Institution of Engineers-India, AMICE by the Institute of Civil Engineers-India)	Completed section A or equivalent of such professional courses	N/A	Professional Certificate/ Provisional Certificate/ Course Completion/ Membership Certificate issued by the Society or Institute	Copy of Marksheet for Section “A”

Certificate from Principal

Candidates who have to submit a certificate from their Principal, as determined from the above table, have to obtain a signature from their principal on a certificate that will be printed on the application PDF file provided only after completion of online application submission. Therefore,  this cannot be scanned and uploaded online.

Candidates with backlogs

Candidates who have appeared in the final semester/year exam in 2012, but with a backlog (arrears/failed subjects) in any of the papers in their qualifying degree should submit

1. A copy of any one of the marks sheets of  the final year,  OR
2. A letter from the principal indicating that the student has a backlog  from an earlier semester/year to be cleared, and therefore cannot produce a course completion certificate now.  This certificate will also be present in the last portion of the PDF application form provided to you after you submit application online.

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

GATE Previous Years Question Papers can be accessed @ http://www.codeblocks.info/p/gate-computer-sciencecs-previous.html

Information courtesy: IITB Gate 2013 Website.

Written by Code Blocks

GATE 2013 - New Formula for GATE Score

From 2013, the GATE score will be computed by a new formula.

New formula for GATE Score calculation

This formula is different from the one used earlier. After the declaration of the results, a GATE Scorecard will be issued to all the candidates of a paper whose marks are equal to or above the qualifying marks of SC/ST/PD candidates in that paper. There is no provision for the issue of Additional GATE scorecard.

The GATE 2013 Committee with the NCB’s approval  has the authority to decide the qualifying mark  for each GATE paper. In case any claim or dispute arises in respect of GATE 2013, it is hereby made absolutely clear that the Courts and Tribunals in Mumbai and Mumbai alone shall have the exclusive jurisdiction to entertain and settle any such dispute or claim.

GATE 2013 Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

GATE Previous Years Question Papers can be accessed @ http://www.codeblocks.info/p/gate-computer-sciencecs-previous.html

Information courtesy: IITB Gate 2013 Website.

Written by Code Blocks

GATE 2013 - Important Dates

GATE 2013 is being organized this year by Indian Institute of Technology, Bombay (IITB). The following are the various deadlines for GATE 2013.

Event	Day	Date
GATE Online Applicant Interface (website) Opens	Saturday	1 September 2012 (00:00 Hrs)
Last date for Submission of Online Application (website closure)	Sunday	30 September 2012 (23:00 Hrs)
Last date for the receipt of printed version of ONLINE Application at the respective zonal GATE Office	Monday	8 October 2012
Last date for request of change of city	Tuesday	20 November 2012
Availability of admit card on Online Application Interface	Wednesday	5 December, 2012
GATE 2013 Online Examination for Papers: AR, CE, GG, MA, MT, PH and TF	Sunday	20 January 2013 (09:00 Hrs to 12:00 Hrs)
GATE 2013 Online Examination for Papers: AE, AG, BT, CH, CY, MN, XE and XL	Sunday	20 January 2013 (14:00 Hrs to 17:00 Hrs)
GATE 2013 Offline Examination for Papers: CS, ME and PI	Sunday	10 February 2013 (09:00 Hrs to 12:00 Hrs)
GATE 2013 Offline Examination for Papers: EC, EE and IN	Sunday	10 February 2013 (14:00 Hrs to 17:00 Hrs)
Announcement of results on Online Applicant Interface	Friday	15 March 2013 (10:00 Hrs)

GATE 2013 Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

GATE Previous Years Question Papers can be accessed @ http://www.codeblocks.info/p/gate-computer-sciencecs-previous.html

Information courtesy: IITB Gate 2013 Website.

Written by Code Blocks

GATE 2013 - Results

Post-Exam Related Information

*** GATE 2013 results will be announced on March 15, 2013 at 10:00 hrs and will be available on the GATE Online Applicant Website ***

GATE Score

After the evaluation of the answers, the raw marks obtained by a candidate will be converted to a normalised GATE Score. From 2013 onwards, a new formula will be used to calculate the GATE Score.

GATE 2013 Results

• GATE 2013 results will be announced on March 15, 2013 at 10:00 hrs and will be available on the GATE Online Applicant Website.
• GATE 2013 score is valid for TWO YEARS from the date of announcement of the results.
• GATE 2013 results may be made available on payment basis to interested organizations (educational institutions, R & D laboratories, industries, etc.) in India and abroad based on a Memorandum of Understanding (MOU) between IIT Bombay and the requesting organization. Details in this regard can be obtained from the Chairman, GATE, IIT Bombay.

GATE Score Card

Scorecard will be issued (mailed to the correspondence address given in the application) to all the candidates for a paper whose marks are equal to or above the qualifying marks of SC/ST/PD candidates in that paper. There is no provision for issue of additional GATE scorecards.

The GATE 2013 Committee with the NCB’s approval has the authority to decide the qualifying score for each GATE paper. In case any claim or dispute arises in respect of GATE 2013, it is hereby made absolutely clear that the Courts and Tribunals in Mumbai and Mumbai alone shall have the exclusive jurisdiction to entertain and settle any such dispute or claim.

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

GATE Previous Years Question Papers can be accessed @ http://www.codeblocks.info/p/gate-computer-sciencecs-previous.html

Information courtesy: IITB Gate 2013 Website.

Written by Code Blocks

Theoretical Computer Science Cheat Sheet for GATE 2013 Aspirants

This is a 10 page cheat sheet containing the following information.

• Asymptotic notations
• Series expansions [ Geometric series, Harmonic series, etc.]
• Recurrences
• Probability
• Binomial distribution
• Trigonometry
• Matrices
• Hyperbolic Functions
• Number Theory
• Graph Theory
• Geometry
• Calculus
• Partial Fractions
• Fibonacci Numbers

It will be very useful to a GATE aspirant.

Download as PDF. You can also get a copy @ www.tug.org

GATE Previous Years Question Papers can be accessed @ http://www.codeblocks.info/p/gate-computer-sciencecs-previous.html

GATE 2013 - Notification, Application & Exam Date @ http://www.codeblocks.info/2012/07/gate-2013-notification-application-exam.html

GATE 2013 Syllabus - Computer Science @ http://www.codeblocks.info/2012/07/gate-2013-syllabus-computer-science.html

Written by Code Blocks

Set difference

Problem :  Given 2 arrays such that second is the subset of the first, find the set difference.
That is all the elements in array1 that are not in array2.
Eg:  
array1 - 6 7 4 3 9 1 2 5 8 0
array2 - 1 2 3 5 4
Set difference - 6 7 9 8 0

#include<stdio.h>

int main()
{
  int s1, s2, i, j, k = 0, check, a1[50], a2[50], a3[50];
  printf("\nEnter the size of array1:");
  scanf("%d", &s1);
  printf("\nEnter the elements\n");
  for(i = 0; i < s1; i++)
    scanf("%d", &a1[i]);
  printf("\nEnter the size of array2 < size of array1:");
  scanf("%d", &s2);
  printf("\nEnter the elements (should be a subset of array1)\n");
  for(i = 0; i < s2; i++)
    scanf("%d", &a2[i]);

  for(i = 0; i < s1; i++)
  {
    check = 1;
    for(j = 0; (j < s2 && check == 1); j++)
    {
      if(a1[i] != a2[j])
        continue;
      else
        check = 0;
    }
    if(check == 1)
      a3[k++] = a1[i];
  }
  printf("\nSet difference:\n");
  for(i = 0; i < k; i++)
    printf("%d ", a3[i]);

  return 0;
}

Written by Munia Balayil

Interview question(coding) - 2 :

Problem : Given an array, construct another array where i-th element
is the product of all but i-th elementof original array 
Example : array size = 5
          array = 5 1 2 3 4
          resultant array = 24 120 60 40 30

1*2*3*4 = 24, 5*2*3*4 = 120, 5*1*3*4 = 60, 5*1*2*4 = 40, 5*1*2*3 =30

          
#include<stdio.h>
 
int main()
{
  int a[50], b[50], i, j, n, prod;
  printf("Enter the size of the array ( < 50 ): ");
  scanf("%d", &n);
  printf("\nEnter the elements of the array : ");
  for(i = 0; i < n; i++)
    scanf("%d", &a[i]);
 
  for(i = 0; i < n; i++)
  { 
    prod = 1;
    for(j = 0; j < n; j++)
    {
      if(j != i)
        prod = prod * a[j];
    }
    b[i] = prod;
  }
  printf("\nThe resultant array\n");
  for(i = 0; i < n; i++)
    printf("%d ", b[i]);
    
  return 0;
}

Written by Munia Balayil

Interview question (coding) : Remove duplicates from a string

Problem : Given a string, remove the duplicate characters.
example: BANANAS -> BANS
         bananas -> bans
         BaNanAs -> BaNnAs
         1232416 - > 12346
         
#include<stdio.h>
 
int main()
{
  char s1[10], s2[10];
  int i, j, c;
  s2[0] = '\0';
 
  printf("Enter the string : ");
  scanf("%s",s1);
 
  for(i = 0; s1[i] != '\0'; i++)
  {
    c = 0;
    for(j = 0; (s2[j] != '\0' && c == 0); j++)
    {
      if(s1[i] != s2[j])
        continue;
      else
        c = 1;
    } 
    if(c == 0)
    {
      s2[j++] = s1[i];
      s2[j] = '\0';
    }
  }
  printf("\nString after removing duplicates:%s\n", s2);

  return 0;
}

Written by Munia Balayil

GATE 2013 Syllabus - Computer Science & Information Technology

GATE 2013 - SYLLABUS FOR COMPUTER SCIENCE AND INFORMATION TECHNOLOGY (CS)

Engineering Mathematics

Mathematical Logic:
Propositional Logic; First Order Logic.

Probability:
Conditional Probability; Mean, Median, Mode and Standard Deviation; Random Variables; Distributions; uniform, normal, exponential, Poisson, Binomial.

Set Theory & Algebra:
Sets; Relations; Functions; Groups; Partial Orders; Lattice; Boolean Algebra.

Combinatorics:
Permutations; Combinations; Counting; Summation; generating functions; recurrence relations; asymptotics.

Graph Theory:
Connectivity; spanning trees; Cut vertices & edges; covering; matching; independent sets; Colouring; Planarity; Isomorphism.

Linear Algebra:
Algebra of matrices, determinants, systems of linear equations, Eigen values and Eigen vectors.

Numerical Methods:
LU decomposition for systems of linear equations; numerical solutions of non-linear algebraic equations by Secant, Bisection and Newton-Raphson Methods; Numerical integration by trapezoidal and Simpson's rules.

Calculus:
Limit, Continuity & differentiability, Mean value Theorems, Theorems of integral calculus, evaluation of definite & improper integrals, Partial derivatives, Total derivatives, maxima & minima.

Computer Science and Information Technology

Digital Logic:
Logic functions, Minimization, Design and synthesis of combinational and sequential circuits; Number representation and computer arithmetic (fixed and floating point).

Computer Organization and Architecture:
Machine instructions and addressing modes, ALU and data-path, CPU control design, Memory interface, I/O interface (Interrupt and DMA mode), Instruction pipelining, Cache and main memory, Secondary storage.

Programming and Data Structures:
Programming in C; Functions, Recursion, Parameter passing, Scope, Binding; Abstract data types, Arrays, Stacks, Queues, Linked Lists, Trees, Binary search trees, Binary heaps.

Algorithms:
Analysis, Asymptotic notation, Notions of space and time complexity, Worst and average case analysis; Design: Greedy approach, Dynamic programming, Divide-and-conquer; Tree and graph traversals, Connected components, Spanning trees, Shortest paths; Hashing, Sorting, Searching. Asymptotic analysis (best, worst, average cases) of time and space, upper and lower bounds, Basic concepts of complexity classes  P, NP, NP-hard, NP-complete.

Theory of Computation:
Regular languages and finite automata, Context free languages and Push-down automata, Recursively enumerable sets and Turing machines, Undecidability.

Compiler Design:
Lexical analysis, Parsing, Syntax directed translation, Runtime environments, Intermediate and target code generation, Basics of code optimization.

Operating System:
Processes, Threads, Inter-process communication, Concurrency, Synchronization, Deadlock, CPU scheduling, Memory management and virtual memory, File systems, I/O systems, Protection and security.

Databases:
ER-model, Relational model (relational algebra, tuple calculus), Database design (integrity constraints, normal forms), Query languages (SQL), File structures (sequential files, indexing, B and B+ trees), Transactions and concurrency control.

Information Systems and Software Engineering:
information gathering, requirement and feasibility analysis, data flow diagrams, process specifications, input/output design, process life cycle, planning and managing the project, design, coding, testing, implementation, maintenance.

Computer Networks:
ISO/OSI stack, LAN technologies (Ethernet, Token ring), Flow and error control techniques, Routing algorithms, Congestion control, TCP/UDP and sockets, IP(v4), Application layer protocols (icmp, dns, smtp, pop, ftp, http); Basic concepts of hubs, switches, gateways, and routers. Network security  basic concepts of public key and private key cryptography, digital signature, firewalls.

Web technologies:
HTML, XML, basic concepts of client-server computing.

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

GATE Previous Years Question Papers can be accessed @ http://www.codeblocks.info/p/gate-computer-sciencecs-previous.html

Information courtesy: IITB Gate 2013 Website.

GATE 2013 - Notification, Application & Exam Date

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

Dates of Examination Online: 20th January 2013 (Sunday) Offline: 10th February 2013 (Sunday)	What is New in GATE 2013 ? Online papers: AE, AG, AR, BT, CE, CH, CY, GG, MA, Mn, MT, PH, TF, XE, and Xl Offline papers: CS, EC, EE, in, ME, and Pi
Application Fee ₹1200 for General/OBC male applicants ₹600 for SC/ST/PD male applicants There is no application fee for female applicants The application fee is not refundable	Application Deadlines Commencement of online application: 1st September 2012 (Saturday) Last date for: Submission of online application (website closure): 30th September 2012 (Sunday) Receipt of application with supporting documents at gate offices: 8th October 2012 (Monday)

GATE Previous Years Question Papers can be accessed @ http://www.codeblocks.info/p/gate-computer-sciencecs-previous.html

Information courtesy: IITB Gate 2013 Website.

Written by Munia Balayil

GATE 2012 EE Official Answer Key

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

The offical answer key for GATE 2012 'EE - Electrical Engineering' paper published by IIT Madras.

Download Official GATE 2012 EE Answer Key

You can also download this @ http://gate.iitm.ac.in/gate2012/anskeys.php

Written by Code Blocks

GATE 2012 EC Official Answer Key

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

The offical answer key for GATE 2012 'EC - Electronics and Communication Engineering' paper published by IIT Madras.

Download Official GATE 2012 EC Answer Key

You can also download this @ http://gate.iitm.ac.in/gate2012/anskeys.php

Written by Code Blocks

GATE 2012 CE Official Answer Key

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

The offical answer key for GATE 2012 'CE - Civil Engineering' paper published by IIT Madras.

Download Official GATE 2012 CE Answer Key

You can also download this @ http://gate.iitm.ac.in/gate2012/anskeys.php

Written by Code Blocks

GATE 2012 ME Official Answer Key

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

The offical answer key for GATE 2012 'ME - Mechanical Engineering' paper published by IIT Madras.

Download Official GATE 2012 ME Answer Key

You can also download this @ http://gate.iitm.ac.in/gate2012/anskeys.php

Written by Code Blocks

GATE 2012 CS/IT Official Answer Key

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

Here is the offical answer key for GATE 2012 'CS - Computer Science and Information Technology' paper published by IIT Madras.

Download Official GATE 2012 CS/IT Answer Key

You can also download this @ http://gate.iitm.ac.in/gate2012/anskeys.php

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

GATE Previous Years Question Papers can be accessed @ http://www.codeblocks.info/p/gate-computer-sciencecs-previous.html

Information courtesy: IITB Gate 2013 Website.

Written by Code Blocks

GATE 2012 CS/IT Question Paper

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

Download GATE 2012 CSE Question Paper.

Written by Code Blocks

GATE 2012 - CS/IT - Answer Key & Solutions

Please refer GATE 2012 CS/IT Official Answer Key for the official answer key published by IIT Madras.

GATE 2012 Answer Key & Solutions for Computer Science and Information Technology.

Download the GATE 2012 CS question paper here.

Key by ACE Engineering Academy
Key by Gate Forum
Key by Engineers Institute of India

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

GATE Previous Years Question Papers can be accessed @ http://www.codeblocks.info/p/gate-computer-sciencecs-previous.html

Information courtesy: IITB Gate 2013 Website.

Written by Code Blocks

GATE CS 2008 Questions 71-73 Solution

GATE 2013 Comprehensive Information Page @ http://www.codeblocks.info/2012/08/gate-2013.html

Consider a machine with a 2-way set associative data cache of size 64 Kbytes and block size 16 bytes. The cache is managed using 32 bit virtual addresses and the page size is 4 Kbytes. A program to be run on this machine begins as follows:

double ARR [1024] [1024] ;

int i, j ;

/* Initialize array ARR to 0.0 * /

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

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

    ARR[i] [j ]=0.0;

The size of double is 8 Bytes. Array ARR is located in memory starting at the beginning of virtual page 0xFF000 and stored in row major order. The cache is initially empty and no prefetching is done. The only data memory references made by the program are those to array ARR.

71. The total size of the tags in the cache directory is

(A) 32 Kbits (B) 34 Kbits (C) 64 Kbits (D) 68 Kbits

72. Which of the following array elements has the same cache index as ARR [0] [0]?

(A) ARR [0] [4] (B) ARR [4] [0] (C) ARR [0] [5] (D) ARR [5] [0]

73. The cache hit ratio for this initialization loop is

(A) 0% (B) 25% (C) 50% (D) 75%

Solutions:

Assumptions:

1. Memory is word addressible.
2. Since no information is given on the number of bytes constituting a word, we take 1 word = 1 Byte

71.  Answer: (D)


Cache Specification:

• Cache size = 64 KB
• Block size = 16 B
• 2 - way set associative

Number of cache blocks = 64 KB/16 B = 4 K = 2¹² blocks
Number of words in a cache block = 16 B/1 B = 16 = 2⁴ words

Number of sets in cache = 2^12 / 2 = 2¹¹ sets
Size of virtual address = 32 bits

Figure 1: Divisions of the address for cache use.

Blocks offset = 4 bits
Set index = 11 bits
=> Number of TAG bits = 32 - ( 11 + 4 ) = 17 bits

Size of TAGs in the cache directory = #cache blocks x #TAG bits = 2¹² * 17 = 2² * 2¹⁰ * 17 = 68 Kbits

---

72. Answer (B)


Page Size = 4 KB
Number of elements that fit in a page = 4 KB/8 B = 2⁹ elements
Number of elements in any row of the array = 1024 = 2¹⁰ elements
Number of words in an array element = 8 B/1 B = 8 words.

Two main memory addresses will be mapped to the same cache set if they have the same bit pattern for the Set Index bits.

The address where array element ARR[0][0] is stored is 0xFF000 or 0x000FF000 since the address is a 32bit address[8*4]. The bits 4 - 14 in the address correspond to the Set Index from the calculation in Q 71.

0x000FF000 = 00000000000011111111000000000000 - (1)

0x00107000 = 00000000000100000111000000000000 - (2)

Addresses 0x000FF000 - 0x000FF00F have the same Set Index bits. There are sixteen addresses in this range each corresponding to one word. Since each array element takes up 8 words, this address range can store only two elements, ARR[0][0] & ARR[0][1]. So these two elements map to one of the 2 ways [each way is one cache block = 16 B] of some set k in the cache.

The next address for which the Set Index bits are the same is (2)
The number of addresses/words between these (1)&(2) = 2⁽¹¹⁺⁴⁾.
The number of array elements that can be stored in this address range = 2¹⁵/8 = 2¹² = 2² * 2¹⁰
=> 4 rows can be stored in this address range. So the last address, 0x00107000, will store ARR[4][0].
So the first element of every 4^th row will map to the same cache set.

---

73. Answer (C)

Number of elements in the array ARR = 1024 * 1024
Size of an element of type double = 8 B
=> Number of elements that fit in a cache block = 16 B/8 B = 2 doubles or two array elements

The sequence of accesses generated by the for loop is

ARR[0][0], ARR[0][1], ARR[0][2], ... , ARR[0][1024], ARR[1][0], ARR[1][1], ARR[1][2], ... , ARR[1][1024], ... , ARR[1024][0], ARR[1024][1], ARR[1024][2], ... , ARR[1024][1024]

Initially, cache doesn't contain any array elements. The access for ARR[0][0] creates a cache miss which loads a block of data from main memory. Since two array elements can be accommodated in a cache block, ARR[0][1] is also brought into the cache. So the access for ARR[0][1] results in a cache hit. Again ARR[0][2] will be a cache miss which results in ARR[0][3] being a hit and so on.

Once the cache becomes full, existing cache blocks get replaced by the new blocks being brought into the cache, again with the same hit/miss pattern.

The cache access for half of the array elements will result in a miss and the other half will be a hit. So the cache hit ratio for the given initialization loop is 50%.

Written by Code Blocks

GATE 2010 CS/IT Answer Key

GATE 2010 - Answer Key

CS/IT : Computer Science & Information Technology

Written by Code Blocks