CSIT PROGRAM IN NEPAL

noreply@blogger.com (Ramesh) — Sun, 20 Mar 2011 06:34:00 +0000

Make An IFrame To Contain Another Blog On Your Blog Page

When you want to merge two websites (either or both being a blog), yet keep the content of each separate, the most obvious solution is to use the same template on each, and link between the two in a consistent fashion. The reader of either blog never has to know when he's viewing the other, unless he habitually observes the content of the browser Address window.

But how about if you would like to display one blog, in its entirety, in the middle of the other blog page? That's a feature called an IFrame. It's a deceptively simple solution too.

You can put an IFrame in either a blog post, or in a special page element. It's a dynamic window; when you change something in the blog contained in the window, the contents of the window changes too. Just refresh, and you can see the change.

An IFrame is a nice substitute for a newsfeed, when you are including a private blog in another web site. Since a newsfeed isn't available for a private blog, it's useless in this case. An IFrame works as well for a private blog as it does for a public blog. Remember, of course, that access to any IFrame requires access to both the IFrame host web site, and to the source web site.

One caveat here, which may be an asset or a liability, is that the content of an IFrame won't be picked up by the search engines. If the text inside the iframe is important content that needs to be indexed with the host blog, you won't want to put it inside an iframe. On the other hand, if you have text that you explicitly do not want indexed, an iframe can be a perfect solution.

It's got a number of settings that can make it more useful to you. You can set the height and width of the IFrame, to determine how much screen space, inside your blog, that you wish to use to display the IFrame contents. If the IFrame contents are larger than the allocated space, by default you'll get scroll bars; these can, at your own risk, be deactivated.

Remember that, as the text size is varied by the reader, the overall size of the contents inside the IFrame will vary, just as the contents of the blog outside the IFrame. Instead of specifying an absolute height or width in pixels, you can specify either in %, and have the IFrame size decrease or increase as the reader necessitates.

Depending upon what effect you desire, you'll want either the IFrame host web site, or the source web site, to be as plain as possible. If you have a normal blog with a page header, post column, and one or two sidebars, you will want the IFrame source web site to have a very plain template. For instance, if you're creating a second blog to contain posts that will be accessible only to a select few of your readers, you'll want to display an IFrame that only contains a posts column - any page header, sidebar, and / or footer section will just take up valuable screen space on the host web site, or force excessive horizontal or vertical scrolling inside the iframe window.

>> Top

Model question of Desing Algorithm Analysis and Design

noreply@blogger.com (Ramesh) — Thu, 16 Sep 2010 07:12:00 +0000

Tribhuvan University

Bachelor of Science in Computer Science

And Information Technology

Model Question:

Full Marks : 80 + 20 Pass Marks : 32 + 8 Time : 3 hrs

>>>Design and analysis of algorithm <<<

1. Can we apply master method to find the big-O estimate of the recurrence T(n)=4T(n/2) + n2logn? Why or why not? Find the big-O estimate for this recurrence by using recursion tree.

2. Given the following block of code, write a recurrence relation for it with reason and also find asymptotic upper bound (Assume that all dotted code takes linear time)

fun(int n)

{

…………….

if(condition1)

x=Fun(n/2)

else if(condition2)

x=Fun(2n/3)

else

x= Fun(n/4)

……………

}

3. What do you mean by order statistics? How can you devise an algorithm that guarantee the selection of ith order statistics in linear time? Write the algorithms of it and also analyze it.

4. In what situations the dynamic programming algorithms are useful? What are the application areas of Longest Common Subsequence? Write the recursive definition for finding LCS and find the LCS of the strings "Monkey" and "Money".

5. What is the advantage and disadvantage of greedy algorithms over dynamic programming algorithms? Under what circumstances greedy algorithm gives us optimal solution? Devise the greedy algorithm that makes the change of n rupees (n<55000 and n is multiple of 10) with minimum number of notes (consider 100 notes of 10 rupees, 80 notes of 20 rupees, 60 notes of 50 rupees, 50 notes of 100 rupees, 40 notes of 500 rupees and 30 notes of 1000 rupees.

6. In which case adjacency matrix representation of graph is better? Explore DFS with example and give it's asymptotic and aggregate analysis.

7. What is the main concept behind randomized algorithms? Write algorithm for randomized quick sort and analyze it.

8. What is NP completeness? What approaches are used in proving NP-completeness of the problems? "Proving a problem as NP-complete is considered as good contribution in computer science" why? Justify with strong argument.

9. What is left turn and right turn? Give an algorithm for finding whether two line segments intersects or not by using left and right turn. Justify with example that algorithm works for all cases.

10. Suppose that our machine does not supports direct multiplication operation. Multiplication must be done by repeated addition. Devise Iterative and recursive algorithm for it and analyze them.

Advantages / Disadvantages of fiber optic cable

noreply@blogger.com (Ramesh) — Wed, 15 Sep 2010 14:25:00 +0000

>> Advantages of fiber optic cable <<

Fiber optic cable has following advantages;

1) Higher Bandwidth

Fiber optic cable can support and dramatically higher bandwidth and hence data rates than twisted pair and co-axial cable. Currently data rates and bandwidth utilization over fiber optic cable are limited not by the medium but by the signal generation and reception technology used.

2) Less signal attenuation

Fiber optic transmission distance is significantly greater than that of other guided media. A signal can run for 50 km without requiring regeneration. we need repeaters at every 5Km for twisted pair and co-axial cable.

3) Immunity to electromagnetic interference (EMI)

Electromagnetic interference (EMI) cannot effect fiber optic cable.

4) Resistance to corrosive material

Glass is more resistance to corrosive material than copper wire.

5) Light weight

Fiber optic cables are much lighter than copper wires.

6) Greater immunity to tapping

Fiber optics cables are more immune to tapping than copper cables. Copper cabl ecreates antenna affects that can easily be tapped.

>> Disadvantages of fiber optic cable <<

Fiber optic cables too have some disadvantages;

1) Installation and maintenance

Since it is new technology, its installation and maintenance requires hight expertize that is not yet available everywhere. It is also dangerous for health of human being.

2) Unidirectional light propagation

Propagation of light is unidirectional. If we need bi-directional communication, two fibers are needed.

3) Cost maintenance

The cable and the interfaces are relatively more expensive than those of other guided media.

>> You might also like <<

Types of Computer Network and Transmission Media

noreply@blogger.com (Ramesh) — Wed, 15 Sep 2010 13:33:00 +0000

Triple ExposureTypes of Computer Network

Mainly, there are three kinds of computer networks given below;

Local Area Network (LANs)
Wide Area Network (WANs)
Metropolitan Area Network (MANs)

>>> Short description of above points <<<

1).Local Area Network (LANs)

Local Area Networks, commonly known as the LANs which are originally owned privately. As the need of the organization and the components involved (networking components)LANs may be simple as connection between the two PCs or Workstation or it may be extended outside the company to connect two LANs. Local Area Networks (LANs) are the networks that are usually confined to a geographic area of small range such as within a single building, college, office, hospital, etc. LANs can be small linking as few as two computers but often link hundreds of computers used by thousands of people. The development of standard networking protocols and media has resulted in world wide growth of LANs throughout business and educational organization.

2). Wide Area Network (WANs)

Wide Area Network commonly known as WANs which is mainly used to connect the different computers at any end of the world (i.e, world wide connection). WANs combine multiple LANs that are geographically separate. This is achieved by connecting the different LANs. Using services such as dedicated leased line, dial-up lines, satellite link, etc WAN can be as simple as a modem and remote access server for employees to dial into, or it can be as complex as hundreds of branch offices globally link using special routing protocols and filters to minimize the expense of sending data such as image, audio, video over large geographic areas. It is the network which connects countries, continents or even the whole world.

3). Metropolitan Area Network (MANs)

These are the computer networks that refers to the networks of computers within city or metropolitan area. A single MANs comprises of several LANs. It is the network between the LANs and WANs.

Transmission Media

Transmission medium is the physical layer or path or link or way through which the data and information are transmitted over the networks. A transmission medium can be broadly defined as anything that can carry information from a source to a destination. It is usually a free space, metallic cable or fiber optic cable.

In telecommunication, transmission media can be divided into two broad categories;

Guided Media
Unguided Media

>>> Short description of above points <<<

I).Guided Media

Guided media are those that provide the conduit from one device to another and includes twisted pair cable, co-axial cable, fiber optic cable. A signal travelling along any of these media is directed and contained by the physical limits of the medium.

There are several guided media available in the markets given as below;

1). Twisted pair cable

Twisted pair cable consists of two insulted strands of copper wire twisted around each other to form a pair. One of the wire is used to carry signals to the receiver and the other is used only as a ground reference. The receiver uses the difference between the two.

In addition to the signal sent by the sender on one of the wires, interference and crosstalk many affect both wires and creates unwanted signal.

The purpose of twisting wire is to eliminate electrical interference fro mother wires and out side resources. Twisting the wire cancels any electrical noise from the adjacent pair. The more twist per linear foot, the greater the effect.

There are two types of twisted pair cable.

a). Shielded twisted pair (STP)

The only difference between STP and UPT is that STP has a foil or wired braid wrapped around the individual wires of the pair. The shielding designed to minimized electromagnetic interference radiation and succeptibility to crosstalk. The STP cable sues a woven copper braided jackets which is a higher quality more protective jacket than UTP.

b). Unshielded twisted pair (UTP)

As the name implies UPT cabling is twisted pair cabling that contains no shielding. It is the most common twisted pair cable used in communication.

2)Co-axial Cable

It is made up of two conductors that share the same axis, the center is a copper wire that is insulated by a plastic coating and then wrapped with an outer conductor usually a wire braid. This outer conductor around the insulation serves as electrical shielding for the signal being carried out by the inner conductor. A tough insulating plastic tube outside the outer conductor provides physical and electrical protection. It carries the signal of high frequency ranges than those in twisted pair cable, in part because the two media are constructed quite differently.

Categories of co-axial cable

Categories	Impedence	Use
RJ-59	75 Ohm	Cable TV
RJ-58	50 Ohm	Thin Ehternet
RJ-11	50 Ohm	Thick Ethernet

3)Fiber Optics

A fiber optic cable is made up of light conducting glass or plastic fibers. It can carry data signals in the form of the pulses of light. The plastic core cables are easy to install but do not carry signals as far as glass core cables.

Optical fibers use total internal reflection to guide light through a channel. A glass or plastic core is surrounded by a cladding of less dense glass or plastic. The difference in density of the two materials must be such that a beam of light moving through the core is reflected off the cladding instead being refracted into it.

#Propagation Mode of fiber optics

Current technology supports two modes of propagation: multimode and single mode for propagating light along optical channels, each requiring fiber with different physical characteristics. Multimode can be implemented in two forms: step-index or graded index.

1).Multi mode propagation:

It is so named because multiple beams from a light source move through the core in different paths. How these beams move within the cable depends on the structure of the core. It is further divided into two categories;

i) Multi-mode step-index fiber

In this mode, the density of the core remains constant form the center to the edges. A beam of light moves through this constant density in a straight line until ti reaches the interface of the core and cladding. At the interface, there is an abrupt change due to the lower density; this alters the angle of the beams motion. The term step-index refers to the suddenness of this change, which contributes to the distortion of the signal as it passes through the fiber.

ii) Multi-mode graded-index fiber

It decreases this distortion of the input through the cable. The word index here refers to the index of refraction. We know that the index of refraction is related to the density. A graded index fiber, therefore, is one with varying density. Density is highest at the center of the core and decreases gradually to its lowest at the edge.

2). Single mode propagation

Single mode use step-index fiber and a highly focused source of light that limits beams to a small range of angles, all close to the horizontal. The single mode fiber itself is manufactured with a much smaller diameter than that of multi-mode fiber and with substantially lower density. The decrease in density results in a critical angle that is close enough to 90 degree to make the propagation of beams almost horizontal. In this phase, propagation of different beams is almost identical and delays are negligible. All the beam arrive at the destination together and can be recombined with little distortion to the signal.

You might like this !!

Application of Computer Network

noreply@blogger.com (Ramesh) — Mon, 13 Sep 2010 12:17:00 +0000

Application of Computer Networks

Computer Networks are applied in following fields;

Facilitating Communication
Sharing Resources / Hardware
Sharing files, data and information
Sharing software
E-commerce
Remote Access

>>> Short description of above points <<<

1). Facilitating Communications

As we know that computer network is the connection of two computer via some means of communicating media. As network exists data travels over the network. Using a network people communicate efficiently and easily via email, instant messaging, chat room, telephone, video telephone calls, and video conference.

2). Sharing Resources / Hardware

Network allows the every computer in the connection to share the hardware resources. In a network environment each computer on a network may access and use hardware resources such as printer, CD-ROM drive.

3). Sharing files, data & information

In a network environment authorized user may access data and information stored on other computers on a network. The capability of providing access to data and information on shared storage devices is an important feature of many networks.

4). Sharing Software

Users connected to a network may run application programs on remote computers. Installing software in the server, every computer in the network can access and use that software efficiently and easily.

5). E-commerce

E-commerce is a short form of 'Electronic Commerce'. It means selling or buying of goods with the help of internet so computer network has huge effect on such transaction.

6). Remote access

Computer network allows a user to log in and access data or information running on distant server.

Go for this !!

Computer Network, Chapter One

noreply@blogger.com (Ramesh) — Mon, 13 Sep 2010 11:47:00 +0000

>>>Notes of Computer Networks, available here, Go for it <<<

Subject Chapters for Computer Networks	Following Link Related Links for given chapters!!!
Introduction of Computer Network	>>Go for related topics<<
Advantages/Disadvantages of Computer network	>>Go for related topics<<
Applications of Computer N/W	>>Go for related topics<<
Types of N/W, Transmission Media	>>Go for related topics<<
Advantages/Disadvantagesoffiberoptics	>>Go for related topics<<

You might like this !!

Advantages of computer network

noreply@blogger.com (Ramesh) — Mon, 13 Sep 2010 11:10:00 +0000

Advantages of computer network

A computer network has following advantages;

File sharing
Resource sharing
Time sharing
Increased storage capacity
Increased cost efficiency

>>> Short description of above points <<<

1).File sharing

The major advantage of computer network is that it allows file sharing and remote file access. For example, a person sitting at one workstation of a network can easily see the files present on the other workstation provided, he is authorized to do so.

2). Resource sharing

In a networked environment, each computer in a network may access each computer and use hardware resources on the network. Such as printing a document on a shared network printer.

3). Time sharing

It shares the time which is wasted in copying a file from one system to another by using storage device. In addition to that many people can access or update the information stored in a database, making it up to date and accurate.

4). Increased storage capacity

As there is more than one computer on a network which can easily share files, the issues of storage capacity gets resolved to a great extent. A standalone computer might falls short of storage memory, but when many computers are on a network, memory of different computers can be used in such case. One can also design a storage server on the network in order to have huge storage capacity.

5). Increased cost efficiency

There are many software available on the market which are costly and take time for installation. Computer network resolve this issue as the software can be stored or installed on a server computer and can be used by different users or clients.

Disadvantages of Computer Network

A computer network has following disadvantages;

Security issues
Rapid spread of computer viruses
Expensive setup
Depending on the main file server

>>> Short description of above points <<<

1).Security issue

One of the major drawbacks of computer network is the security issue involved. If a computer is a standalone, physical access becomes necessary for any kind of data theft. However, if a computer is on a network, a computer hacker can get unauthorized access.

2). Rapid spread of computer viruses

Viruses get spread on a network easily because of the interconnectivity of workstations. Such spread can be dangerous if the computers have important database which can corrupted by the virus.

3). Expensive Setup

The initial setup cost of a computer network can be high depending on the number of computers to be connected. Costly devices like routers, switches, hubs, etc can add up to the bills of person trying to install a computer network. He will also have to buy NIC, network cables, RJ-45 connector, etc. for each of the workstations

4). Dependency on the main file server

In case of the main file server of the computer network breaks down the system becomes useless. In case of big networks, the file server should be a powerful computer which often makes it expensive.

Introduction of Networks

noreply@blogger.com (Ramesh) — Mon, 13 Sep 2010 10:23:00 +0000

Introduction of computer networks

A network is a set of devices (often referred to as nodes) connected by some means of communication medias or links. A node can be a computer, printer, or any device capable of sending and / or receiving data generated by other nodes on the network.

A computer network is a collection of computers and other devices connected by some means of communication channels that facilitate communication among users and allows user to share resources with other users.

Some features of computer networks:

>> Distributed Processing :

Most networks use distributed processing, in which a task is divided among multiple computers. In this system instead of single large machine being responsible for all aspects of a process, separate computers handle a subset.

>> Network Criteria :

A network must be able to meet a certain number of criteria. The most important of these among several of them are ;

Performance

Reliability

Security

>>Performance

Performance of any network can be measured in many ways, including transit time and response time. The transit time is the amount of the time required for a message to travel from one device to another device. The response time is the time consumed between an inquiry and a response.The performance of a network depends on a number of factors, including the number of users, the type of transmission media, the capabilities of the connected hardware, and the efficiency of the software components.

Performance is often evaluated by two networking components: throughput and delay. Main purpose of any network is to bring the more throughput and less delay. That mean we need more throughput and less delay. However, these two criteria are often contradictory. If we try to send more data tot the network, we may increase the throughput but we also increase the delay because of the traffic congestion in the network.

>> Reliability

The system which must send / deliver the data to the correct destination as well as it is also necessary for any system to send the data more accurately. In addition to accuracy of delivery, network reliability is measured by the number of times of failure, the time it takes a line to recover from a failure, and the network's robustness in a catastrophe.

>> Security

Network security issues include protecting data from unauthorized access. It also handle the issue of protecting the data from damage and development, and implementing policies and procedures fro recovery from data losses.

Types of agent

noreply@blogger.com (Ramesh) — Thu, 09 Sep 2010 12:43:00 +0000

>>>> Chapter one, Types of Artificial Agent <<<<

# Simple Reflex Agent:

The simple reflex agent has:

Information comes from sensor
change the agent current state of the world
trigger action through the effectors

Simply the simple reflex agent act only the basic of current percepts, that is which has no notion of history.

The main characteristics of this agent are:

No internal representation for reasoning inference
Efficient
No strategic planning
Learning

# Reflex Agent with state (Model-based reflex agent)

This type of agent differ from simple reflex agent in that such agent maintain some sort of state based on the percept sequence. The state is updated regularly based on what the agent seems and the agent action keeping track of the state. The model based agent work as follow ;

information comes from sensors
the agent change the current state of the world
based on this state of the world and knowledge it trigger action through the effectors.

# Goal based agent

Goal based agent are similar to simple reflex agent which stores the information regarding its situation that are desirable. This allows the agent a way to choose among multiple possibilities selecting the one which reaches a goal state.

# Utility based agent

The utility based agent provides a more general agent frameworks. In case that multiple goals, this framework can accommodate different goals. Such systems are characterized by utility function that maps a state or a sequence of states to real value utility.

#Additional Agents <<<

learning agent
deliberative agent
reactive agent
hybrid agent
emailing agent

Click here to download: "Overview of Artificial Intelligence"

Hope guys, u will enjoy it !!

Good luck have a nice day!!

Artificial Agent

noreply@blogger.com (Ramesh) — Thu, 09 Sep 2010 11:49:00 +0000

>>>> Chapter one, Artificial Agent <<<<

Artificial Agent

The word "agent" is derived from the concept of agency which means employing someone to act on behalf of the users. An agent is something that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators. An human agent has eyes, ears and other organs for sensors and body parts like hands, legs, mouth etc, for actuators, A software agent receives keystrokes, file contents and networking packets as sensory inputs and acts on the environment by displaying on the screen, writing files and sending network packets. Computer agent (or software agents) have several characteristics which distinguish them from every programs. They are:

Capability to work on their own (autonomy)
Perceiving their environment
Persisting over a prolonged time period
Adapting to change (adaptivity)
Capable of taking on another's goal (goal oriented)
Transportable over networks (mobility)
Ability to interact with humans, systems and other agents (communicative)
Ability to learn

In AI, we use the term "intelligent agent" which represent a new technology for software programs. AI is about the design and implementation of intelligent agents. Turing suggested that a system or agent can be said to be intelligent when the agent's performance cannto be distinguished from that of a human performing the same task.

A better definition of artificial agent is:

An intelligent agent is a software entity which senses its environment and then carries out some set of operations on behalf of a user (or a program), with some degree of autonomy, and in doing so employs some knowledge or representation of the user's goals or desires.

In other words, AI are software programs which work in the background to carry out specific, repetitive, predictable task for an individual user, business processor software application.

Structure of Agent

A simple agent program can be defined mathematically by an agent function which maps every possible percept sequences to a possible action to the agent. That is,

f : p * ---------> A

So the agent program run on the physical architecture and that implement the agent function 'f'.

That is, agent = Architecture + Program.

For example: A Vacuum Cleaner:

Environment	Percept	Action
Square A and B	[location, content] [A, Clean] [A, Dirty] [B, Clean] [B, Dirty] ...............	Right Suck Left Suck .................

The Pro log programming

function RVF ([location, status]) return
an action

if (status == dirty) then
return suck

else if (location == A) then
return right

else

return left

Notes of Computer Networks

noreply@blogger.com (Ramesh) — Wed, 08 Sep 2010 10:11:00 +0000

>>>Notes of Computer Networks, available here, Go for it <<<

Subject Chapters for Computer Networks	Following Link Related Links for given chapters!!!
Data communication	>>Go for related topics<<
Components of Data Communications System	>>Go for related topics<<
Data representation	>>Go for related topics<<
Data flow	>>Go for related topics<<
Chapter 1	>>Go for related topics<<

Notes of Algorithm Design & Analysis

noreply@blogger.com (Ramesh) — Wed, 08 Sep 2010 10:09:00 +0000

>>>Notes of Algorithm Design & Analysis Algorithm, Go <<<

Subject Chapter lists for Algorithm Des. & Ana.	Following Link Related Links for given Chapters
About Sorting	>> Go for related topic <<<
Merge sort	>> Go for related topic <<<
Selection sort	>> Go for related topic <<<
Insertion sort	>> Go for related topic <<<

Data Communications

noreply@blogger.com (Ramesh) — Wed, 08 Sep 2010 10:01:00 +0000

"Notes of Computer Networks"

Things to remember before going on computer networks

To understand the concept of networking or network, first we have to understand the concept of data communications. Because the main purpose of the network is to transmit the data between all the computers connected to the network. To fully grasp about the network, we must understand the data communication components, how data can be represented in various form, and how to create a data flow.

Data communications between the remote parties can be established through the process networking, by involving the connection of computers, networking devices, media etc. Mainly there are two types of networks: Local Area Networks(LANs) and Wide Area Networks(WANs). These two types of networks have distinct characteristic and different functionalities.

Protocols and standards are other two main components of computer network and are vital to the implementation of data communications and networking. Protocols refers to the rules and standard is a protocol that has been adopted by the vendors and manufacturers.Network models serve to organize, unify, and control the hardware and software components of data communications and networking.

Data Communications

While we communicate, we are sharing something i.e, information. This sharing can be local or remote. Between individuals, local communications usually takes places face to face, while remote communication occurs over distance. The term telecommunication(taken from Greek word tele : "far"), which includes telephony, telegraphy, and television, means communication at a distance.

The word data refers to information presented in whatever from which is shared among the networking devices connected to the networks. Data communication is the process of exchange of data between two devices through some form of transmission medium such as a wire cable. For data communications to occur, the communicating devices must be the part of the communication system made up of a combination of hardware (physical equipment) and software (programs).

The effectiveness of the data communication system depends on four major and fundamental characteristics; delivery, accuracy, timeliness and jitter.

Delivery: The system must deliver the data to the correct destination. Data must be received by the intended device or user and only by that device or user.
Accuracy: The system must deliver the data accurately. Data that have been altered in transmission and left uncorrected are unusable.
Timeliness: The system must deliver the data in a timely manner. Data delivered late are useless. In the case of video and audio, timely delivery means delivering data as soon as they are produced, in the same order that they are produced, and without any significant delay. This kind of delivery is called real-time transmission.
Jitter: Jitter refers to the variation in the packet arrival time. It is the uneven delay in the delivery of audio or video packets. For example, let us consider that video packets are sent every 30 ms. If some of the packets arrive with 30-ms delay and others with 40-ms delay, an uneven quality in the video is the result.

Simulation And Modeling

noreply@blogger.com (Ramesh) — Wed, 08 Sep 2010 09:53:00 +0000

>>>Notes of Simulation And Modeling, available here, Go for it <<<

Subject Chapters for Simulation & Modeling	Following Link Related Links for given chapters!!!
Coming soon...	Coming soon...
Coming soon...	Coming soon...
Coming soon...	Coming soon...
Coming soon...	Coming soon...

Wireless Networking

noreply@blogger.com (Ramesh) — Wed, 08 Sep 2010 09:49:00 +0000

>>>Notes of Wireless Networking, available here, Go for it <<<

Subject Chapters for Wireless Networking	Following Link Related Links for given chapters!!!
Coming soon...	Coming soon...
Coming soon...	Coming soon...
Coming soon...	Coming soon...
Coming soon...	Coming soon...

Artificial Intelligence

noreply@blogger.com (Ramesh) — Wed, 08 Sep 2010 09:37:00 +0000

>>>Notes of Artificial Intelligence, available here, Go for it <<<

Subject Chapters forArtificial Intelligence	Following Link Related Links for given chapters
Coming soon...	Coming soon...
Coming soon...	Coming soon...
Coming soon...	Coming soon...
Coming soon...	Coming soon...

Data Flow

noreply@blogger.com (Ramesh) — Wed, 08 Sep 2010 06:30:00 +0000

Data Flow

Communication between two devices can be simplex, half-duplex, or full-duplex.

Simplex:
In the simplex mode, the communication is unidirectional, as a one-way street. This meant data flow takes place towards only one direction at a time. Only one of two devices on a link can transmit the data and the other can only receive . Keyboards and traditional monitors are examples of simplex devices. The keyboard can only support the input, the monitor can only accept output. The simplex mode can use the entire capacity of the channel to send data in one direction.

Half-Duplex
In half-duplex mode, each node in the network can send and receive, but the same time. When one device is sending, the other can only receive, and the vice versa. The half-duplex mode is like one-lane road with traffic allowed in both directions. When cars are travelling in one direction, cars going the other way must wait. In a half-duplex transmission, the entire capacity of a channel is taken over by whichever of the two devices is transmitting at the time. Walkie-Talkie and CB (citizen band ) radios are both half-duplex systems.

Full-Duplex
In full-duplex mode (also called duplex), both stations can transmit and receive simultaneously. The full-duplex mode is like a two-way street with traffic flowing in both direction at the same time. In full-duplex mode, signals going in one direction share the capacity of the link with signals going in the other direction. This sharing can occur in two ways; either the link must contain two physically separate transmission paths, one for sending and the other for receiving; or the capacity of the channel is divided between signals traveling in both directions.

Data Representation

noreply@blogger.com (Ramesh) — Wed, 08 Sep 2010 05:16:00 +0000

Note of Computer Networks!!

Information today comes in different forms such as text, numbers, images, audio and video.

Brief description about each of them is given below:

Video: Video is the another form of the data that is transmitted over the computer networks. It refers to the recording or broadcasting of the pictures or videos. Video can either be produced as a continuous entity (e.g., by a TV camera), or it can be combination of the images, each a discrete entity, arranged to convey the idea or motion. We can change the video to a digital or an analog signal.

Text: In data communications, text is represented as a bit pattern, that is a sequence of bits (either 0s or 1s). Different sets of bit patterns have been designed to represent text symbols. Each set is called a code, and the process of representing symbols is called coding. Today, the most prevalent coding system is called Unicode, which uses 32-bits to represent a symbol or character used in any language in the world. The American Standard Code for Information Interchange (ASCII), developed some few decades ago in the United States, now constitutes the first 127 characters in Unicode and is also referred to as Basic Latin.

Numbers: Numbers are also represented by bit patterns. Unlike a text, to represent numbers does not require a code such as ASCII. The number is directly converted to a binary number to simplify mathematical operations.

Images: Images are also represented by bit patterns. In its very simplest form, an image is composed of a matrix of pixels (picture elements), where each pixel is a small dot. The size of the pixel depends on the resolution. For example, an image can be divided into 100 pixels or 1,000 pixels. In previous example, in second case, there is a better representation of the image (i.e, better resolution), but the memory usage of the computer is increased to store the image.

After an image is divided into pixels, each pixel is assigned a bit pattern. The size and the value of the pattern depend on the image. For an image made of only black-and-white dots (e.g., a chessboard), a 1-bit pattern is enough to represent a pixel. To represent four level of gray scale, 2 bit-patterns can be used. A black pixel can be represented by 00, a dark gray pixel by 01, a light gray pixel by a 10, and a white pixel by 11.

There are several methods to represent color images. One method is called RGB, so called because each color is made of a combination of three primary colors; red, green, and blue. The intensity of each color is measured, and a bit pattern is assigned to it. Another method is called YCM, in which a color is made of a combination of three primary colors: yellow, cyan, and magenta.

Audio: Audio is the another form of the data that is to be communicated. It refers to the exchange of the recordings or broadcasting of sound or music. Audio is by nature different from text, numbers, or images. Unlike text, numbers and images it is continuous. Even when we use a microphone to change voice or mute to an electric signal, we create a continuous signal.

Video: Video is the another form of the data which is transmitted over the computer networks. It refers to the recording or broadcasting of a pictures or movie. Video can either be produced as a continuous entity (e.g., by a TV camera), or it can be a combination of the images, each a discrete entity, arranged to convey the idea of motion. We can change the video to a digital signal or an analog signal.

Data Communications

noreply@blogger.com (Ramesh) — Wed, 08 Sep 2010 03:53:00 +0000

Data Communications

While we communicate, we are sharing something i.e, information. This sharing can be local or remote. Between individuals, local communications usually takes places face to face, while remote communication occurs over distance. The term telecommunication(taken from Greek word tele : "far"), which includes telephony, telegraphy, and television, means communication at a distance.

The word data refers to information presented in whatever from which is shared among the networking devices connected to the networks. Data communication is the process of exchange of data between two devices through some form of transmission medium such as a wire cable. For data communications to occur, the communicating devices must be the part of the communication system made up of a combination of hardware (physical equipment) and software (programs).

The effectiveness of the data communication system depends on four major and fundamental characteristics; delivery, accuracy, timeliness and jitter.

Delivery: The system must deliver the data to the correct destination. Data must be received by the intended device or user and only by that device or user.
Accuracy: The system must deliver the data accurately. Data that have been altered in transmission and left uncorrected are unusable.
Timeliness: The system must deliver the data in a timely manner. Data delivered late are useless. In the case of video and audio, timely delivery means delivering data as soon as they are produced, in the same order that they are produced, and without any significant delay. This kind of delivery is called real-time transmission.
Jitter: Jitter refers to the variation in the packet arrival time. It is the uneven delay in the delivery of audio or video packets. For example, let us consider that video packets are sent every 30 ms. If some of the packets arrive with 30-ms delay and others with 40-ms delay, an uneven quality in the video is the result.

Components of Data Communications System

noreply@blogger.com (Ramesh) — Wed, 08 Sep 2010 03:39:00 +0000

Mainly, a data communications system consists of five components:

Message: The message is the information (data) to be communicated. Popular forms of information include text, numbers, pictures, audio, and video.
Sender: The sender is the device that sends the data message. It can be a computer, workstation, telephone handset, video camera, and so on.
Receiver: The receiver is the device that receives the message. It can be a computer, workstation, telephone handset, television, and so on.
Transmission medium: The transmission medium is the physical path by which a message travels from sender to receiver. Some examples of transmission media include twisted-pair wire, coaxial cable, fiber-optic cable, and radio waves.
Protocol: A protocol is a set of rules that govern the data communications. It represents n agreement between the communicating devices. Without the protocols, two devices may be connected but can not communicate with each, just as a person speaking Chines cannot be understood by a person who speaks only French.

About Sorting

noreply@blogger.com (Ramesh) — Mon, 06 Sep 2010 18:29:00 +0000

About Sorting: (Source : Wikipedia)

Sorting is any technique or process of arranging items in some sequence and/or in different sets.Accordingly, it has two common, yet distinct meanings:

ordering: arranging items of the same kind, class, nature, etc. in some ordered sequence,

categorizing: grouping and labeling items with similar properties together (by sorts).

For the sorting to be unique, these two are restricted to a total order and a strict total order, respectively.For sorting we can either specify a weak order "should not come after" or a strict weak order"should come before" (specifying one defines also the other, the two are the complement of the inverse of each other, see operations on binary relations).

Sorting n-tuples (depending on context also called e.g. records consisting of fields) can be done based on one or more of its components. More generally objects can be sorted based on a property. Such a component or property is called a sort key.

For example, the items are books, the sort key is the title, subject or author, and the order is alphabetical.

A new sort key can be created from two or more sort keys by lexicographical order. The first is then called the primary sort key, the second the secondary sort key, etc.

For example, addresses could be sorted using the city as primary sort key, and the street as secondary sort key.

If the sort key values are totally ordered, the sort key defines a weak order of the items: items with the same sort key are equivalent with respect to sorting. If different items have different sort key values then this defines a unique order of the items.

A standard order is often called ascending (corresponding to the fact that the standard order of numbers is ascending, i.e. A to Z, 0 to 9), the reverse order descending (Z to A, 9 to 0).
Now if you sort on different keys, then you get different lists of header information (such as the author's name) with the appended tailing records (such as title or publisher). Sorting in computer science is one of the most extensively researched subjects because of the need to speed up the operation on thousands or millions of records during a search operation; see sorting algorithm.

The main purpose of sorting information is to optimise its usefulness for specific tasks. In general, there are two ways of grouping information: by category e.g. a shopping catalogue where items are compiled together under headings such as 'home', 'sport & leisure', 'women's clothes' etc. (nominal scale) and by the intensity of some property, such as price, e.g. from the cheapest to most expensive (ordinal scale). Richard Saul Wurman, in his book Information Anxiety, proposes that the most common sorting purposes are Name, by Location and by Time (these are actually special cases of category and hierarchy).

Together these give the acronym LATCH (Location, Alphabetical, Time, Category, Hierarchy) and can be used to describe just about every type of ordered information.

Often information is sorted using different methods at different levels of abstraction: e.g. the Nepal telephone directories which are sorted by location, by category (business or residential) and then alphabetically. New media still subscribe to these basic sorting methods: e.g. a Google search returns a list of web pages in a hierarchical list based on its own scoring system for how closely they match the search criteria (from closest match downwards).
The opposite of sorting, rearranging a sequence of items in a random or meaningless order, is called shuffling.

Link to Related Topics !

Insertion Sort

Selection Sort

Merge Sort

Hope u will enjoy !!!

Merge Sort

noreply@blogger.com (Ramesh) — Mon, 06 Sep 2010 18:05:00 +0000

Merge Sort: (Source Wikipedia)

Merge sort is an O(n log n) comparison-based sorting algorithm. In most implementations it is stable, meaning that it preserves the input order of equal elements in the sorted output. It is an example of the divide and conquer algorithmic paradigm. It was invented by John von Neumann in 1945.

Example of merge sort sorting a list of random dots.
Class	Sorting algorithm
Data structure	Array
Worst case performance	$Θ(n log n)$
Best case performance	$Θ(n log n)$ typical, $Θ(n)$ natural variant
Average case performance	$Θ(n log n)$
Worst case space complexity	$Θ(n)$ auxiliary

Algorithm
Conceptually, a merge sort works as follows
If the list is of length 0 or 1, then it is already sorted. Otherwise:

Divide the unsorted list into two sublists of about half the size.

Sort each sublist recursively by re-applying merge sort.

Merge the two sublists back into one sorted list.

Merge sort incorporates two main ideas to improve its runtime:
A small list will take fewer steps to sort than a large list.

Fewer steps are required to construct a sorted list from two sorted lists than two unsorted lists. For example, you only have to traverse each list once if they're already sorted (see the merge function below for an example implementation).

Example: Using merge sort to sort a list of integers contained in an array:
Suppose we have an array A with n indices ranging from $A 0$ to $A n - 1$ . We apply merge sort to $A (A 0 .. A c - 1)$ and $A (A c .. A n - 1)$ where c is the integer part of $n / 2$ . When the two halves are returned they will have been sorted. They can now be merged together to form a sorted array.
In a simple pseudocode form, the algorithm could look something like this:

function merge_sort(m)

if length(m) ≤ 1
return m
var list left, right, result

var integer middle = length(m) / 2

for each x in m up to middle
add x to left
for each x in m after middle
add x to right
left = merge_sort(left)
right = merge_sort(right)
result = merge(left, right)
return result

Following writing merge_sort function, then it is required to merge both the left and right lists created above. There are several variants for the merge() function; one possibility is this:
function merge(left,right)

var list result

while length(left) > 0 or length(right) > 0
if length(left) > 0 and length(right) > 0
if first(left) ≤ first(right)
append first(left) to result
left = rest(left)
else
append first(right) to result
right = rest(right)
else if length(left) > 0
append first(left) to result
left = rest(left)
else if length(right) > 0
append first(right) to result
right = rest(right)
end while
return result
Analysis

A recursive merge sort algorithm used to sort an array of 7 integer values. These are the steps a human would take to emulate merge sort (top-down).
In sorting n objects, merge sort has an average and worst-case performance of O(n log n). If the running time of merge sort for a list of length n is T(n), then the recurrence T(n) = 2T(n/2) + n follows from the definition of the algorithm (apply the algorithm to two lists of half the size of the original list, and add the n steps taken to merge the resulting two lists). The closed form follows from the master theorem.
In the worst case, merge sort does an amount of comparisons equal to or slightly smaller than (n ⌈lg n⌉ - 2^⌈lg n⌉ + 1), which is between (n lg n - n + 1) and (n lg n + n + O(lg n)).^[1]
For large n and a randomly ordered input list, merge sort's expected (average) number of comparisons approaches α·n fewer than the worst case where

In the worst case, merge sort does about 39% fewer comparisons than quicksort does in the average case; merge sort always makes fewer comparisons than quicksort, except in extremely rare cases, when they tie, where merge sort's worst case is found simultaneously with quicksort's best case. In terms of moves, merge sort's worst case complexity is O(n log n)—the same complexity as quicksort's best case, and merge sort's best case takes about half as many iterations as the worst case.

Recursive implementations of merge sort make 2n − 1 method calls in the worst case, compared to quicksort's n, thus merge sort has roughly twice as much recursive overhead as quicksort. However, iterative, non-recursive implementations of merge sort, avoiding method call overhead, are not difficult to code. Merge sort's most common implementation does not sort in place; therefore, the memory size of the input must be allocated for the sorted output to be stored in (see below for versions that need only n/2 extra spaces).

Merge sort as described here also has an often overlooked, but practically important, best-case property. If the input is already sorted, its complexity falls to O(n). Specifically, n-1 comparisons and zero moves are performed, which is the same as for simply running through the input, checking if it is pre-sorted.

Sorting in-place is possible (e.g., using lists rather than arrays) but is very complicated, and will offer little performance gains in practice, even if the algorithm runs in O(n log n) time. (Katajainen, Pasanen & Teuhola 1996) In these cases, algorithms like heapsort usually offer comparable speed, and are far less complex. Additionally, unlike the standard merge sort, in-place merge sort is not a stable sort. In the case of linked lists the algorithm does not use more space than that the already used by the list representation, but the O(log(k)) used for the recursion trace.

Merge sort is more efficient than quick sort for some types of lists if the data to be sorted can only be efficiently accessed sequentially, and is thus popular in languages such as Lisp, where sequentially accessed data structures are very common. Unlike some (efficient) implementations of quicksort, merge sort is a stable sort as long as the merge operation is implemented properly.

As can be seen from the procedure merge sort, there are some demerits. One complaint we might raise is its use of 2n locations; the additional n locations were needed because one couldn't reasonably merge two sorted sets in place. But despite the use of this space the algorithm must still work hard: The contents of m are first copied into left and right and later into the list result on each invocation of merge_sort (variable names according to the pseudocode above). An alternative to this copying is to associate a new field of information with each key (the elements in m are called keys). This field will be used to link the keys and any associated information together in a sorted list (a key and its related information is called a record). Then the merging of the sorted lists proceeds by changing the link values; no records need to be moved at all. A field which contains only a link will generally be smaller than an entire record so less space will also be used.

Another alternative for reducing the space overhead to n/2 is to maintain left and right as a combined structure, copy only the left part of m into temporary space, and to direct the merge routine to place the merged output into m. With this version it is better to allocate the temporary space outside the merge routine, so that only one allocation is needed. The excessive copying mentioned in the previous paragraph is also mitigated, since the last pair of lines before the return result statement (function merge in the pseudo code above) become superfluous.
Merge sorting tape drives

Merge sort type algorithms allowed large data sets to be sorted on early computers that had small random access memories by modern standards. Records were stored on magnetic tape and processed on banks of magnetic tape drives, such as these IBM 729s.
Merge sort is so inherently sequential that it is practical to run it using slow tape drives as input and output devices. It requires very little memory, and the memory required does not depend on the number of data elements.
For the same reason it is also useful for sorting data on disk that is too large to fit entirely into primary memory. On tape drives that can run both backwards and forwards, merge passes can be run in both directions, avoiding rewind time.
If you have four tape drives, it works as follows:
Divide the data to be sorted in half and put half on each of two tapes

Merge individual pairs of records from the two tapes; write two-record chunks alternately to each of the two output tapes

Merge the two-record chunks from the two output tapes into four-record chunks; write these alternately to the original two input tapes

Merge the four-record chunks into eight-record chunks; write these alternately to the original two output tapes

Repeat until you have one chunk containing all the data, sorted --- that is, for log n passes, where n is the number of records.

For almost-sorted data on tape, a bottom-up "natural merge sort" variant of this algorithm is popular.
The bottom-up "natural merge sort" merges whatever "chunks" of in-order records are already in the data. In the worst case (reversed data), "natural merge sort" performs the same as the above—it merges individual records into 2-record chunks, then 2-record chunks into 4-record chunks, etc. In the best case (already mostly-sorted data), "natural merge sort" merges large already-sorted chunks into even larger chunks, hopefully finishing in fewer than log n passes.
In a simple pseudocode form, the "natural merge sort" algorithm could look something like this:
# Original data is on the input tape; the other tapes are blank

function merge_sort(input_tape, output_tape, scratch_tape_C, scratch_tape_D)
while any records remain on the input_tape
while any records remain on the input_tape
merge( input_tape, output_tape, scratch_tape_C)
merge( input_tape, output_tape, scratch_tape_D)
while any records remain on C or D
merge( scratch_tape_C, scratch_tape_D, output_tape)
merge( scratch_tape_C, scratch_tape_D, input_tape)
the single given output_tape. # tapes are scanned linearly. # tape[next] gives the record cur
# take the next sorted chunk from the input tapes, and merge int orently under the read head of that tape. # tape[current] gives the record previously under the read head of that tape.
# (Generally both tape[current] and tape[previous] are buffered in RAM ...)
function merge(left[], right[], output_tape[])
do
if left[current] ≤ right[current]
append left[current] to output_tape
read next record from left tape
else
append right[current] to output_tape
read next record from right tape
while left[current] < left[next] and right[current] < right[next]
if left[current] < left[next]
append current_left_record to output_tape
if right[current] < right[next]
append current_right_record to output_tape
return
Either form of merge sort can be generalized to any number of tapes.
Optimizing merge sort
On modern computers, locality of reference can be of paramount importance in software optimization, because multi-level memory hierarchies are used. Cache-aware versions of the merge sort algorithm, whose operations have been specifically chosen to minimize the movement of pages in and out of a machine's memory cache, have been proposed. For example, the tiled merge sort algorithm stops partitioning subarrays when subarrays of size S are reached, where S is the number of data items fitting into a single page in memory. Each of these subarrays is sorted with an in-place sorting algorithm, to discourage memory swaps, and normal merge sort is then completed in the standard recursive fashion. This algorithm has demonstrated better performance on machines that benefit from cache optimization. (LaMarca & Ladner 1997)
Kronrod (1969) suggested an alternative version of merge sort that uses constant additional space. This algorithm was refined by Katajainen, Pasanen & Teuhola (1996).
Comparison with other sort algorithms
Although heapsort has the same time bounds as merge sort, it requires only Θ(1) auxiliary space instead of merge sort's Θ(n), and is often faster in practical implementations. On typical modern architectures, efficient quicksort implementations generally outperform mergesort for sorting RAM-based arrays. On the other hand, merge sort is a stable sort, parallelizes better, and is more efficient at handling slow-to-access sequential media. Merge sort is often the best choice for sorting a linked list: in this situation it is relatively easy to implement a merge sort in such a way that it requires only Θ(1) extra space, and the slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.
As of Perl 5.8, merge sort is its default sorting algorithm (it was quicksort in previous versions of Perl). In Java, the Arrays.sort() methods use merge sort or a tuned quicksort depending on the datatypes and for implementation efficiency switch to insertion sort when fewer than seven array elements are being sorted.^[2] Python uses timsort, another tuned hybrid of merge sort and insertion sort, which will also become the standard sort algorithm for Java SE 7.
Utility in online sorting
Merge sort's merge operation is useful in online sorting, where the list to be sorted is received a piece at a time, instead of all at the beginning. In this application, we sort each new piece that is received using any sorting algorithm, and then merge it into our sorted list so far using the merge operation. However, this approach can be expensive in time and space if the received pieces are small compared to the sorted list — a better approach in this case is to store the list in a self-balancing binary search tree and add elements to it as they are received.

Selection Sort

noreply@blogger.com (Ramesh) — Mon, 06 Sep 2010 17:58:00 +0000

Selection Sort:

Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n²) complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations.

Algorithm

The algorithm works as follows:

Find the minimum value in the list
Swap it with the value in the first position
Repeat the steps above for the remainder of the list (starting at the second position and advancing each time)

Effectively, the list is divided into two parts: the sublist of items already sorted, which is built up from left to right and is found at the beginning, and the sublist of items remaining to be sorted, occupying the remainder of the array.

Here is an example of this sort algorithm sorting five elements:

64 25 12 22 11


1 25 12 22 64
1

12 25 22 64
1
111 12 22 25 64


11 12 22 25 64

(nothing appears changed on this last line because the last 2 numbers were already in order)

Selection sort can also be used on list structures that make add and remove efficient, such as a linked list. In this case it's more common to remove the minimum element from the remainder of the list, and then insert it at the end of the values sorted so far. For example:

64 25 12 22 11


1 64 25 12 22
1

12 64 25 22
1
111 12 22 64 25


11 12 22 25 64


Mathematical 

definition



Let  $L$  be a non-empty set and 

 such that  $f (L) = L'$  
where:


 


 $L'$  is a permutation


 of  $L$ ,

 




for all 
and ,

 
,

 


 $s$  is the smallest element of  $L$ ,


and

 


 $L s$  is the set 


of elements of  $L$  without one 

instance of the smallest element of  $L$ .

 

Analysis

Selection sort is not difficult to analyze compared to other sorting algorithms since none of the loops depend on the data in the array. Selecting the lowest element requires scanning all n elements (this takes n − 1 comparisons) and then swapping it into the first position. Finding the next lowest element requires scanning the remaining n − 1 elements and so on, for (n − 1) + (n − 2) + ... + 2 + 1 = n(n − 1) / 2 ∈ Θ(n²) comparisons (see arithmetic progression). Each of these scans requires one swap for n − 1 elements (the final element is already in place).

Comparison to other sorting algorithms
Among simple average-case Θ(n²) algorithms, selection sort almost always outperforms bubble sort and gnome sort, but is generally outperformed by insertion sort. Insertion sort is very similar in that after the kth iteration, the first k elements in the array are in sorted order. Insertion sort's advantage is that it only scans as many elements as it needs in order to place the k + 1st element, while selection sort must scan all remaining elements to find the k + 1st element.
Simple calculation shows that insertion sort will therefore usually perform about half as many comparisons as selection sort, although it can perform just as many or far fewer depending on the order the array was in prior to sorting. It can be seen as an advantage for some real-time applications that selection sort will perform identically regardless of the order of the array, while insertion sort's running time can vary considerably. However, this is more often an advantage for insertion sort in that it runs much more efficiently if the array is already sorted or "close to sorted."
Another key difference is that selection sort always performs Θ(n) swaps, while insertion sort performs Θ(n²) swaps in the average and worst cases. Because swaps require writing to the array, selection sort is preferable if writing to memory is significantly more expensive than reading. This is generally the case if the items are huge but the keys are small. Another example where writing times are crucial is an array stored in EEPROM or Flash. There is no other algorithm with less data movement.
Finally, selection sort is greatly outperformed on larger arrays by Θ(n log n) divide-and-conquer algorithms such as mergesort. However, insertion sort or selection sort are both typically faster for small arrays (i.e. fewer than 10-20 elements). A useful optimization in practice for the recursive algorithms is to switch to insertion sort or selection sort for "small enough" sublists.

Variants
Heapsort greatly improves the basic algorithm by using an implicit heap data structure to speed up finding and removing the lowest datum. If implemented correctly, the heap will allow finding the next lowest element in Θ(log n) time instead of Θ(n) for the inner loop in normal selection sort, reducing the total running time to Θ(n log n).
A bidirectional variant of selection sort, called cocktail sort, is an algorithm which finds both the minimum and maximum values in the list in every pass. This reduces the number of scans of the list by a factor of 2, eliminating some loop overhead but not actually decreasing the number of comparisons or swaps. Note, however, that cocktail sort more often refers to a bidirectional variant of bubble sort.
Selection sort can be implemented as a stable sort. If, rather than swapping in step 2, the minimum value is inserted into the first position (that is, all intervening items moved down), the algorithm is stable. However, this modification either requires a data structure that supports efficient insertions or deletions, such as a linked list, or it leads to performing Θ(n²) writes.
In the bingo sort variant, items are ordered by repeatedly looking through the remaining items to find the greatest value and moving all items with that value to their final location. Like counting sort, this is an efficient variant if there are many duplicate values. Indeed, selection sort does one pass through the remaining items for each item moved. Bingo sort does two passes for each value (not item): one pass to find the next biggest value, and one pass to move every item with that value to its final location. Thus if on average there are more than two items with each value, bingo sort may be faster.

(Source Wikipedia)

Model question of Wireless Networking

noreply@blogger.com (Ramesh) — Mon, 06 Sep 2010 17:50:00 +0000

Tribhuwan University

Bachelor of Computer Science and information Technology
Wireless Networking

Course Title: Wireless Netwoking Full Marks : 60 + 20 + 20

Course no : CSC-308 Pass Marks: 24+8+8

Credit Hrs : 3Hrs

Nature of course: Theory (3 Hrs.)

Course Synopsis: This course contains the concept of wireless networking technology.

Goal: To provide the concept and working principle for wireless communication and networking.

Model Questions:

Click for syllabus

Attempt all questions: 10 * 6 = 60

1) List out the keypoints of wireless communication development. What are the challenges in wireless communication network? [3+3]

2) A GSM system operating at 900 MHz has operating power of 40W. The transmitter and receiver gain are 5 dB each. By using free space path loss.

a. Express the transmission power in dBm.

b. Calculate free space path loss between the BS and MS separated by 5 km.

c. Calculate received power. [3*2]

3)   Define modulation. Explain about GMSK transmitter and receiver. [1+3+2]

4)  Define diversity. Explain different diversity mechanism. [2+4]

5)   Explain the concept of frequency reuse. In AMPS cellular system with 30 kHz channel BW, a S/I of 18 dB is required for acceptable speech quality. By using path loss exponent of 4,
      a) Calculate D/R.
   b) Calculate the cluster size or frequency reuse factor. [3+3]

6) Explain briefly about different techniques for capacity increase in cellular system. [6]

7) What is multiple access technique? Write briefly on TDMA with its advantages over FDMA. [1+5]

8) Describe the steps involved in setting up the call between the calling MSC and the called MSC with flow diagram. [6]

9) Write briefly on operation of mobile IP. [6]

10) Write short notes on [any two] [2*3]

a. Rayleigh fading

b. QPSK

c. MIPv4 vs MIPv6

d. Handoff management

Insertion Sort

noreply@blogger.com (Ramesh) — Mon, 06 Sep 2010 17:44:00 +0000

Insertion sort:

Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:

Simple implementation
Efficient for (quite) small data sets
Adaptive, i.e. efficient for data sets that are already substantially sorted: the time complexity is O(n + d), where d is the number of inversions
More efficient in practice than most other simple quadratic, i.e. O(n²) algorithms such as selection sort or bubble sort; the best case (nearly sorted input) is O(n)
Stable, i.e. does not change the relative order of elements with equal keys
In-place, i.e. only requires a constant amount O(1) of additional memory space
Online, i.e. can sort a list as it receives it.

Most humans when sorting—ordering a deck of cards, for example—use a method that is similar to insertion sort.

Algorithm

Every repetition of insertion sort removes an element from the input data, inserting it into the correct position in the already-sorted list, until no input elements remain. The choice of which element to remove from the input is arbitrary, and can be made using almost any choice algorithm.
Sorting is typically done in-place. The resulting array after k iterations has the property where the first k + 1 entries are sorted. In each iteration the first remaining entry of the input is removed, inserted into the result at the correct position, thus extending the result:

becomes

with each element greater than x copied to the right as it is compared against x.
The most common variant of insertion sort, which operates on arrays, can be described as follows:

Suppose there exists a function called Insert designed to insert a value into a sorted sequence at the beginning of an array. It operates by beginning at the end of the sequence and shifting each element one place to the right until a suitable position is found for the new element. The function has the side effect of overwriting the value stored immediately after the sorted sequence in the array.
To perform an insertion sort, begin at the left-most element of the array and invoke Insert to insert each element encountered into its correct position. The ordered sequence into which the element is inserted is stored at the beginning of the array in the set of indices already examined. Each insertion overwrites a single value: the value being inserted.

Pseudocode of the complete algorithm follows, where the arrays are zero-based and the for-loop includes both the top and bottom limits (as in Pascal):

insertionSort(array A)
begin
    for i := 1 to length[A]-1 do
    begin
        value := A[i];
        j := i - 1;
        done := false;
        repeat
            if A[j] > value then
            begin
                A[j + 1] := A[j];
                j := j - 1;
                if j < 0 then
                    done := true;
            end
            else
                done := true;
        until done;
        A[j + 1] := value;
    end;
end;

Below is the pseudocode for insertion sort (as in C):

1. for j ← to length(A)
2. do key ← A[ j ]
3. > A[ j ] is added in the sorted sequence A[1, .. j-1]
4. i ← j - 1
5. while i >= 0 and A [ i ] > key
6. do A[ i +1 ] ← A[ i ]
7. i ← i -1
8. A [i +1] ← key

Best, worst, and average cases

Graphical example.

The best case input is an array that is already sorted. In this case insertion sort has a linear running time (i.e., Θ(n)). During each iteration, the first remaining element of the input is only compared with the right-most element of the sorted subsection of the array.
The worst case input is an array sorted in reverse order. In this case every iteration of the inner loop will scan and shift the entire sorted subsection of the array before inserting the next element. For this case insertion sort has a quadratic running time (i.e., O(n²)).
The average case is also quadratic, which makes insertion sort impractical for sorting large arrays. However, insertion sort is one of the fastest algorithms for sorting very small arrays, even faster than quick sort; indeed, good quick sort implementation use insertion sort for arrays smaller than a certain threshold, also when arising as subproblems; the exact threshold must be determined experimentally and depends on the machine, but is commonly around ten.
Example: The following table shows the steps for sorting the sequence {5, 7, 0, 3, 4, 2, 6, 1}. For each iteration, the number of positions the inserted element has moved is shown in parentheses. Altogether this amounts to 17 steps.

5 7 0 3 4 2 6 1 (0)

5 7 0 3 4 2 6 1 (0)
0 5 7 3 4 2 6 1 (2)
0 3 5 7 4 2 6 1 (2)
0 3 4 5 7 2 6 1 (2)
0 2 3 4 5 7 6 1 (4)
0 2 3 4 5 6 7 1 (1)
0 1 2 3 4 5 6 7 (6)

Comparisons to other sorting algorithms

Insertion sort is very similar to selection sort. As in selection sort, after k passes through the array, the first k elements are in sorted order. For selection sort these are the k smallest elements, while in insertion sort they are whatever the first k elements were in the unsorted array. Insertion sort's advantage is that it only scans as many elements as needed to determine the correct location of the k+1^th element, while selection sort must scan all remaining elements to find the absolute smallest element.
Calculations show that insertion sort will usually perform about half as many comparisons as selection sort. Assuming the k+1^th element's rank is random, insertion sort will on average require shifting half of the previous k elements, while selection sort always requires scanning all unplaced elements. If the input array is reverse-sorted, insertion sort performs as many comparisons as selection sort. If the input array is already sorted, insertion sort performs as few as n-1 comparisons, thus making insertion sort more efficient when given sorted or "nearly-sorted" arrays.
While insertion sort typically makes fewer comparisons than selection sort, it requires more writes because the inner loop can require shifting large sections of the sorted portion of the array. In general, insertion sort will write to the array O(n²) times, whereas selection sort will write only O(n) times. For this reason selection sort may be preferable in cases where writing to memory is significantly more expensive than reading, such as with EEPROM or flash memory.
Some divide-and-conquer algorithms such as quicksort and mergesort sort by recursively dividing the list into smaller sublists which are then sorted. A useful optimization in practice for these algorithms is to use insertion sort for sorting small sublists, where insertion sort outperforms these more complex algorithms. The size of list for which insertion sort has the advantage varies by environment and implementation, but is typically between eight and twenty elements.

Variants

D.L. Shell made substantial improvements to the algorithm; the modified version is called Shell sort. The sorting algorithm compares elements separated by a distance that decreases on each pass. Shell sort has distinctly improved running times in practical work, with two simple variants requiring O(n^3/2) and O(n^4/3) running time.
If the cost of comparisons exceeds the cost of swaps, as is the case for example with string keys stored by reference or with human interaction (such as choosing one of a pair displayed side-by-side), then using binary insertion sort may yield better performance. Binary insertion sort employs a binary search to determine the correct location to insert new elements, and therefore performs comparisons in the worst case, which is Θ(n log n). The algorithm as a whole still has a running time of Θ(n²) on average because of the series of swaps required for each insertion.
The number of swaps can be reduced by calculating the position of multiple elements before moving them. For example, if the target position of two elements is calculated before they are moved into the right position, the number of swaps can be reduced by about 25% for random data. In the extreme case, this variant works similar to merge sort.
To avoid having to make a series of swaps for each insertion, the input could be stored in a linked list, which allows elements to be inserted and deleted in constant-time. However, performing a binary search on a linked list is impossible because a linked list does not support random access to its elements; therefore, the running time required for searching is O(n²). If a more sophisticated data structure (e.g., heap or binary tree) is used, the time required for searching and insertion can be reduced significantly; this is the essence of heap sort and binary tree sort.
In 2004 Bender, Farach-Colton, and Mosteiro published a new variant of insertion sort called library sort or gapped insertion sort that leaves a small number of unused spaces (i.e., "gaps") spread throughout the array. The benefit is that insertions need only shift elements over until a gap is reached. The authors show that this sorting algorithm runs with high probability in O(n log n) time.^[2]

CSIT PROGRAM IN NEPAL

Model question of Desing Algorithm Analysis and Design

Advantages / Disadvantages of fiber optic cable

Types of Computer Network and Transmission Media

Application of Computer Network

Computer Network, Chapter One

Advantages of computer network

Introduction of Networks

Types of agent

Artificial Agent

Notes of Computer Networks

Notes of Algorithm Design & Analysis

Data Communications

Simulation And Modeling

Wireless Networking

Artificial Intelligence

Data Flow

Data Representation

Data Communications

Components of Data Communications System

About Sorting

Merge Sort

Algorithm

Analysis

Merge sorting tape drives

Optimizing merge sort

Comparison with other sort algorithms

Utility in online sorting

Selection Sort

Algorithm

Mathematical definition

Analysis

Model question of Wireless Networking

Insertion Sort

Best, worst, and average cases

Comparisons to other sorting algorithms

Variants

Mathematical

definition