The Cyberphilic's Info Box

TEXT LINE LENGTH ADJUSTMENT

2009-11-09T08:38:00.001-08:00

TEXT LINE LENGTH ADJUSTMENT

AIM

To verify the text line length adjustment

PROBLEM DESCRIPTION

In a given set of lines the text length should be re format. So, that the text line of more than n characters that is maximum 40 character should be displayed. The output line maximum number of words that occupy less than or n characters should be printed. No word should extend across two lines. If suppose user give more than 40 characters then infinite loop will occurs.

Character length starts with 1.
String length function starts with 1.
No words in a file should not be splitted.

EXAMPLE

FLOWERS ARE BEAUT

IFULL.

This is wrong.

FLOWERS ARE BEAUTIFULL.

This is correct.

Flowers-actual is stores from 0-6 (7) elements.

ALGORITHM DESCRIPTION

Read the line length limit and add one to it, to allow for a space.
Initialize the word characters counts to 0 and end of line flag to false.
No end of line means, read the next character and store it.
If character is a space or a new paragraph then reset character count for new line.
Add current word length to current line length.
When it across the line length limit then move to next line.
Write out the current word and re-initialize count.
If at end of input line then, set end of input line flag and move to next line.

IMPLEMENTATION

#include <stdio.h>

#define size 40

Main()

FILE*fp;

Char a[100], str[50], i, empty, length;

Fp=fopen(“sk.txt”,”r”);

While(!feof(fp))

{

Fscanf(fp,”%s”,&a);

Empty=size-strlen(a)-1;

If(empty>length)

{

Strcat(str,a);

Strcat(str,” “);

}

Else

{

Printf(“%s\n”,str);

For(i=0;i<50;i++)

Str[i]=’\0’;

Strcat(str,” “);

}

If(feof(fp))

Printf(“%s\n”,str);

}

Fclose(fp);

Getch();

}

APPLICATIONS

Text processing,
Report writing and
File management.

Submitted by

K.KALAISELVI

08BCS033

An_Introduction_to_Data_Mining

2009-10-21T07:37:00.001-07:00

An Introduction to Data Mining

Discovering hidden value in your data warehouse

Overview

Data mining, the extraction of hidden predictive information from large databases, is a powerful new technology with great potential to help companies focus on the most important information in their data warehouses. Data mining tools predict future trends and behaviors, allowing businesses to make proactive, knowledge-driven decisions. The automated, prospective analyses offered by data mining move beyond the analyses of past events provided by retrospective tools typical of decision support systems. Data mining tools can answer business questions that traditionally were too time consuming to resolve. They scour databases for hidden patterns, finding predictive information that experts may miss because it lies outside their expectations.

Most companies already collect and refine massive quantities of data. Data mining techniques can be implemented rapidly on existing software and hardware platforms to enhance the value of existing information resources, and can be integrated with new products and systems as they are brought on-line. When implemented on high performance client/server or parallel processing computers, data mining tools can analyze massive databases to deliver answers to questions such as, "Which clients are most likely to respond to my next promotional mailing, and why?"

This white paper provides an introduction to the basic technologies of data mining. Examples of profitable applications illustrate its relevance to today’s business environment as well as a basic description of how data warehouse architectures can evolve to deliver the value of data mining to end users.

The Foundations of Data Mining

Data mining techniques are the result of a long process of research and product development. This evolution began when business data was first stored on computers, continued with improvements in data access, and more recently, generated technologies that allow users to navigate through their data in real time. Data mining takes this evolutionary process beyond retrospective data access and navigation to prospective and proactive information delivery. Data mining is ready for application in the business community because it is supported by three technologies that are now sufficiently mature:

1. Massive data collection

2. Powerful multiprocessor computers

3. Data mining algorithms

Commercial databases are growing at unprecedented rates. A recent META Group survey of data warehouse projects found that 19% of respondents are beyond the 50 gigabyte level, while 59% expect to be there by second quarter of 1996.1 In some industries, such as retail, these numbers can be much larger. The accompanying need for improved computational engines can now be met in a cost-effective manner with parallel multiprocessor computer technology. Data mining algorithms embody techniques that have existed for at least 10 years, but have only recently been implemented as mature, reliable, understandable tools that consistently outperform older statistical methods.

In the evolution from business data to business information, each new step has built upon the previous one. For example, dynamic data access is critical for drill-through in data navigation applications, and the ability to store large databases is critical to data mining. From the user’s point of view, the four steps listed in Table 1 were revolutionary because they allowed new business questions to be answered accurately and quickly.

Evolutionary Step	Business Question	Enabling Technologies	Product Providers	Characteristics
Data Collection (1960s)	"What was my total revenue in the last five years?"	Computers, tapes, disks	IBM, CDC	Retrospective, static data delivery
Data Access (1980s)	"What were unit sales in New England last March?"	Relational databases (RDBMS), Structured Query Language (SQL), ODBC	Oracle, Sybase, Informix, IBM, Microsoft	Retrospective, dynamic data delivery at record level
Data Warehousing & Decision Support (1990s)	"What were unit sales in New England last March? Drill down to Boston."	On-line analytic processing (OLAP), multidimensional databases, data warehouses	Pilot, Comshare, Arbor, Cognos, Microstrategy	Retrospective, dynamic data delivery at multiple levels
Data Mining (Emerging Today)	"What’s likely to happen to Boston unit sales next month? Why?"	Advanced algorithms, multiprocessor computers, massive databases	Pilot, Lockheed, IBM, SGI, numerous startups (nascent industry)	Prospective, proactive information delivery

Table 1. Steps in the Evolution of Data Mining.

The core components of data mining technology have been under development for decades, in research areas such as statistics, artificial intelligence, and machine learning. Today, the maturity of these techniques, coupled with high-performance relational database engines and broad data integration efforts, make these technologies practical for current data warehouse environments.

The Scope of Data Mining

Data mining derives its name from the similarities between searching for valuable business information in a large database — for example, finding linked products in gigabytes of store scanner data — and mining a mountain for a vein of valuable ore. Both processes require either sifting through an immense amount of material, or intelligently probing it to find exactly where the value resides. Given databases of sufficient size and quality, data mining technology can generate new business opportunities by providing these capabilities:

Automated prediction of trends and behaviors.

Data mining automates the process of finding predictive information in large databases. Questions that traditionally required extensive hands-on analysis can now be answered directly from the data — quickly. A typical example of a predictive problem is targeted marketing. Data mining uses data on past promotional mailings to identify the targets most likely to maximize return on investment in future mailings. Other predictive problems include forecasting bankruptcy and other forms of default, and identifying segments of a population likely to respond similarly to given events.

Automated discovery of previously unknown patterns.

Data mining tools sweep through databases and identify previously hidden patterns in one step. An example of pattern discovery is the analysis of retail sales data to identify seemingly unrelated products that are often purchased together. Other pattern discovery problems include detecting fraudulent credit card transactions and identifying anomalous data that could represent data entry keying errors.

Data mining techniques can yield the benefits of automation on existing software and hardware platforms, and can be implemented on new systems as existing platforms are upgraded and new products developed. When data mining tools are implemented on high performance parallel processing systems, they can analyze massive databases in minutes. Faster processing means that users can automatically experiment with more models to understand complex data. High speed makes it practical for users to analyze huge quantities of data. Larger databases, in turn, yield improved predictions.

Databases can be larger in both depth and breadth:

More columns. Analysts must often limit the number of variables they examine when doing hands-on analysis due to time constraints. Yet variables that are discarded because they seem unimportant may carry information about unknown patterns. High performance data mining allows users to explore the full depth of a database, without preselecting a subset of variables.

More rows. Larger samples yield lower estimation errors and variance, and allow users to make inferences about small but important segments of a population.

A recent Gartner Group Advanced Technology Research Note listed data mining and artificial intelligence at the top of the five key technology areas that "will clearly have a major impact across a wide range of industries within the next 3 to 5 years."2 Gartner also listed parallel architectures and data mining as two of the top 10 new technologies in which companies will invest during the next 5 years. According to a recent Gartner HPC Research Note, "With the rapid advance in data capture, transmission and storage, large-systems users will increasingly need to implement new and innovative ways to mine the after-market value of their vast stores of detail data, employing MPP [massively parallel processing] systems to create new sources of business advantage (0.9 probability)."3

The most commonly used techniques in data mining are:

Artificial neural networks: Non-linear predictive models that learn through training and resemble biological neural networks in structure.

Decision trees: Tree-shaped structures that represent sets of decisions. These decisions generate rules for the classification of a dataset. Specific decision tree methods include Classification and Regression Trees (CART) and Chi Square Automatic Interaction Detection (CHAID) .

Genetic algorithms: Optimization techniques that use processes such as genetic combination, mutation, and natural selection in a design based on the concepts of evolution.

Nearest neighbor method: A technique that classifies each record in a dataset based on a combination of the classes of the k record(s) most similar to it in a historical dataset (where k ³ 1). Sometimes called the k-nearest neighbor technique.

Rule induction: The extraction of useful if-then rules from data based on statistical significance.

Many of these technologies have been in use for more than a decade in specialized analysis tools that work with relatively small volumes of data. These capabilities are now evolving to integrate directly with industry-standard data warehouse and OLAP platforms. The appendix to this white paper provides a glossary of data mining terms.

How Data Mining Works

How exactly is data mining able to tell you important things that you didn't know or what is going to happen next? The technique that is used to perform these feats in data mining is called modeling. Modeling is simply the act of building a model in one situation where you know the answer and then applying it to another situation that you don't. For instance, if you were looking for a sunken Spanish galleon on the high seas the first thing you might do is to research the times when Spanish treasure had been found by others in the past. You might note that these ships often tend to be found off the coast of Bermuda and that there are certain characteristics to the ocean currents, and certain routes that have likely been taken by the ship’s captains in that era. You note these similarities and build a model that includes the characteristics that are common to the locations of these sunken treasures. With these models in hand you sail off looking for treasure where your model indicates it most likely might be given a similar situation in the past. Hopefully, if you've got a good model, you find your treasure.

This act of model building is thus something that people have been doing for a long time, certainly before the advent of computers or data mining technology. What happens on computers, however, is not much different than the way people build models. Computers are loaded up with lots of information about a variety of situations where an answer is known and then the data mining software on the computer must run through that data and distill the characteristics of the data that should go into the model. Once the model is built it can then be used in similar situations where you don't know the answer. For example, say that you are the director of marketing for a telecommunications company and you'd like to acquire some new long distance phone customers. You could just randomly go out and mail coupons to the general population - just as you could randomly sail the seas looking for sunken treasure. In neither case would you achieve the results you desired and of course you have the opportunity to do much better than random - you could use your business experience stored in your database to build a model.

As the marketing director you have access to a lot of information about all of your customers: their age, sex, credit history and long distance calling usage. The good news is that you also have a lot of information about your prospective customers: their age, sex, credit history etc. Your problem is that you don't know the long distance calling usage of these prospects (since they are most likely now customers of your competition). You'd like to concentrate on those prospects who have large amounts of long distance usage. You can accomplish this by building a model. Table 2 illustrates the data used for building a model for new customer prospecting in a data warehouse.

	Customers	Prospects
General information (e.g. demographic data)	Known	Known
Proprietary information (e.g. customer transactions)	Known	Target

Table 2 - Data Mining for Prospecting

The goal in prospecting is to make some calculated guesses about the information in the lower right hand quadrant based on the model that we build going from Customer General Information to Customer Proprietary Information. For instance, a simple model for a telecommunications company might be:

98% of my customers who make more than $60,000/year spend more than $80/month on long distance

This model could then be applied to the prospect data to try to tell something about the proprietary information that this telecommunications company does not currently have access to. With this model in hand new customers can be selectively targeted.

Test marketing is an excellent source of data for this kind of modeling. Mining the results of a test market representing a broad but relatively small sample of prospects can provide a foundation for identifying good prospects in the overall market. Table 3 shows another common scenario for building models: predict what is going to happen in the future.

	Yesterday	Today	Tomorrow
Static information and current plans (e.g. demographic data, marketing plans)	Known	Known	Known
Dynamic information (e.g. customer transactions)	Known	Known	Target

Table 3 - Data Mining for Predictions

If someone told you that he had a model that could predict customer usage how would you know if he really had a good model? The first thing you might try would be to ask him to apply his model to your customer base - where you already knew the answer. With data mining, the best way to accomplish this is by setting aside some of your data in a vault to isolate it from the mining process. Once the mining is complete, the results can be tested against the data held in the vault to confirm the model’s validity. If the model works, its observations should hold for the vaulted data.

An Architecture for Data Mining

To best apply these advanced techniques, they must be fully integrated with a data warehouse as well as flexible interactive business analysis tools. Many data mining tools currently operate outside of the warehouse, requiring extra steps for extracting, importing, and analyzing the data. Furthermore, when new insights require operational implementation, integration with the warehouse simplifies the application of results from data mining. The resulting analytic data warehouse can be applied to improve business processes throughout the organization, in areas such as promotional campaign management, fraud detection, new product rollout, and so on. Figure 1 illustrates an architecture for advanced analysis in a large data warehouse.

Figure 1 - Integrated Data Mining Architecture

The ideal starting point is a data warehouse containing a combination of internal data tracking all customer contact coupled with external market data about competitor activity. Background information on potential customers also provides an excellent basis for prospecting. This warehouse can be implemented in a variety of relational database systems: Sybase, Oracle, Redbrick, and so on, and should be optimized for flexible and fast data access.

An OLAP (On-Line Analytical Processing) server enables a more sophisticated end-user business model to be applied when navigating the data warehouse. The multidimensional structures allow the user to analyze the data as they want to view their business – summarizing by product line, region, and other key perspectives of their business. The Data Mining Server must be integrated with the data warehouse and the OLAP server to embed ROI-focused business analysis directly into this infrastructure. An advanced, process-centric metadata template defines the data mining objectives for specific business issues like campaign management, prospecting, and promotion optimization. Integration with the data warehouse enables operational decisions to be directly implemented and tracked. As the warehouse grows with new decisions and results, the organization can continually mine the best practices and apply them to future decisions.

This design represents a fundamental shift from conventional decision support systems. Rather than simply delivering data to the end user through query and reporting software, the Advanced Analysis Server applies users’ business models directly to the warehouse and returns a proactive analysis of the most relevant information. These results enhance the metadata in the OLAP Server by providing a dynamic metadata layer that represents a distilled view of the data. Reporting, visualization, and other analysis tools can then be applied to plan future actions and confirm the impact of those plans.

Profitable Applications

A wide range of companies have deployed successful applications of data mining. While early adopters of this technology have tended to be in information-intensive industries such as financial services and direct mail marketing, the technology is applicable to any company looking to leverage a large data warehouse to better manage their customer relationships. Two critical factors for success with data mining are: a large, well-integrated data warehouse and a well-defined understanding of the business process within which data mining is to be applied (such as customer prospecting, retention, campaign management, and so on).

Some successful application areas include:

A pharmaceutical company can analyze its recent sales force activity and their results to improve targeting of high-value physicians and determine which marketing activities will have the greatest impact in the next few months. The data needs to include competitor market activity as well as information about the local health care systems. The results can be distributed to the sales force via a wide-area network that enables the representatives to review the recommendations from the perspective of the key attributes in the decision process. The ongoing, dynamic analysis of the data warehouse allows best practices from throughout the organization to be applied in specific sales situations.
A credit card company can leverage its vast warehouse of customer transaction data to identify customers most likely to be interested in a new credit product. Using a small test mailing, the attributes of customers with an affinity for the product can be identified. Recent projects have indicated more than a 20-fold decrease in costs for targeted mailing campaigns over conventional approaches.
A diversified transportation company with a large direct sales force can apply data mining to identify the best prospects for its services. Using data mining to analyze its own customer experience, this company can build a unique segmentation identifying the attributes of high-value prospects. Applying this segmentation to a general business database such as those provided by Dun & Bradstreet can yield a prioritized list of prospects by region.
A large consumer package goods company can apply data mining to improve its sales process to retailers. Data from consumer panels, shipments, and competitor activity can be applied to understand the reasons for brand and store switching. Through this analysis, the manufacturer can select promotional strategies that best reach their target customer segments.

Each of these examples have a clear common ground. They leverage the knowledge about customers implicit in a data warehouse to reduce costs and improve the value of customer relationships. These organizations can now focus their efforts on the most important (profitable) customers and prospects, and design targeted marketing strategies to best reach them.

Data Mining Algorithms (Analysis Services - Data Mining)

The data mining algorithm is the mechanism that creates a data mining model. To create a model, an algorithm first analyzes a set of data and looks for specific patterns and trends. The algorithm uses the results of this analysis to define the parameters of the mining model. These parameters are then applied across the entire data set to extract actionable patterns and detailed statistics.

The mining model that an algorithm creates can take various forms, including:

A set of rules that describe how products are grouped together in a transaction.
A decision tree that predicts whether a particular customer will buy a product.
A mathematical model that forecasts sales.
A set of clusters that describe how the cases in a dataset are related.

Microsoft SQL Server Analysis Services provides several algorithms for use in your data mining solutions. These algorithms are a subset of all the algorithms that can be used for data mining. You can also use third-party algorithms that comply with the OLE DB for Data Mining specification

Types of Data Mining Algorithms

Analysis Services includes the following algorithm types:

Classification algorithms predict one or more discrete variables, based on the other attributes in the dataset. An example of a classification algorithm is the Microsoft Decision Trees Algorithm.
Regression algorithms predict one or more continuous variables, such as profit or loss, based on other attributes in the dataset. An example of a regression algorithm is the Microsoft Time Series Algorithm.
Segmentation algorithms divide data into groups, or clusters, of items that have similar properties. An example of a segmentation algorithm is the Microsoft Clustering Algorithm.
Association algorithms find correlations between different attributes in a dataset. The most common application of this kind of algorithm is for creating association rules, which can be used in a market basket analysis. An example of an association algorithm is the Microsoft Association Algorithm.
Sequence analysis algorithms summarize frequent sequences or episodes in data, such as a Web path flow.

Conclusion

Comprehensive data warehouses that integrate operational data with customer, supplier, and market information have resulted in an explosion of information. Competition requires timely and sophisticated analysis on an integrated view of the data. However, there is a growing gap between more powerful storage and retrieval systems and the users’ ability to effectively analyze and act on the information they contain. Both relational and OLAP technologies have tremendous capabilities for navigating massive data warehouses, but brute force navigation of data is not enough. A new technological leap is needed to structure and prioritize information for specific end-user problems. The data mining tools can make this leap. Quantifiable business benefits have been proven through the integration of data mining with current information systems, and new products are on the horizon that will bring this integration to an even wider audience of users.

COMPUTING THE nth FIBONACCI

2009-10-21T07:30:00.001-07:00

COMPUTING THE nth FIBONACCI NUMBER

PROBLEM:

Given a number n generate the nth member of the Fibonacci sequence.

AIM:

To generate the nth Fibonacci number.

PROGRAM DESCRIPTION:

F1=-1

F2=1

-1 value is used in Fibonacci series.

F3=f1+f2; →1

F1=f2;

F2=f3;

From equ1 converting equ1 to general form,

F3→fn (generalized form)

F1→f3-f2

Since f3 is repeated in terms of fn.

F2→f3-1→fn-1

Therefore final solution of fn=fn-1+fn-2;

Fibonacci: 0 1 1 2 3 5 8 13 21 24

Index : 1 2 3 4 5 6 7 8 9 10

Example:

F4=2

F5=3

It is possible to get the next element.

F6=f4+f5 →2

It is possible to get f7 from f5 and f6.

F7=f6+f5 →3

From equ3 substitute f7=[f4+f5]+f5 →4

F8=f7+f6 →5

From equ2 substitute

F6=f4+f5

From equ4 substitute

F7=[f4+f5]+f5

Here, the result can be stored in equ5.

F8=[(f4+f5)+f5]+[f4+f5]

F8=3f5+2f4

Here, the equ starts from f4 and by doubling, then stop at f8.

F8=3*3+2*2

F8=13;

From this find the f2n value.

F8=f5²+f4²

Now in generalised form

F2n=fn+1²+fn²

F2n=fnp1

↓

f2n=fnp1*fnp1

fn*fn

based on proof by induction,

f2n+1=2+fn+fn+1+fn+1²

f2np1=2*fn*fn+1+fn+1*fnp1;

ALGORITHM DESCRIPTION:

Initialize n, then indicating the nth Fibonacci number is to be required.

Derive the binary representation of n

by repeated division by 2 and store the

current element in array d[1.....i-1].

Initialize the first two members of the doubling sequence.

Step by step from (p-1) th most significant digit in the binary representation of n to 1.

Then use present set of Fibonacci number. To generate the set f2n and f2n+1.
If the present binary digit d[k] is zero, then make the reassignment to fn and fn+1.
Else extend the sequence by 1 number and then make the reassignment to fn and fn+1.

The first Fibonacci numbers are

1 1 2 3 5 8 13 21 24

IMPLEMENTATION:

#include<stdio.h>

#include<conio.h>

void main( )

{

int n,i=0;

while(n>1)

{

i=i+1;

if odd(n) then

d[i]=1;

else

d[i]=0;

n=n/2;

}

for(k=i-1;k≤1;k--)

{

sq fnp1=fnp1*fnp1;

f2n=fn*fn+sq fnp1;

f2np1=2*fn*fnp1+sq fnp1;

if d[k]=0

{

fn=f2n;

fnp1=f2np1;

}

else

{

fn=f2np1;

fnp1=f2np1+f2n;

}

APPLICATION:

It is used in computation methods.

It is used to find the Fibonacci series.

Design and analyses of algorithm

2009-10-21T07:26:00.001-07:00

Kth smallest element in an array:

Aim:

Write a program to find the Kth smallest element in array(we need to find two minimum’s)

Program implementation:

I/p:

IF K=1, O/P=3

IF K=2, O/P=4

Ist pass:

min

Set 1^st element as min:

(Compare min to I ‘<‘ or not. If lesser interchange both)

Min i

I < min (min=i)

Min I

Condition satisfied

Min I

CONDITION NOT SATISFIED

Min I

CONDITION NOT SATISFIED

IInd pass

Min I

═

Condition satisfied

Min I

Condition not satisfied

Min I

CONDITION SATISFIED (MIN=I)

IIIrd pass:

Min I

▬▬▬

CONDITION NOT SATISFIED

Min I

CONDITION SATISFIED

(MIN =I)

Min I

IVth pass:

Min I

▬▬▬▬▬▬

Condition satisfied

Min I

▬▬▬▬▬▬▬▬

Algorithm:

Step 1: set the given no’s in sorted order

Step 2: set the first element as min

Step 3: compare min to next to next elements

Step 4: if it’s ‘<’ than min,swap the both elements through the temporary element

Step 5: Then i++ the array element.

Step 6: compare the other elements in this same order. Then we find the smallest element in an array.

Coding:

Void main()

{

Int a[15],temp,k,n,i,j,min;

Printf(“enter the no of elements”);

Scanf(“%d”,&n);

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

Printf(“enter the elements’);

Scanf(“%d”,&k);

For(i=0;i<k-1;i++)

{

Min=a[0];

For(j=i++;j<n;j++)

If(a[i]<min)

{

Min=a[j];

T=a[j];

A[i]=a[j];

A[i]=t;

Printf(“%d”,a[k-1];

}}

Queston 2: Find the Kth largest element in an array.

Aim: write a program to find the largest element in an array.

Program implementation:

(Set 1^st element as ‘max’,&compare with next to next elements with condition ‘>’ or not if condition satisfied swap both element.)

I/P: Max I

O/P: IF K=1, 60

IF K=2, 50

Ist pass:

Max I

(not satisfied)

Max I

60>50,CONDITION SATISFIED. (MAX=I)

Max I

NOT SATISFIED

Max I

NOT SATISFIED

2^ND PASS: Max I

Satisfied. ▬▬

Max i

Not satisfied

Max i

Not satisfied.

3^rd pass:

Max i

Not satisfied. ▬▬▬▬▬

Max i

Satisfied.

4^th pass:

Max i

Satisfied. ▬▬▬▬▬▬▬

max

▬▬▬▬▬▬▬▬▬

Algorithm:

Step 1: set arrays first element as ‘max’.

Step 2: compare that element with ‘I th’ element.

Step 3: if I > max swap the both values through temporary element.

Step 4then compare other element,s with max if condition not satisfied i++ the array element

Step 5:after that all comparition the kth largest element will be found.

Coding:

Void main()

{

Int a[15],temp,k,n,i,j,max;

Printf(“enter the no of elements”);

Scanf(“%d”,&n);

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

Printf(“enter the elements’);

Scanf(“%d”,&k);

For(i=0;i<k-1;i++)

{

Max=a[0];

For(j=i++;j<n;j++)

If(a[i]>max)

{

Max=a[j];

T=a[j];

A[i]=a[j];

A[i]=t;

Printf(“%d”,a[k-1];

}}

assignment

2009-10-21T07:20:00.001-07:00

SERVERS AND WEBSERVERS….

Server :

(ser´ver) (n.) A computer or device on a network that manages network resources. For example, a file server is a computer and storage device dedicated to storing files. Any user on the network can store files on the server.

A print server is a computer that manages one or more printers, and a network server is a computer that manages network traffic. A database server is a computer system that processes database queries.

Definition of server :

A server is an application running on a computer that delivers a service. For example, a web server will deliver web pages when requested by a browser (called client in this context). The way a server and a client dialogs is called a protocol. For instance, HTTP is the protocol used between a browser an a web server.

Among the many services provided by the Internet servers are:

* World Wide Web

* the domain name system

* e-mail

* FTP file transfer

* chat and instant messaging

* voice communication

* streaming audio and video

* online gaming

Virtually every action taken by an ordinary Internet user requires one or more interactions with one or more servers.

Servers in daily life :

A server is any combination of hardware or software designed to provide services to clients.

A server is a computer that handles requests for data, email, file transfers, and other network services from other computers (ie, clients).

A computer that stores application and data files for all workstations on a network; also referred to as a file server.

A server is the computer program (housed in a computer) that serves requested HTML pages or files by the client.

A server is a computer that stores information, and "serves" that information to viewers who request to see it. Everything that you see on the Internet is stored somewhere on a server.

A computer or application, that provides a service to client software on other computers. Servers are used for web hosting and other web applications.

Types of server :

Application server.
Communication server.
Datebase server.
Fax server.
File server.
Game server.
Home server.
Name server.
Print server.
Proxy server.
Sound server.
Standalone server.
Web server.
Web feed server.
Client server.
Catalog server.

Web Server :

(1) A computer program that serves the requested files which form web pages to the client's browser.

(2) A web server can also refer to the computer that runs the server software and holds the files for one or more websites.

Historical notes :

In 1989 Tim Berners-Lee proposed to his employer CERN (European Organization for Nuclear Research) a new project, which had the goal of easing the exchange of information between scientists by using a hypertext system. As a result of the implementation of this project, in 1990 Berners-Lee wrote two programs:

* a browser called WorldWideWeb;

* the world's first web server, later known as CERN HTTPd, which ran on NeXTSTEP.

The world's first web server

Between 1991 and 1994 the simplicity and effectiveness of early technologies used to surf and exchange data through the World Wide Web helped to port them to many different operating systems and spread their use among lots of different social groups of people, first in scientific organizations, then in universities and finally in industry.

Common features :

1. Virtual hosting to serve many web sites using one IP address.

2. Large file support to be able to serve files whose size is greater than 2 GB on 32 bit OS.

3. Bandwidth throttling to limit the speed of responses in order to not saturate the network and to be able to serve more clients.

A home web server

Load limits

A web server (program) has defined load limits, because it can handle only a limited number of concurrent client connections (usually between 2 and 80,000, by default between 500 and 1,000) per IP address (and TCP port) and it can serve only a certain maximum number of requests per second depending on:

* its own settings;

* the HTTP request type;

* content origin (static or dynamic);

* the fact that the served content is or is not cached;

* the hardware and software limits of the OS where it is working.

When a web server is near to or over its limits, it becomes overloaded and thus unresponsive.

Kernel-mode and user-mode web servers :

A web server can be either implemented into the OS kernel, or in user space (like other regular applications).

An in-kernel web server (like TUX on Linux or Microsoft IIS on Windows) will usually work faster because, as part of the system, it can directly use all the hardware resources it needs, such as:

* non-paged memory;

* CPU time-slices;

* network adapters buffers.

Web servers that run in user-mode have to ask the system the permission to use more memory or more CPU resources. Not only these requests to the kernel take time, but they are not always satisfied because the system reserves resources for its own usage and has the responsibility to share hardware resources with all the other running applications.

Also applications cannot access the system internal buffers, which is causing useless buffer copies that create another handicap for user-mode web servers.

Overload causes :

At any time web servers can be overloaded because of:

* Too much legitimate web traffic (i.e. thousands or even millions of clients hitting the web site in a short interval of time. e.g. Slashdot effect);

* DDoS (Distributed Denial of Service) attacks;

* Computer worms that sometimes cause abnormal traffic because of millions of infected computers (not coordinated among them);

* XSS viruses can cause high traffic because of millions of infected browsers and/or web servers;

* Internet web robots traffic not filtered/limited on large web sites with very few resources (bandwidth, etc.);

* Internet (network) slowdowns, so that client requests are served more slowly and the number of connections increases so much that server limits are reached;

Market structure

Given below is a list of top Web server software vendors published in a Netcraft survey in January 2009.

Market share of major web servers

Vendor	Product	Web Sites Hosted	Percent
Apache	Apache	96,531,033	52.05%
Microsoft	IIS	61,023,474	32.90%
Google	GWS	9,864,303	5.32%
nginx	nginx	3,462,551	1.87%
lighttpd	lighttpd	2,989,416	1.61%
Oversee	Oversee	1,847,039	1.00%
Others	-	9,756,650	5.26%
Total	-	185,474,466	100.00%

Application :

* Your local website behaves more like the live one. For example, you can configure directory security, test your custom error pages etc before commiting them to the production environment.

* You can use server-side scripting languages such as PHP and ColdFusion.

* Allows you to standardize your coding. For example, you can use root-relative paths for your image references and hyperlinks (i.e. "/directory/image.gif"). In other words, your paths can represent the website structure, rather than the directory structure of your computer.

* Knowledge. The knowledge you gain from using your own web server will help you understand how it works in the live environment. This will most certainly help you when you need to communicate with your hosting provider - you'll be able to use terminology that makes it easier for them to understand your request/issue.

Advantages and Disadvantages :

Advantages :

Cheap : Cost and Affordable Price:Available at Most Affordable Cost. Today thousands of Companies Offering at Very Cheap Prices.Most Common Option In the Industry. Its Market Share is Also High as Compared to Other Host Options.

No Maintenance Cost:It Comes with All Inclusive Price.You would like Not Bother About Server Maintenance and Setup

Fast Setup : In Case of Shared Host Your Site Could Be Live With in 24 Hours of Purchase.Unlike Dedicated Host it Could Setup Instantly.No need to be a Technically Sound Person.

Good For Small Sites : and :It is the Best Option For Beginners and Small Websites.

Disadvantages :

Security issues :Security is one Of Main Disadvantage.

Backup Process is Very Hard Task As the thousands of Websites Hosted on Same Web Server.Security is one of chief disadvantage of Shared Hosting. Backup Process is exceptionally hard task as the thousands of Web sites Hosted on same Web Server.

Limited Resources:

Thousands Of Web Sites Using Same Resources.That's Why If One User Site consumes More Resources of web Server Other Sites Might Slow Down.In Other Way One Problematic Website May Cause Crash of All Other Sites in the Same Server.

Dynamic IP:

Many Providers Does not Give Static ip For Shared Website Hosting. Dynamic ip is outstandingly risk when You Going for E-commerce Transactions On Your WebSite.This

Disadvantage Could Overcome By Choosing Static iP.Some Companies Gives a Option to Choose Static or Dynamic IP. They Will Charge You Small Amount for Static IP.

Not good For Large Data Base E-Commerce Sites:

Large Websites Need Plenty of Server Resources.So They are not Suitable of it. Final Word: No Doubt It Has Major Share in Industry. But Before You Going to Buy a Shared host Plan, You Must Know Your Requirements.Then Proceed. Best of Luck..

2009-10-21T07:14:00.000-07:00

THE TWO-WAY MERGE SORT

AIM:

Merge two arrays with their elements in ascending order into a

single ordered array

PROBLEM DESCRIPTION:

RULE:1)The elements of both the input arrays should be in sorted form

2)the size of the merged array should be c=m+n ie(size

of A array+size of B array)

INPUT:A: 5 6 7 8 9

B: 1 2 3 4 5

OUTPUT:C:1 2 3 4 5 5 6 7 8 9

m: Size of A array

n:size of B array

ALGORITHM DEVELOPMENT:

We need to merge the two array elements in ascending order

into a single ordered array. We will discuss this in three scenarios

1scenario:

i/p A: 1 2 3 4 5

B: 5 6 7 8 9

If the last element of the first array is lesser than or equal to the

first element of the second array then copy the contents of A array

to C array and from m+1 location onwards copy the contents of B array

o/p C:1 2 3 4 5 5 6 7 8 9

2scenario:

i/p A:5 6 7 8 9

B:1 2 3 4 5

If the last element of the second array is lesser than or equal to

the first element of the first array then copy the contents of B array

to C array and from n+1 location onwards copy the contents of A array

o/p C:1 2 3 4 5 5 6 7 8 9

3scenario:

i/p A:1 2 3 4 5

B:2 5 6 7 8

Maintain two indexes i and j for A and B array.Compare i and j if

A[i]

C and update j.If there are still more elements after completion of an

array then copy the remaining contents of the array to C array.

o/p C:1 2 2 3 4 5 5 6 7 8

ALGORITHM:

1scenario:

1)Read both the arrays A and B

2)If last A element is less than or equal to the first B element then

copy the contents of A to C and from m+1th location onwards copy the

contents of B

3)Return the merged result

2scenario:

1)Read both the arrays A and B

2)If last B element is less than or equal to the first A element then

copy the contents of B to C and from n+1th location onwards copy the

contents of A

3)Return the merged result

3scenario:

1)Read both the arrays A and B

2)Maintain two indexes i and j for A and B array.

3)Compare i and j if A[i]

B[j]

4)If there are still more elements after completion of an array then

copy the remaining contents of the array to C array.

IMPLEMENTATION:

#include

int firstarray( );

int secondarray( );

int compare( );

int a[10],b[10],c[20],i,n,n1,n3;

void main( )

{

printf("enter the elements for A array:");

scanf("%d",&n);

for(i=0;i

scanf("%d",&a[i]);

printf("enter the elements for B array:");

scanf("%d",&n1);

for(i=0;i

scanf("%d",&b[i]);

n3=n+n1;

if(a[n-1]<=b[0])

firstarray( );

else if(b[n1-1]<=a[0])

secondarray( );

else

compare( );

for(i=0;i

printf("%d",c[i]);

getch( );

}

int firstarray( )

{

printf("firstcase \n");

int j;

for(i=0;i

c[i]=a[i];

j=0;

while(j

{

c[i]=b[j];

j++;

i++;

}

return(0);

}

int secondarray( )

{

printf("secondcase \n");

int j;

for(i=0;i

c[i]=b[i];

j=0;

while(j

{

c[i]=a[j];

j++;

i++;

}

return(0);

}

int compare( )

{

printf("comparecase \n");

int j=0,k=o;

i=-1;

while(j

{

i++;

if(a[j]

{

c[i]=a[j];

j++;

}

else

{

c[i]=b[k];

k++;

}

while(j

{

i++;

c[i]=a[j];

j++;

}

while(k

{

i++;

c[i]=b[k];

k++;

}

retuen(0);

}

APPLICATION:

SORTING,TAPE SORTING,DATA PROCESSING.

Design and analysis of algorithm

2009-10-21T06:56:00.001-07:00

Exchanging of two variables

Exchanging of two variables:

1. without using temporary variable,

2. using temporary variable,

3. using arithmetic operators

Problem description:

Given two variables a and b,

Exchange the values of both a and b.

Algorithm development:

Now the two values of a and b is exchanged without using the temporary variable.

1.The value of a is assigned to value of b.

2.the sum(a+b) is stored in the variable a.

Hence a=a+b;

3. the difference (a-b) is stored in the variable b.

4. again the difference (a-b) is stored in the variable a.

The values of a and b are exchanged without using temporary variable.

Program coding:

#include<stdio.h>

#include<conio.h>

void main()

{

int a,b;

printf("\n Enter the 2 numbers");

scanf("%d%d",&a,&b);

//swapping of 2 numbers without using temp variable

a=a+b;

b=a-b;

a=a-b;

printf("\n A = %d \n B = %d\n");

getch();

}

2. with using temporary variables:

Now the two variables a,b are assigned to the temporary variable t.

The value of a is assigned to the value of b.

a=b;

The value of b is stored in the value of temporary variable t.

b=t;

3. Now the value which is assigned to the temporary variable t is stored in a.

t=a;

program coding:

#include<stdio.h>

#include<conio.h>

void main()

{

int a,b,t;

printf("\n enter the values of a,b");

scanf("%d",&a,&b);

t=a;

a=b;

b=t;

printf("%d",&t);

getch();

}

Application Server

2009-10-21T06:53:00.001-07:00

Application Server

What is Application Server ?

An application server is a component-based product that resides in the middle-tier of a server centric architecture. It provides middleware services for security and state maintenance, along with data access and persistence.

Java application servers are based on the Java™ 2 Platform, Enterprise Edition (J2EE™). J2EE uses a multi-tier distributed model. This model generally includes a Client Tier, a Middle Tier, and an EIS Tier. The Client Tier can be one or more applications or browsers. The J2EE Platform is in the Middle Tier and consists of a Web Server and an EJB Server. (These servers are also called "containers.") There can be additional sub-tiers in the middle tier. The Enterprise Information System (EIS) tier has the existing applications, files, and databases.

For the storage of business data, the J2EE platform requires a database that is accessible through the JDBC, SQLJ, or JDO API. The database may be accessible from web components, enterprise beans, and application client components. The database need not be accessible from applets.

Types of application servers:

The simplest forms of servers are disk servers and file servers. With a file server, the client passes requests for files or file records over a network to the file server. This form of data service requires large bandwidth and can slow a network with many users down considerably. Traditional LAN computing allows users to share resources, such as data files and peripheral devices, by moving them from standalone PCUs onto a Networked File Server (NFS). The more advanced form of servers are database servers, transaction server and application servers.In database servers, clients passes SQL (Structured Query Language) requests as messages to the server and the results of the query are returned over the network. The code that processes the SQL request and the data resides on the server allowing it to use its own processing power to find the requested data, rather than pass all the records back to a client and let it find its own data as was the case for the file server. In transaction servers, clients invoke remote procedures that reside on servers which also contains an SQL database engine. There are procedural statements on the server to execute a group of SQL statements (transactions) which either all succeed or fail as a unit. The applications based on transaction servers are called On-line Transaction Processing (OLTP) and tend to be mission-critical applications which require 1-3 second response time, 100% of the time and require tight controls over the security and integrity of the database. The communication overhead in this approach is kept to a minimum as the exchange typically consists of a single request/reply (as opposed to multiple SQL statements in database servers). Application servers are not necessarily database centered but are used to server user needs, such as. download capabilities from Dow Jones or regulating a electronic mail process. Basing resources on a server allows users to share data, while security and management services, which are also based in the server, ensure data integrity and security.

When an application server should be used ?

You should consider an application server when you have a need for:

Integration with existing systems and databases
Web site support

Secondary reasons to use application servers derive from the primary reasons. A few secondary reasons are:

E-Commerce
Web-integrated collaboration
Component re-use.
One way to look at application servers is that they are a formalization of a solution to a problem that has been around for a long time. That problem can characterized as a need to create an integrated presentation and processing environment for existing systems and databases. The presentation has pretty much been decided with browsers now being the dominant interface. This is why you usually see a Web server paired with or included in an application server. The integrated processing has been moving towards components for some time. Application servers provide containers for such components along with application program interfaces (APIs) to support the components. These APIs are to the existing systems and databases.

ow does an application server work:

It would be interesting to consider what's inside of the application server and how it works. Some of the basic functionalities of an application server are transaction management, data persistence, object pooling, socket handling, and request handling. The flow between these responsibilities is seen in Figure 4. There are various components that handle these functionalities. These components need to synchronize the threads within the application server, in order to manage and maintain the sanctity of data and operations on them. This synchronization, although beneficial and necessary for the proper functioning of the application server, acts as a limitation at higher loads, even when there are enough hardware resources.

LAVANYA

2009-10-21T06:48:00.001-07:00

NETWORKING

What is a Network?

A network consists of two or more computers that are linked in order to share resources (such as printers and CDs), exchange files, or allow electronic communications. The computers on a network may be linked through cables, telephone lines, radio waves, satellites, or infrared light beams.

The two basic types of networks include:

You may also see references to a Metropolitan Area Networks (MAN), a Wireless LAN (WLAN), or a Wireless WAN (WWAN).

Local Area Network

A Local Area Network (LAN) is a network that is confined to a relatively small area. It is generally limited to a geographic area such as a writing lab, school, or building. Rarely are LAN computers more than a mile apart.

In a typical LAN configuration, one computer is designated as the file server. It stores all of the software that controls the network, as well as the software that can be shared by the computers attached to the network. Computers connected to the file server are called workstations. The workstations can be less powerful than the file server, and they may have additional software on their hard drives. On many LANs, cables are used to connect the network interface cards in each computer; other LANs may be wireless. See the Topology, Cabling, and Hardware sections of this tutorial for more information on the configuration of a LAN.

Wide Area Network

Wide Area Networks (WANs) connect larger geographic areas, such as Florida, the United States, or the world. Dedicated transoceanic cabling or satellite uplinks may be used to connect this type of network.

Using a WAN, schools in Florida can communicate with places like Tokyo in a matter of minutes, without paying enormous phone bills. A WAN is complicated. It uses multiplexers to connect local and metropolitan networks to global communications networks like the Internet. To users, however, a WAN will not appear to be much different than a LAN.

Advantages of Installing a School Network

Speed. Networks provide a very rapid method for sharing and transferring files. Without a network, files are shared by copying them to memory cards or discs, then carrying or sending the discs from one computer to another. This method of transferring files (referred to as sneaker-net) can be very time-consuming.
Cost. Network able versions of many popular software programs are available at considerable savings when compared to buying individually licensed copies.
Security. Files and programs on a network can be designated as "copy inhibit," so that you do not have to worry about illegal copying of programs. Also, passwords can be established for specific directories to restrict access to authorized users.
Centralized Software Management. One of the greatest benefits of installing a network at a school is the fact that all of the software can be loaded on one computer (the file server). This eliminates that need to spend time and energy installing updates and tracking files on independent computers throughout the building.
Resource Sharing. Sharing resources is another advantage of school networks. Most schools cannot afford enough laser printers, fax machines, modems, scanners, and CD players for each computer. However, if these or similar peripherals are added to a network, they can be shared by many users.
Electronic Mail. The presence of a network provides the hardware necessary to install an e-mail system. E-mail aids in personal and professional communication for all school personnel, and it facilitates the dissemination of general information to the entire school staff. Electronic mail on a LAN can enable students to communicate with teachers and peers at their own school. If the LAN is connected to the Internet, students can communicate with others throughout the world.
Flexible Access. School networks allow students to access their files from computers throughout the school. Students can begin an assignment in their classroom, save part of it on a public access area of the network, then go to the media center after school to finish their work. Students can also work cooperatively through the network.
Workgroup Computing. Collaborative software allows many users to work on a document or project concurrently. For example, educators located at various schools within a county could simultaneously contribute their ideas about new curriculum standards to the same document, spreadsheets, or website.

Disadvantages of Installing a School Network

Expensive to Install. Although a network will generally save money over time, the initial costs of installation can be prohibitive. Cables, network cards, routers, and software are expensive, and the installation may require the services of a technician.
Requires Administrative Time. Proper maintenance of a network requires considerable time and expertise. Many schools have installed a network, only to find that they did not budget for the necessary administrative support.
File Server May Fail. Although a file server is no more susceptible to failure than any other computer, when the files server "goes down," the entire network may come to a halt. When this happens, the entire school may lose access to necessary programs and files.
Cables May Break. The Topology chapter presents information about the various configurations of cables. Some of the configurations are designed to minimize the inconvenience of a broken cable; with other configurations, one broken cable can stop the entire network.
Must Monitor Security Issues. Wireless networks are becoming increasingly common; however, security can be an issue with wireless networks.

What is a Protocol?

A protocol is a set of rules that governs the communications between computers on a network. In order for two computers to talk to each other, they must be speaking the same language. Many different types of network protocols and standards are required to ensure that your computer (no matter which operating system, network card, or application you are using) can communicate with another computer located on the next desk or half-way around the world. The OSI (Open Systems Interconnection) Reference Model defines seven layers of networking protocols. The complexity of these layers is beyond the scope of this tutorial; however, they can be simplified into four layers to help identify some of the protocols with which you should be familiar (see fig 1).

OSI Layer	Name	Common Protocols
7	Application
6	Presentation	HTTP \| FTP \| SMTP \| DNS
5	Session
4	Transport	TCP	SPX
3	Network	IP	IPX
2	Data Link	Ethernet
1	Physical	Ethernet

Fig 1. OSI model related to common network protocols

Figure 1 illustrates how some of the major protocols would correlate to the OSI model in order to communicate via the Internet. In this model, there are four layers, including:

Ethernet (Physical/Data Link Layers)
IP/IPX (Network Layer)
TCP/SPX (Transport Layer)
HTTP, FTP, Telnet, SMTP, and DNS (Session/Presentation/Application Layers)

Assuming you want to send an e-mail message to someone in Italy, we will examine the layers "from the bottom up" -- beginning with Ethernet (physical/data link kayers).

Ethernet (Physical/Data Link Layers)

The physical layer of the network focuses on hardware issues, such as cables, repeaters, and network interface cards. By far the most common protocol used at the physical layer is Ethernet. For example, an Ethernet network (such as 10BaseT or 100BaseTX) specifies the type of cables that can be used, the optimal topology (star vs. bus, etc.), the maximum length of cables, etc. (See the Cabling section for more information on Ethernet standards related to the physical layer).

The data link layer of the network addresses the way that data packets are sent from one node to another. Ethernet uses an access method called CSMA/CD (Carrier Sense Multiple Access/Collision Detection). This is a system where each computer listens to the cable before sending anything through the network. If the network is clear, the computer will transmit. If some other node is already transmitting on the cable, the computer will wait and try again when the line is clear. Sometimes, two computers attempt to transmit at the same instant. When this happens a collision occurs. Each computer then backs off and waits a random amount of time before attempting to retransmit. With this access method, it is normal to have collisions. However, the delay caused by collisions and retransmitting is very small and does not normally effect the speed of transmission on the network.

Client/Server

Client/server network operating systems allow the network to centralize functions and applications in one or more dedicated file servers (See fig. 2). The file servers become the heart of the system, providing access to resources and providing security. Individual workstations (clients) have access to the resources available on the file servers. The network operating system provides the mechanism to integrate all the components of the network and allow multiple users to simultaneously share the same resources irrespective of physical location. Novell Netware and Windows 2000 Server are examples of client/server network operating systems.

Fig. 2. Client/server network

Advantages of a client/server network:

Centralized - Resources and data security are controlled through the server.
Scalability - Any or all elements can be replaced individually as needs increase.
Flexibility - New technology can be easily integrated into system.
Interoperability - All components (client/network/server) work together.
Accessibility - Server can be accessed remotely and across multiple platforms.

Disadvantages of a client/server network:

Expense - Requires initial investment in dedicated server.
Maintenance - Large networks will require a staff to ensure efficient operation.
Dependence - When server goes down, operations will cease across the network.

Network Operating System Software

The following links include some of the more popular peer-to-peer and client/server network operating systems.

Assignment-gcd

2009-10-21T06:21:00.001-07:00

Greatest Common Divisor of 2 Integer numbers

Problem Definition:

To find the greatest common divisor (GCD) of an two integer number.

Problem Description:

Gcd for two numbers 20,30

Every gcd number will have greatest and smaller number.
The first number will be smaller number and the second number will be greatest number.
If gcd is even number then gcd(u,v)=2.gcd(u\2,v\2).because 2 is a common divisor.
If gcd is odd number then gcd(u,v)=gcd(u\2,v),because 2 is not a common divisor.

Diagramatic Representation:

Common part

20 U 30 V

10 20

Gcd=10

Gcd(20,30)=gcd(10,20)

Gcd=10

Gcd for same number:

If gcd have same number then gcd will be the same number.

For example:6,6

6 1

Gcd =6

While (n1!=n2)

We have to use this condition to implement for the same number in gcd.

Implementation:

#include<stdio.h>

#include<conio.h>

Void main()

{

Int n1,n2;

Clrscr();

Printf(“/n enter two numbers:”);

Scanf(“%d%d”,&n1,&n2);

While(n1!=n2)

{

If(n1>=n2-1)

n 1=n1-n2;

else

n 2=n2-n1

}

Printf(“/n gcd=%d”,n1);

getch();

}

Algorithm:

gcd(0, v) = v, because everything divides zero, and v is the largest number that divides v. Similarly, gcd(u, 0) = u, including u=0.
If u and v are both even, then gcd(u, v) = 2·gcd(u/2, v/2), because 2 is a common divisor.
If u is even and v is odd, then gcd(u, v) = gcd(u/2, v), because 2 is not a common divisor. Similarly, if u is odd and v is even, then gcd(u, v) = gcd(u, v/2).
If u and v are both odd, and u ≥ v, then gcd(u, v) = gcd((u−v)/2, v). If both are odd and u < v, then gcd(u, v) = gcd((v-u)/2, u). These are combinations of one step of the simple Euclidean algorithm, which uses subtraction at each step, and an application of step 3 above. The division by 2 results in an integer because the difference of two odd numbers is even.
Repeat steps 3–4 until u = v, or (one more step) until u = 0. In either case, the result is 2^kv, where k is the number of common factors of 2 found in step 2.

Application:

Reduces the fraction.

ARRAY TECHNIQUES

2009-10-05T07:46:00.001-07:00

ARRAY TECHNIQUES

FINDING THE KTH AMALLEST ELEMENT

PROBLEM

Given a randomly ordered array of n element determine the k^th smallest element in the set.

ALGORITHM DEVELOPMENT

To find the k^th smallest element would be to simply sort the element and then pick the k^th value. We may, however, suspect that this problem in a similar fashion to the partitioning problem.

K is number of passes in the array

K=1 =>O/P=5

K=2 =>O/P=6

If n value is smallest fully sorted. If the value is greater we sorted lightly

30 10 6 40 5

30 is minimum value it should compared and inter change

By the default I consider this is my smallest element

Minimum->compared->interchange

1^stpass

Min i

30 10 6 40 5

0 1 2 3 4

i comparison is started here

I found the minimum element to swap and update the index

Min i

10 30 6 40 5

Compare I found minimum element to swap and update the index

Min i

6 30 10 40 5

It is not minimum so update the index

Min i

6 30 10 40 5

I found minimum element to swap the element

Min i

5 30 10 40 6

If the 1^st pass is finished found the first minimum element

2 pass

Min i

5 30 ↔ 10 40 6

Compare I found minimum element to swap and update the index

Min i

5 10 30 40 6

no swapping update the index

min i

5 10 30 40 6

Compare I found minimum element to swap and update the index

5 6 10 30 40

Now we found second minimum element

PROGRAM

#include<stdio.h>

#include<conio.h>

Void main()

{

Int a[10],t,k,n,i,j ;

Printf(“ enter the values “) ;

Scanf(“%d”,&n);

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

Scanf(“%d”,&k);

For(i=0;i<k-1;i++)

{

Min=a[i];

For(j=i+1;j<n;j++)

{

If(a[j]<min)

{

Min=a[j];

t=a[i];

a[i]=a[j];

a[j]=t;

}

ALGORITHM DESCRIPTION

1. Establish the requirement that kth smallest element is sought.

2. left and right partition do not overlap do

a. choose a[k] as the paritition value x;

b. set I to the upper limit l of the left partition

3. extend the left partition whilea[i]<x;

4. exchange a[i]with a[j]

5. if k^th smallest in left partition ,update the values

6. if k^th smallest in right partition ,update the values

7. first k position in array

APPLICATIONS

Finding the median and finding percentiles

ARRAY ORDER REVERSAL

2009-09-26T23:20:00.001-07:00

CONTENT

PROBLEM DESCRITION

ALGORITHM DISCRIPTION

IMPLIMENTATION

APPLICATION

AIM:

WE HAVE TO REVERSE THE NUMBERS IN THE PROBLEM GIVEN

PROBLEM DISCRIPTION

REVERSAL ORDER MEANS JUST REVERSE THE NUMBER. WE HAVE THE NUMBERS IN ORDER OF 1,2,3,4,5,6,7

MEANS THE REVERSE OF THE NUMBERS ARE 7,6,5,4,3,2,1.

WE TAKE THIS AS AN EXAMPLE.

N=7 WE HAVE TO INTIALISE THE VALUE OF I IS1.

R IS THE NUMBER OF SWAPING.

WE HAVE CALCULATE R VALUE R=N/2.

A [1] <=> A [7]

A [2] <=> A [6]

A [3] <=> A [5]

A [4] <=> A [4]

I=1 INCREASE THE VALUE. N IS DECREASE VALUE.

WE HAVE ACHIVE ONLY ONE VARIABLE USE BOTH RIGHT & LEFT SIDE.

SO THE FORMULA IS N=N-I+1.

N=7-1+1=7

N=7-2+1=6

N=7-3+1=5

N=7-4+1=4

N=7-5+1=3

N=7-6+1=2

N=7-7+1=1

ALGORITHM DESCRIPTION

READ THE VALUES

INITIALIZ THE I VALUE

FIND THE NO OF SWAP

SUBSTUTE THE FORMULA N=N-I+1.

COLECT THE VALUES AND STORED

STOP THE PROCESS.

IMPLEMENTATION:

#INCLUDE<STDIO.H>

#INCLUDE<CONIO.H>

VOID MAIN ( )

{

INT A [100], T, R, I, N;

PRINTF (“ENTER THE VALUES’);

SCANF (“%D”, &N);

FOR (I=0; I<=N; I++)

R=N/2;

FOR (I=0; I<=R;I++)

{

T=A [I];

A [I] = A [N-I+1];

A [N-I+1] =T;

}

FOR (I=1;I<=N;I++)

PRINTF (“%D “, &D [I]);

}

IF ARRAY IS STARTING WITH 0 TH INDEX IT IS NOT WORK.

N=8 WE HAVE TO INTIALISE THE VALUE OF I IS 0.

R IS THE NUMBER OF SWAPING.

WE HAVE CALCULATE R VALUE R= (N+1)/2.

A [0] <=> A [7]

A [1] <=> A [6]

A [2] <=> A [5]

A [3] <=> A [4]

I=0 INCREASE THE VALUE. N IS DECREASE VALUE.

WE HAVE ACHIVE ONLY ONE VARIABLE USES BOTH RIGHT & LEFT SIDE.

SO THE FORMULA IS N= N-I.

N=7-0=7

N=7-1=6

N=7-2=5

N=7-3=4

N=7-4=3

N=7-5=2

N=7-6=1

PROGRAM FOR STARTING INDEX 0:

#INCLIDE<STDIO.H>

#INCLUDE<CONIO.H>

VOID MAIN ( )

{

INT A [100], T, R,I,N;

PRINTF (“ENTER THE VALUES’);

SCANF (“%D”, &N);

FOR (I=0; I<=N; I++)

R=N/2;

FOR (I=0; I<=R; I++)

{

T=A [I];

A [I] = A [N-I];

A [N-I] =T;

}

FOR (I=1; I<=N; I++)

PRINTF (“%D “, &D [I]);

}

APPLICATION:

SORTING IN MATHEMATICAL.

MATRIX MALTIPLICATION

re

2009-09-26T23:12:00.001-07:00

REMOVAL OF DUPLICATES FROM ORDEREDARRAY

Problem definition: To design an algorithm for removal of duplicates using array.

Problem description:

We can use array with duplicates and also array without duplicates.In both of this we can use sorted array with duplicates and sorted array without duplicates.

Two methods:

*Array without duplicates.

*Array with duplicates.

Two types of condition to compare the given two elements:

(1).i=1; a[i]=a[i+1];

->In this type we assign that the comparison is between the adjacent elements.

->And also this type may have the range of values in the outer bound.

(2).i=2; a[i-1]=a[i];

->In this type we assign that the current i index is compared with (i-1)th index.

->This part also have the range of values and it is supply within the array.

->Comparing with this two type of range of values (2) type of values is best choice for doing removal of duplicates.

Purpose of usage the condition(i<n) instead of i<=n:

->Though (i<=n) condition is satisfied,no need to use this condition because that one value is count in out of range area.So,we can use the condition(i<n).

(Eg):n=3,i=2.

->Here i<n is condition is more applicable.

@.Explanations:

(1).Array without duplicates:

Consider an (eg): 10 20 30 40 50

->While comparing the elements if they are equal then it is duplicate element.Orelse if the element is not equal then update the i value after that it move on to next comparison.

(1a) Necessary steps:

->Initialize i=2;

->Check condition(i<n&&a[i-1]!=a[i])

->If it is satisfy then update the I value.

i=2

I (1). (eg) 10 _ 20 30 40 50

_ ( comparison symbol)

Here condition is true .So,there is no duplicate element,update the i value.

i=3

I(2).10 20 _ 30 40 50

Here condition is true .So,there is no duplicate element,update the i value.

i=4

I(3).10 20 30 _ 40 50

Here condition is true .So,there is no duplicate element,update the i value.

i=5

I(4).10 20 30 40 _ 50

If i is reach the last element the comparison is not done for the 4 &5 element.

So ,we have include this coding during ‘array without duplicates’:

->a[i-1]!=a[i]

->if this condition is satisfied then i is incremented to 6.

->J=i-1;//this above 6 is in out of range of array values.so,decrement the i value and assign it to ‘j’ value.

Then the result is:10 20 30 40 50

(2).sorted array with duplicates:

Consider an (eg): 20 30 40 40 40 50

->While comparing the elements if they are equal then it is duplicate element.Orelse if the element is not equal then update the i value after that it move on to next comparison.

(2a)necessary steps:

->Initialize same as i=2;

->Then check (a[i-1]!=a[i]&&i<n).

->If it is satisfy my condition i++ the index.

i=2

I(1).20 _ 30 40 40 40 50

The condition is true because the comparing element is not equal.then update the i value.

i=3

I(2).20 30 _ 40 40 40 50

The condition is true because the comparing element is not equal.then update the i value.

i=3

I(3).20 30 40 _ 40 40 50

->The condition is false because the comparing element is equal.then no update here. It move on to next comparison

->Here we have to maintain the variable j is a unique index that have only the element which are not duplicated.It move on to next comparison.

->J=i-1//it assign the previous element which are not duplicate element by using loop.

j i=3

I(4).20 30 40 40 _ 40 50

->The condition is false because the comparing element is equal.then no update here. It move on to next comparison.

j i=4

I(5).20 30 40 40 40 _ 50 -> (1)

The condition is true because the comparing element is not equal.then update the i value.

20 30 40 40/50 ||40 50|| -> (2)

|| || ->virtual value.

/ -> overwrite the value.

->Here no change is happen then j (unique index) is update.

->Overwritten the last element in the place of recent j variable.(40/50).

->This means the duplicate value is removed from array.

->Then finally result is:20 30 40 50.

Program:

Void main()

{

Int a[100],i,j,n;

Scanf(“%d”,&n);

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

Scanf(“%d”,&a[i]);

i=2;

while(i<n&&a[i-1]!=a[i])

i++;

if(a[i-1]!=a[i])

i++;

j=i-1;

while(i<n)

{

i++;

if(a[i-1]!=a[i])

{

j++;

a[j]=a[i];

}

n=j;

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

printf(“%d”,a[i]);

}

Applications:

#Data compression

#Text processing problems.