Data Structure Sequential Searches

June 1, 2011 james

Let’s examine how long it will take to find an item matching a key in the collections we have discussed so far. We’re interested in:

  1. the average time
  2. the worst-case time and
  3. the best possible time.

However, we will generally be most concerned with the worst-case time as calculations based on worst-case times can lead to guaranteed performance predictions. Conveniently, the worst-case times are generally easier to calculate than average times.

If there are n items in our collection – whether it is stored as an array or as a linked list – then it is obvious that in the worst case, when there is no item in the collection with the desired key, then n comparisons of the key with keys of the items in the collection will have to be made.

To simplify analysis and comparison of algorithms, we look for a dominant operation and count the number of times that dominant operation has to be performed. In the case of searching, the dominant operation is the comparison, since the search requires n comparisons in the worst case, we say this is a O(n) (pronounce this “big-Oh-n” or “Oh-n”) algorithm. The best case – in which the first comparison returns a match – requires a single comparison and is O(1). The average time depends on the probability that the key will be found in the collection – this is something that we would not expect to know in the majority of cases. Thus in this case, as in most others, estimation of the average time is of little utility. If the performance of the system is vital, i.e. it’s part of a life-critical system, then we must use the worst case in our design calculations as it represents the best guaranteed performance.

Data Structures , Leave a comment

Binary Search on int Array using Java

May 30, 2011 james

import java.util.Arrays;

public class BinarySearchIntArrayExample {

public static void main(String[] args) {
//create int array
int intArray[] = {1,2,4,5};

/*
To perform binary search on int array use
int binarySearch(int[] b, int value) of Arrays class. This method searches
the int array for specified int value using binary search algorithm.
Please note that the int array MUST BE SORTED before it can be searched
using binarySearch method.
This method returns the index of the value to be searched, if found in the
array.
Otherwise it returns (- (X) – 1)
where X is the index where the the search value would be inserted.
i.e. index of first element that is grater than the search
value or array.length, if all elements of an array are less than
the search value.
*/

//sort int array using Arrays.sort method
Arrays.sort(intArray);

//value to search
int searchValue = 2;

//since 2 is present in int array, index of it would be returned
int intResult = Arrays.binarySearch(intArray,searchValue);
System.out.println(“Result of binary search of 2 is : ” + intResult);

//lets search something which is not in int array!
searchValue = 3;
intResult = Arrays.binarySearch(intArray,searchValue);
System.out.println(“Result of binary search of 3 is : ” + intResult);

}
}

/*
Output would be
Result of binary search of 2 is : 1
Result of binary search of 3 is : -3
*/

Java Programming , , Leave a comment

Binary Search Data Structure

May 29, 2011 james

There is quite obviously no way to speed up a search, unless more information is available about the searched data. It is well known that a search can be made much more effective, if the data are ordered. Imagine, for example, a telephone directory in which the names were not alphabetically listed. It would be utterly useless. We shall therefore present an algorithm which makes use of the knowledge that a is ordered, i.e., of the condition

Ak: 1≤k < N : ak-1≤ak

The key idea is to inspect an element picked at random, say am, and to compare it with the search argument x. If it is equal to x, the search terminates; if it is less than x, we infer that all elements with indices less or equal to m can be eliminated from further searches; and if it is greater than x, all with index greater or equal to m can be eliminated. This results in the following algorithm called binary search; it uses two index variables L and R marking the left and at the right end of the section of a in which an element may still be found.

L := 0; R := N-1; found := FALSE ;

WHILE (L≤R) & ~found DO

m := any value between L and R;

IF a[m] = x THEN found := TRUE

ELSIF a[m] < x THEN L := m+1

ELSE R := m-1

END

END

The loop invariant, i.e. the condition satisfied before each step, is

(L≤R) & (Ak : 0≤k < L : ak < x) & (Ak : R < k < N : ak > x)

from which the result is derived as

found OR ((L > R) & (Ak : 0≤k < L : ak < x ) & (Ak : R < k < N : ak > x))

which implies

(am = x) OR (Ak : 0≤k < N : ak≠x)

The choice of m is apparently arbitrary in the sense that correctness does not depend on it. But it does influence the algorithm’s effectiveness. Clearly our goal must be to eliminate in each step as many elements as possible from further searches, no matter what the outcome of the comparison is. The optimal solution is to choose the middle element, because this eliminates half of the array in any case. As a result, the maximum number of steps is log2N, rounded up to the nearest integer. Hence, this algorithm offers a drastic improvement over linear search, where the expected number of comparisons is N/2.

The efficiency can be somewhat improved by interchanging the two if-clauses. Equality should be tested second, because it occurs only once and causes termination. But more relevant is the question, whether – as in the case of linear search — a solution could be found that allows a simpler condition for termination. We indeed find such a faster algorithm, if we abandon the naive wish to terminate the search as soon as a match is established. This seems unwise at first glance, but on closer inspection we realize that the gain in efficiency at every step is greater than the loss incurred in comparing a few extra elements. Remember that the number of steps is at most log N. The faster solution is based on the following invariant:

(Ak : 0≤k < L : ak < x) & (Ak : R≤k < N : ak≥x)

and the search is continued until the two sections span the entire array.

L := 0; R := N;

WHILE L < R DO

m := (L+R) DIV 2;

IF a[m] < x THEN L := m+1 ELSE R := m END

END

The terminating condition is L≥R. Is it guaranteed to be reached? In order to establish this guarantee, we must show that under all circumstances the difference R-L is diminished in each step. L < R holds at the 36 beginning of each step. The arithmetic mean m then satisfies L≤m < R. Hence, the difference is indeed diminished by either assigning m+1 to L (increasing L) or m to R (decreasing R), and the repetition terminates with L = R. However, the invariant and L = R do not yet establish a match. Certainly, if R = N, no match exists. Otherwise we must take into consideration that the element a[R] had never been compared. Hence, an additional test for equality a[R] = x is necessary. In contrast to the first solution, this algorithm — like linear search — finds the matching element with the least index.

Data Structures , , Leave a comment

What is VPN (Virtual Private Network)

May 26, 2011 james

A private network can provide privacy to an organization when sending information among different cities or countries offices of that organization. But establishing a dedicated link between different office among the cities or even countries involve lots of cost. This link cost can be minimized if we use the virtual private network technology where we do not need any private link among offices but Internet. VPN creates a network that is private but virtual since it uses the global Internet. It is private because it guarantees privacy inside the organization. It is virtual because it does not use real private WANs; the network is physically public but virtually private due use of security features. Usually VPN technology uses two simultaneous techniques to establish privacy and those two are: encryption/authentication of the data to be sent and creating the tunnel between the receiver and sender.

Data Communication and Networks , , Leave a comment

Key Features of Agile Software Development

May 26, 2011 james
  1. Iterative: Entire application is distributed in incremental units called as iteration. Development time of each iteration is small (couple of weeks), fixed and strictly adhered to. Every Iteration is a mini increment of the functionality and is build on top of previous iteration.
  2. Active Customer involvement: There is lot of client involvement and face-to-face interaction. Every iteration is tested and approved by client. The feedback obtained is implemented in subsequent iterations; thus minimizing risk and ensuring higher client satisfaction.
  3. Feature driven: More emphasis is on providing the required features in the application. 80/20 principle is applied to decide the 20% features which would be used 80% of the time.
  4. Fixed Time: Each iteration has a fixed time span in which it is delivered.
  5. Priority based delivery: Features are prioritized depending on customer need, development risk etc. High priority features are developed first. After every iteration, the project priorities are re-evaluated.
  6. Adaptive: The methodology in general is very adaptive, so that the application that is developed can cater to inflow of new requirements throughout its development. Goal is not to remove the uncertainty in the very beginning, but is to adapt to the changing needs.
  7. Empowered Teams: The project teams are generally small and have lot of interaction and communication. Since entire team is actively involved, team is empowered to take decisions. No separate team to manage project.
  8. People Centric: More emphasis is on using the adequately skilled people to do the development than on following the processes. The documentation and other non-development activities are minimized and more time is devoted to development and testing.
  9. Rapid development: Generally the development is done rapidly using light weight development technologies.
  10. More disciplined: Being rapid, everything has to be delivered correctly first time. So the process involves lot of team and self discipline Thus, it requires highly skilled and organized team members.
  11. Simplicity: Emphasis is on keeping things as simple as possible and being open to change.
Software, Web , , , Leave a comment

8088 Microprocessor

May 26, 2011 james

Soon after this in 1979 Intel introduced another microprocessor 8088 which is similar in architecture to 8086 but the difference is in the available number of data bits of the data bus, they were limited to 8-bits even though the ALU is of 16-bits. This is for 8-bit applications requiring higher computational power. It had a pre-fetch queue of 4 instructions. A pivotal sale to IBM made the Intel 8088 the brains of IBM’s new hit product—the IBM PC.

Microprocessor , , , , Leave a comment

8086 Microprocessor

May 26, 2011 james

In 1976 Intel decided to embark on a 16-bit project and the result was 8086 which came-in to market in 1978. 8086 is a 16-bit device with 10 times the performance of the 8080. It is build as an extension of the 8080’s architectural concepts, making it easier for customers to use and for Intel market. In this microcontroller first time pipelining was introduced which furthermore increased the execution speed. Segmentation of memory i.e. dividing the memory space in to different segments for example code , data and stack segment was introduced for the first time. This segmentation of memory enabled the microprocessor to address the memory even though it had no register which could hold 20 bit address. This was done using two registers base register and offset register to which a 0H had been hard wired in to the register as the lower nibble of base register and the higher nibble of offset register. Thus when we add both of the register we get a 20-bit address. It had a pre-fetch queue of 6 instructions where in the instructions which were to be executed were fetching during execution of an instruction. Its architecture is designed to support parallel processing. It is made up of 29,000 MOS transistors and could work at clock rates of 5 to 10 MHz. It has a 16-bit ALU (Arithmetic and Logic Unit) and data bus but the width of address bus is 20-bit (could address only 1M byte of memory).

Microprocessor , , , Leave a comment

8085 Microprocessor

May 26, 2011 james

Two years later, in 1976 Intel came up with an improved version of 8080 which was called 8085. It use to work on a single 5v-power supply, is faster and integrated more functions. It consisted of 6,500 MOS transistor and could work at clock rates of 3 to 5MHz.

Microprocessor , , , Leave a comment

8080 Microprocessor

May 25, 2011 studiesinn

It soon became obvious to Intel and its competitors that there were almost limitless number of applications for microprocessors. A big advance came in 1974 with Intel’s 8080 chip, the first true general purpose microprocessor. It is much more highly integrated chip than its predecessors, with about 10 times the performance. It could execute about 290,000 operations a second and could address 64K bytes of memory. Both the 4004 and 8008 utilized the P-channel MOS technology, whereas the 8080 used the innovative N-channel MOS process yielding vast gains in speed, power, capacity and density. What’s more the 8080 required only 6 support chips for operation as opposed to 20 with the 8008. It consisted of 60,000 transistors and worked at clock rate of 2 MHz.

Microprocessor , , Leave a comment

8008 Microprocessor

May 25, 2011 studiesinn

The 8-bit 8008 microprocessor had been developed in tandem with the 4004 and was introduced in April 1972. It was intended to be a custom chip for Computer Terminals Corp. of Texas. But as it developed, CTC rejected the 8008 because it was too slow for the company’s purpose and required too many supporting chips. However, Intel offered the 8008 on the open market, where its orientation to data/character manipulation versus the 4004’s arithmetic orientation caught the eye of a new group of users. The 8008 is made up of 3,500 MOS transistors and could work at a clock rate of 200 KHz.

Microprocessor , , Leave a comment