Searching
·
Linear/ Sequential Search
·
Binary Search (Binary Chop)
· Linear/ Sequential Search
In computer
science, linear search or sequential search is a method
for finding a particular value in a list that checks each element in sequence
until the desired element is found or the list is exhausted.
· Binary Search (Binary Chop)
In computer science, a binary search or half-interval search algorithm finds the position of a target value within a sorted array.
The binary
search algorithm begins by comparing the target value to the value of the
middle element of the sorted array. If the target value is equal to the middle
element's value, then the position is returned and the search is finished. If
the target value is less than the middle element's value, then the search
continues on the lower half of the array; or if the target value is greater
than the middle element's value, then the search continues on the upper half of
the array. This process continues, eliminating half of the elements, and
comparing the target value to the value of the middle element of the remaining
elements - until the target value is either found (and its associated element
position is returned), or until the entire array has been searched (and
"not found" is returned).
Binary
Search Java Code
1
int[] data;
2
int size;
3
4
public boolean binarySearch(int key)
5 {
6
int low = 0;
7
int high = size - 1;
8
9
while(high >= low) {
10
int middle = (low + high) / 2;
11
if(data[middle] == key) {
12 return true;
13
}
14
if(data[middle] < key) {
15 low = middle + 1;
16
}
17
if(data[middle] > key) {
18 high = middle - 1;
19
}
20
}
21
return false;
22 }
3 Control Structures
According
to the structure
theorem, any computer
program can be written using the basic control structures shown in Figure 3-1. They can be combined in any way necessary to deal with a given
problem.
Figure
3-1 Control Structures
Stacks and Queues
Stacks
|
A stack is a container of objects that are inserted and
removed according to the last-in first-out (LIFO) principle. In the pushdown
stacks only two operations are allowed: push the item into the stack, and pop the item out of the
stack. A stack is a limited access data structure - elements can be added and
removed from the stack only at the top. push adds an item to the top of the
stack, pop removes the item from the top. A
helpful analogy is to think of a stack of books; you can remove only the top
book, also you can add a new book on the top.
Applications of stack
|
 |
Queues
|
A queue is a container of objects (a linear collection)
that are inserted and removed according to the first-in first-out (FIFO)
principle. An excellent example of a queue is a line of students in the food
court of the UC. New additions to a line made to the back of the queue, while
removal (or serving) happens in the front. In the queue only two operations
are allowed enqueue and dequeue. Enqueue means to
insert an item into the back of the queue, dequeue means removing the front
item. The picture demonstrates the FIFO access.
The difference between stacks and queues is in removing. In a stack we
remove the item the most recently added; in a queue, we remove the item the
least recently added. |
 |
Difference between Sequential and
Parallel Programming
Parallel programming involves
the concurrent computation or simultaneous execution of processes or threads at
the same time. While Sequential programming involves a consecutive and ordered
execution of processes one after another.
In other words with
sequential programming, processes are run one after another in a succession
fashion while in parallel computing, you have multiple processes execute at the
same time. With sequential programming, computation is modeled after problems
with a chronological sequence of events.
The program in such cases
will execute a process that will in turn wait for user input, then another
process is executed that processes a return according to user input creating a
series of cascading events. In contrast to sequential computation, parallel
programming, while processes might execute concurrently, yet sub-processes or
threads might communicate and exchange signals during execution and therefore
programmers have to place measures in place to allow for such transactions.
Software Types
The term 'software' refers to the set of electronic
program instructions or data a computer processor reads in order to perform a
task or operation. In contrast, the term 'hardware' refers to the
physical components that you can see and touch, such as the computer hard
drive, mouse, and keyboard.
Software can be categorized according to what it is designed to
accomplish. There are two main types of software: systems software and application software.
Systems Software
Systems software includes the
programs that are dedicated to managing the computer itself, such as the operating system, file management utilities, and disk operating system (or DOS).
The operating system manages the computer hardware resources in addition to
applications and data. Without systems software installed in our computers we
would have to type the instructions for everything we wanted the computer to
do!
Applications Software
Application software, or simply applications, are often called
productivity programs or end-user programs because they enable the user to
complete tasks such as creating documents, spreadsheets, databases, and
publications, doing online research, sending email, designing graphics, running
businesses, and even playing games! Application software is specific to the
task it is designed for and can be as simple as a calculator application or as
complex as a word processing application. When you begin creating a document,
the word processing software has already set the margins, font style and size,
and the line spacing for you. But you can change these settings, and you have
many more formatting options available. For example, the word processor
application makes it easy to add color, headings, and pictures or delete, copy,
move, and change the document's appearance to suit your needs.
No comments:
Post a Comment