Tribhuvan University Bachelor of Science in Computer Science And Information Technology Model Question: Full Marks : 80 + 20 Pass Marks : 32 + 8 Time : 3 hrs 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. You might also like --> |
Thursday, September 16, 2010
Model question of Desing Algorithm Analysis and Design
Wednesday, September 15, 2010
Advantages / Disadvantages of fiber optic cable
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
Triple Exposure Types of Computer Network |
Mainly, there are three kinds of computer networks given below;
>>> 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;
>>> 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
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 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 !!
Monday, September 13, 2010
Application of Computer Network
| Application of Computer Networks |
Computer Networks are applied in following fields;
>>> 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
| Subject Chapters for Computer Networks | Following Link Related Links for given chapters!!! |
|---|---|
| Introduction of Computer Network | |
| Advantages/Disadvantages of Computer network | |
| Applications of Computer N/W | |
| Types of N/W, Transmission Media | |
| Advantages/Disadvantagesoffiberoptics |
You might like this !!
Advantages of computer network
| Advantages of computer network |
A computer network has following advantages;
>>> 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;
>>> 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
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. |
Thursday, September 9, 2010
Types of agent
| # Simple Reflex Agent: The simple reflex agent has:
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:
# 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 ;
# 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 <<<
Click here to download: "Overview of Artificial Intelligence" |
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:
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:
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 |
Subscribe to:
Posts (Atom)
