Lecture 20 - System Software

This is the final lecture note for Software Development subject.

Compilers and Interpreters
A compiler is a program translator used for translating source program of high level languages in to machine executable form. That is the compiler is a program that takes in the C/C++ file(s) as an input and outputs an executable file that can then be directly run on the host computer.

Compilation Process
Compilation process consists of three stages;

Lexical Analysis
The source program of the programming language is scanned by the lexical analyzer to identify the commands, operators, identifiers, and tokens. After the identification it builds the syntax tree to detect any syntax or semantic errors.

Code Generation
During this stage for each and every rapid statement in the program machine code instructions are generated to prior the object program. In addition code optimization techniques are used to improve the efficiency of the program.

Linking
In the final stage separately compiled object codes in the external library functions are integrated to produce the final executable program.

If compilers are one extreme to running programming languages then pure interpreters are the other extreme. Pure interpreters do not do any code translation as done by compilers. These interpreters take the source code (which is written in a high language) and start executing the statements on the host machine one by one.

Comparison of compilers and interpreters

Compilers:

• Translated the whole program at once to produce the object code
• Can run the program independently 
• Repeated executions do not need re-translation of the code
• Syntax and sementic errors are detected before execution of the program
• Execution speed is much higher
• Run time memory requirement is less
• Source program code is hidden from the user

 Interpreters

• Translator execute the program statement by statement (line by line)
• Program is run under the control of the interpretor
• Every execution need to re-translate the program
• Errors are detected at the run time only
• Execution speed is much slower
• More memory is required at the run time
• Most of the time program source code can not be hidden

Some of the commercial programming languages have been known to be interpreted (Basic, Java) and yet these languages do not behave quiet like the description given above. The reason is simple - none -of the popular modern programming languages are pure-interpreter based. They are either compiled (like C/C++) or adopt a Hybrid approach (like Java, Basic).


Assembler
Assembly language is the closest thing you come to machine code It's a low level language which means that isn't as intelligent as high level languages like C or Pascal. It's harder to code in than those programs, but it runs much faster and you have total control of what you are doing. you should write programs all in assembly but use it as inline assembly in high level languages where you want it to run faster. Simplifies the task of writing machine code programs.

Lecture 19 - User Interface Design

The user interface is the aggregate of means by which people (the users) interact with a particular machine, device, computer program or other complex tool (the system). The user interface provides means of:

• Input, allowing the users to manipulate a system
• Output, allowing the system to produce the effects of the users manipulation

User Interface Types

Currently the following types of user interface are the most common:

Graphical User Interfaces (GUl)
Accept input via devices such as computer keyboard and mouse and provide articulated graphical output on the computer monitor. There are at least two different principles widely used in GUl design. object-oriented interfaces (OOUI) and application oriented interfaces.

Web-Based User Interfaces
Web-based user interfaces accept input and provide output by generating web pages which  are transported via the internet and viewed by the user using a web browser program. Newer implementations utilize Java, AJAX, Microsoft .NET, or similar technologies to provide real time control in a separate program, eliminating the need to refresh a traditional HTML based web browser.

Command-Line Interfaces (CLI)
Command-line inter-faces, where the user provides the input by typing a command string with the computer keyboard and the system provides output by printing text on the computer monitor. Used for system administration tasks etc.

Touch-Interfaces
Touch interfaces are graphical user interfaces using a touchscreen display as a combined input and output device. Used in many types of industrial processes and machines, self- service machines etc.

Tips and Techniques for UID
The following tips and techniques are commonly using in User Interface Designing.

Consistency: The most important thing you can possibly do is ensure your user interface works consistently. If you can double-click on items in one list and have something happen, then you should be able to double-click on items in any other list and have the same sort of thing happen. Put your buttons in consistent places on all your windows, use the same wording in labels and messages, and use a consistent color scheme throughout.

Set standards and stick to them: The only way you can ensure consistency within your application is to set user interface design standards, and then stick to them.

Use color appropriately: Color should be used sparingly in your applications and, if you do use ii, you must also use a secondary indicator. The problem is that some of your users may be color blind and if you are using color to highlight something on a screen, then you need to do something else to make it stand out if you want these people to notice it. You also want to use colors in your application consistently, so you have a common look and feel throughout your application.

Expect your users to make mistakes: How many times have you accidentally deleted some text in one of your files or in the file itself? Were you able to recover from these mistakes or were you forced to redo hours, or even days, of work? The reality is that to err is human, so you should design your user interface to recover from mistakes made by your users.

Don't create busy user interfaces. Crowded screens are difficult to understand and, hence, are difficult to use.

Group things effectively: items that are logically connected should be grouped together on the screen to communicate they are connected, whereas items that have nothing to do with each other should be separated. You can use white space between collections of items to group them and/or you can put boxes around them to accomplish the same thing.


UI Design Principles
The structure principle: Your design should organize the user interface purposefully, in meaningful and useful ways based on clear, consistent models that are apparent and recognizable to users, putting related things together and separating unrelated things, differentiating dissimilar things and making similar things resemble one another. The structure principle is concerned with your overall user inter"face architecture.

The simplicity principle: Your design should make simple, common tasks simple to do, communicating clearly and simply in the user's own language, and providing good shortcuts that are meaningfully related to longer procedures.

The visibility principle: Your design should keep all needed options and materials for a given task visible without distracting the user with extraneous or redundant information. Good designs don't overwhelm users with too many alternatives or confuse them with unneeded information.

The feedback principle: Your design should keep users informed of actions or interpretations, changes of state or condition, and errors or exceptions that are relevant and of interest to the user through clear, concise, and unambiguous language familiar to users.

The tolerance principle: Your design should be flexible and tolerant, reducing the cost of mistakes and misuse by allowing undoing and redoing, while also preventing errors wherever possible by tolerating varied inputs and sequences and by interpreting all reasonable actions reasonable.

The reuse principle: Your design should reuse internal and external components and behaviors, maintaining consistency with purpose rather than merely arbitrary consistency, thus reducing the need for users to rethink and remember.

Command Line Interfaces
Short for command line interface, a user interface common to MS-DOS computers. The user sees the command line on the monitor and a prompt that is waiting to accept instructions from the user. The user types in the command, the computer acts on that command and then issues a new prompt for the next instruction from the user.

CLI Advantages

• Ubiquitous
• Easy to understand
• Supports long-running processes within the one session
• Third-party NMS products can use the CLI for management plane access
• Session-based
• Audit trail is supported

CLI Disadvantages

• Non-standard
• Proprietary-each vendor has its own CLI
• Not very extensible
• Security is proprietary
• Places a burden on the network
• Session orientation limits the number of users

Graphical User Interfaces
A program interface that takes advantage of the computer's graphics capabilities to make the program easier to use. Well-designed graphical user interfaces can free the user from learning complex command languages.

GUI Advantages

The GUI is much easier to learn than the other interfaces, and it can serve as a starting point for learning the package.

For non-programmers, the GUI is the only interface available. The GUI is also much easier to use than the programmatic inter-faces, since it is easier to point-and-click on buttons than it is to write and debug code'

GUI Disadvantages
One of the major disadvantages of using any GUI is that if it does not have the functionality to do what you want it to do, then you are simply stuck. lf you want to continue to use the GUl. your only option is to prevail upon the developers to put into the GUI what you want (or to write your own GUI if you are talented and ambitious)

Lecture 18 - CASE Tools

CASE has emerged as a much talked about topic in software industries. Software is becoming the most important component in any computer installation. Even though hardware prices keep falling below even the most optimistic expectations, software is becoming costlier due to increased manpower cost involved.

In this scenario CASE tools promise reduction in software development and maintenance costs. CASE tools help to develop better quality products more efficiently.

Traditional vs CASE based Development

CASE-Based Systems Development

• Emphasis on analysis and design
• Rapid interactive Prototyping
• Automated code generation
• Automated documentation generation
• Automated design checking
• Maintain design specifications

Traditional Systems Development

• Emphasis on coding and testing
• Paper-based specifications
• Manual coding of Programs
• Manual documenting
• Intensive software testing
• Maintain code and documentation

Advantages of using CASE tools

A CASE tool is a generic term used to denote any form of automated support for software engineering. In more restrictive sense, a CASE tool can mean any tool used to automate some activity associated with software development.

Many CASE tools are now available. Some of these tools assist in phase-related tasks such as specification, structured analysis, design, coding, testing, etc. and others are related to non-phase activities such as project management and configuration management.

The primary objectives of deploying CASE tool are:

• To increase the productivity
• To produce quality software fast and for a lower cost

Benefits of CASE Tools

A key benefit arising out of the use of a CASE environment is cost saving through all development phases. Different studies carried out to measure the impact of CASE put effort reduction to between 30% and 40%.

Use of CASE tools leads to considerable improvements to quality. This is mainly due to the facts one can easily iterate through different phases of software development and chances of human errors are very low.

CASE tools help produce high quality and consistent documents. since the important data relating to software product are maintained in central repository, redundancy in the stored data is reduced and therefore chances of inconsistent documentation are reduced to a great extent.

CASE tools reduce the redundancy of software engineers work. For example, they need to check laboriously the balancing of the Data Flow Diagrams but can do it effortlessly through the press of a button.

CASE tools have led to revolutionary cost saving on software maintenance efforts. This has been possible not only due to the tremendous value of a CASE environment trace-ability and consistency checks, but also due to the systematic information capture during the various phases of software development as a result of adhering to a CASE environment.

Use of a CASE environment has an impact on the style of working of a company, and makes it conscious of structured and orderly approach.

Components of CASE

Upper CASE
CASE tools designed to support the information planning and the project identification and selection, process initiation and planning, analysis and design phases of the systems development life cycle

Lower CASE
CASE tools designed to support the implementation and maintenance phases of the systems development life cycle. This includes the tools used for coding, testing, reverse engineering and maintenance tools.

Cross Life-Cycle CASE
CASE tools designed to support activities that occurs across multiple phases of the systems development life cycle. Most CASE tools utilize a repository to store all diagrams, forms, models and report definitions.

CASE support in software life cycle

Let us examine the various types of support that CASE provides during the different phases of a software life cycle. CASE tools should support a development methodology, help enforce the same, and provide certain amount of consistency checking between different phases.

The kind of support that CASE tools usually provide in the software development life cycle is elucidated below.

Prototyping Support
There are several stand-alone prototyping tools. But a tool that integrates with the data dictionary can make use of the entries in the data dictionary, help in populating the data dictionary and ensure the consistency between design data and the prototype.

One prototyping CASE tool is GUI (Graphical User Interface) design. CASE tool should support user to create GUI using a GUI itself (GUI Editor such as Dreamweaver / Visual Studio).

It should integrate with the data dictionary of the CASE environment. lf possible, it should be able to integrate with the external user-defined modules written in C language or in some popular high level programming languages.

The user should be able to define the sequence states through which a created prototype can run. The user should also be allowed to control the running of the prototype.

The run-time system of the prototype should support mock up run of the actual system and management of the input and output data

Structured Analysis and Design
A CASE tool should support one or more of the structured analysis and design techniques. It should support effortlessly, making analysis and design diagrams. lt should also support making fairly complex diagrams and preferably through hierarchy of levels.

Code Generation
As far as code generation is concerned, the general expectation from a CASE tool is quite low. A reasonable requirement is trace ability from source file to design data. Most case tools for code generation is capable of generating code templates rather than actual logic itself.

Test CASE Generator
It should support both design and requirement testing. Generating test cases manually is a very time consuming process and therefore this type tool is helpful for generating test cases based on source code or based on a formal specification.

It should generate test set reports in ASCII format which can be directly imported in to the test plan document.

Reverse and Re-Engineering Tools

Reverse Engineering Tools
Automated tools that read program source code as input and create graphical and textual representations of program design level information.
 

Re-engineering Tools
Automated software that reads program source code, analyzes it and automatically or interactively alters an existing system to improve quality.

Other characteristics of CASE tools:

• Hardware and environmental requirements
• Documentation support
• Project management
• Reverse engineering support
• Data dictionary interface
• Tutorial and help

Lecture 17 - File Organization

There are several ways of organizing records in a file.

• Serial file organization
• Sequential file organization
• Indexed serial file organization
• Indexed sequential file organization
• Random i hash i direct file organization

Serial file and Sequential file
A serial file will consist of records in a order which the records are entered. Therefore if a new record needs to be inserted it will be done to the end of a file

Example:

 

When considering sequential files storage of records is done either in ascending or descending order. Therefore when inserting a record it will first of all identify the exact location for storage.

Example:

 

After record 37 was inserted

When we need to search for a group of records which are in order the best form of file organization is a sequential file.

If records need to be updated quickly the best form of file organization is a serial file.


Indexed Serial Files
An index serial file will consist several indexed layers. This will depend on the complexity of the serial file. Zero indexed layer of this file organization is same as a sequential file.

Inserting Records

When inserting value '35' from the second indexed layer identify which indexed page has the relevant set of records. (Indexed page 'J')

From first indexed layer identify which index page has the relevant values (g). From the zero indexed layer identify where value '35' should be stored. Thereafter re-arrange the indexed layers appropriately.

Searching for Records

Searching for record '29'

From the second indexed layer identify on which page record'29' exists. (Page i)

From the first indexed layer identify on which page the record exists (Page C)

Finally from the data file read the records one by one from the relevant page until you find the necessary record.


Indexed Sequential File
The final data file in this method of file organization is a sequential file. Therefore we need not have an additional indexed layer to sequence the records. (As in index serial file organization), therefore accessing an index sequential file is faster compared with accessing an indexed serial file.

Inserting Records

When inverting records to an index sequential file we cannot attach the particular record to the end of the file as in an index serial file organization.

The exact location to store the record should be identified by following the indexed layers.

Based on the insertion the index layers may have to be updated.

As in sequential files the index sequential file provides to access a group of records which is in order comparatively faster than the serial file.


Hash / Random and Direct Files

Hash files uses hashing algorithms for example mod 3 in order to generate a bucket number to add new record. Based on generated bucket address the record will be stored in particular area. When the bucket area is full additional records will be sent to the particular overflow area.

Lecture 16 - Documentation

What is Documentation?

The printed or online documents that explain things: identify the parts of your hardware or software, give installation instructions, and give directions for use. In programming this includes explanations of the code

"What the logic is, why it is written that way, what the code is doing"

Documentation is needed for the following purposes.

• As a mode of communication
• To support the project management activities
• System maintenance

When documenting information a standard format should be adopted, they should provide simple, comprehensive & unambiguous set of information.

Attributes of Good documentation

1. During the various stages of a project development such as Systems analysis, Systems design etc the need arises to pass on information. Sometimes this is done verbally, but this is short term & subject to loss or misses interpretation.
2. Documents are better, but need to confirm to rules to avoid ambiguity, duplication, omission & contradiction.
3. Good standards provide a framework & are not meant to reject rules. Often they are provided in the form of checklists.
4. Standards need to govern the way the documents are prepared & maintained.
5. Good documentation requires time and effort and an application of who the audience will be for such documentation because that will dictate the style & tone of the work.
6. However do not create unnecessary documentation, be selective and consider if the output is really needed.

The primary outputs of good documentation are:

• Complete and up to date
• Well structured
• Indexed
• Presented in a standard form

Types of Documentation

• User Documentation
• System Documentation
• Program Documentation

User Documentation
This will describe the functions of the system without referring to how they are implemented. The user documentation will mainly consist of users requests. This will include the following.

• State the problems - Definition of the organization, the actual problem will be stated.
• Assess the feasibility - This is the description of the proposed approach to the project which states the objectives
• Plan the schedule for lmplementation - This will be a time table for the development work. lt will also state an approximate completion date of the project.

System Documentation
The system documentation describes the system functions and how they are implemented. Most system documentation is prepared during the system analysis and system design phases.

System documentation consist of;

• Data dictionaries
• Data flow diagrams
• Object models
• Screen layouts
• Source documents
• Initial System requests

Program Documentation
The program documentation will consists of more detail description of the modules and continues during the system implementation It begins in the system analysis phase and continues during system implementation includes process descriptions and report layouts.

Programmers provide documentation with comments to make it easier to understand and maintain the program. An analyst must verify that program documentation is accurate and complete.

The documentation required to enable a programmer to maintain a program over its life may be divided in to two:

1. Internal Documentation
2. External Documentation

Internal Documentation
This covers the aspects of programs which are embodied in the syntax of the programming. These includes:

• Meaningful names used to describe data items and procedures.
• Comments relating to the function of the program as a whole and of the modules comprising the program
• Clarity of the style and format - one instruction per line, indention or related groups of instruction, blank lines separating modules.
• Use of symbolic names instead of constants or literals in the procedural code.
• Develop the program as set of modules

External Documentation
The category covers the supporting documentation which should be maintained in a manual accompanying every program. It is essential that as changes are made to a program, it's external Documentation rs updated at the same time. Out-of-date documentation can be misleading to a maintenance programmer and result in much time being wasted.

External Documentation should includes;

• A current of the source program - the program as written by the programmer, including any memory maps, cross references, and so on, that are able to be obtained from the compilation process.
• The program specification - the document defining the purpose and mode of operation of the program
• An explanation of any formulae or complex calculations in the program
• A specification of the data being processed - data accepted from of displayed on a screen, items in reports, external files processed, including the format of record structures and fields within those records. All data being describe in terms of its size, format, type and structure.
• Program Specification
• Analysis Information
• Program Design
• Design Checking Methods
• Program Code
• Test data and test outputs
• Testing methods
• Review Documents
• Detail description of the program
• Any special details required for programing such as formulas and calculations
• Hardware and software requirements
• User interface and their structures

Lecture 15 - Software Testing (Part II)

Testing Techniques

Black Box Testing

Black box testing can be referred to as:

• Functional Testing
• Opaque Testing
• Closed Box Testing

Black Box Test design is usually described as focusing on testing functional requirements. Knowing the specified function that the product has been designed to perform , test can be conducted to demonstrate that each function is fully operational at the same time searching for errors in that function.

Since the system is black box its behavior can only be determined by studying its inputs and the related outputs.

The outcome of black box testing will be compared with the expected outcome which was generated by using the systems specification.



White Box Testing

White box testing can be referred as;

• Structural Testing
• Glass Box Testing
• Clear Box Testing

White box test design allows one to peak inside the function and it focuses specifically on using internal knowledge of the software, to guide the selection of test data. Knowing the internal working of a product, test can be conducted to ensure that the internal operations perform according to the specification.


White box testing confirms the following:

• All independent paths written in a module have been exercised at least once.
• Check all logical operations for their true false options Exercise internal data structures to ensure their validating.
• Exercise all the loops within their boundaries.

Static Verification
The process whereby programmers read the program before they are tested by running the code on computer can be categorized into two sections.

• Desk checking
• Dry Run

Desk Checking
Desk checking is used test the actrons or process of a program and should be carried out with the following guide lines. Desk checking is done by a manager or supervisor of work, who goes through the following items and report error to ihe programmer.

• Variable List
• Subroutines / Functions
• Constants
• Equation of variables

The next test after performing the desk check for the program design is dry running the corresponding code.

Dry Running
Dry running a program segment involves the execution of the segment with the programmer acting as a computer. The success of the technique depends updn the ability to simulate the computer's action wiihout making any assumption at all. The dry run table should have separate columns for the following instructions.

• Each instruction working
• Each variable declaration
• Each data structure such as arrays, linked Iist etc.

This is used to test the logic of the program.

V-Model (Link between design and testing)

Lecture 14 - Software Testing (Part I)

Testing
Objectives & Principles of Testing

Testing is the process of executing a program with the intent of finding an error.

It demonstrates that software functions appear to be working according to specifications and that performance requirements have been met. Testing can be conducted at different levels and ways it basically takes two forms.

1. Verification
This refers to the set of activities that ensure software correctly implement a given function. Verification means "Are we building the product right?" (Is it correct with respect to the software specifications?).

2. Validation
Validation is a set of activities which ensures the software that has been built satisfies customer requirements. "Are we building the right product?" (are the software specifications correct?)

Static vs Dynamic Testing
Before the implemented program is tested on a computer, series .of tests are being performed on various documents manually. such testing is usually called as static verification and include desk checking, dry running and code reviews etc.

Dynamic testing is the process of running a program or part of a program on a computer with view to identify the errors. This includes various stages of testing methods.

Debugging
Debugging is consequence of successful testing and its objective is to remove the defects uncovered by tests. The debugging process works from symptom to cause. Because the cause may hot be directly linked-to the symptom. It may be necessary to enumerate hypotheses explicitly and then design new tests cases to allow confirmation or rejection of the hypothesized cause.

Some among the main difficulties in debugging are:

• The symptom and the cause may lie at locations in the code that are quite remote from one another.
• The symptom may disappear by the removal of another error, but only temporarily
  The symptom may be cause not by an error but by misjudgment
• The symptom may be caused by human error (incorrect test plans, is interpretation of specifications).
• The symptom may be difficult to reproduce (in real-time systems input sequences are indeterminate)

Stages of Dynamic Testing
There are four basic testing stages, progressing from smaller to larger scope. They are typically known as:

• Unit Testing
• Integration Testing
• System Testing
• Acceptance Testing

Unit Testing

Unit Testing focuses verification effort on the smallest unit of software design that is the module.

It is typically the work of the programmer as it requires detail knowledge of the internal program design & code.

Each and every module or unit in the system will be tested in isolation.

The amount of Testing needed will vary in proportion to the size & the complexity of the module been tested.


Integration Testing

Integration testing is a systematic technique for constructing the program while conducting tests to uncover errors associated with linking.

The aim of integrated testing is to identify

1. Data being lost between modules.
2. Sub functions may not produce the derived functions when combined.
3. One module can have an adverse effect on another module.


System Testing

System Testing fully exercises the computer based system. It verifies that all system elements have been integrated & perform the allocated function.

The following are the types of System Testing.

Recovery Testing
A system test that causes the siw in a variety of ways & verifies recovery is properly performed.

Security Testing
Security testing attempts to verify that protection mechanisms built in to system will in fact protect if from improper or illegal penetration.

Stress Testing
Some systems are designed to handle specific work load, so stress testing will be processed to see whether this system can process intended work load.


Acceptance Testing
 
This type of testing process is carried out by the users rather than software developer. They concentrate on validating requirements.

Typically errors or omissions in the System requirements are deleted & performance related problems are also detected.

An Acceptance Test can range from an informal test drive to a planned and systematically executed series of tests. In fact acceptance testing can be conducted over a period of weeks or months.


Software Testing Strategies
 
A software testing strategy provides a road map for the software developer, quality assurance team and the customer. The road map describes its steps to be conducted during testing process.

A testing strategy should incorporate

1. Test Planning
2. Test Case Design

Test Planning
Test Planning is concerned with setting out standards for the testing process which will be carried out in the near future.

• Software engineers - To design & conduct testing
• The technical staff - To get an overall picture of testing

Contents of a Test Plan

• The Testing process - Description of the major phases.
• Requirement Tractability - Users are interested on system meeting its requirements and therefore testing should be planned so that all requirements are individually tested.
• Test items Products to be tested should be specified.
• Testing Schedules & resource allocation
• Test recording procedures- The results of the test must be systematically recorded. lt must be possible to audit the testing process. This will verify the correctness of the testing process.

Test Case Design
Test case is an outline which tests a feature or set of features. It provides developer a systematic approach for testing; therefore it will ensure the completeness of test and provide the highest likelihood for uncovering errors in software. Test cases consist of :

• Test Data
• Expected Results
• Purpose of having the particular test data

Top down Testing

This method tests the higher level modules before testing its detail components.The program is represented as a single abstract component where sub components are represented by stubs. Stubs simulate the functionality of the lower level modules. After the top level components are tested, then the sub components are implemented and tested in the same way. This process continues until the lowest level modules are implemented.

Advantages

• Can detect unnoticed design errors very early, early error detection means that extensive redesign & re implementation may be avoided.
• Allows you to make a working limited system early in the development process which gives a psychological boost to those involved in the system development.
• Working Limited system in the initial stages can demonstrate the feasibility of the system to management.

Disadvantages

• Strict to the Top down testing is impractical, because sometimes it is not possible to simulate some complex components using stubs.
• Test output may be difficult to observe
• It may be difficult to find top level input data that will exercise a lower level module in a particular derived manner.

Bottom up Testing

Bottom up testing is the converse of Top down Testing

It involves testing the modules at the lowest level of the hierarchy and then working up the hierarchy until the final module is tested.

When using bottom up testing, test drives are used. Drivers simulate the functionality of higher level modules.

Advantages 

• Testing low level modules are easier because they produce the output in term user requirements
• Easier to create test cases & observe output. (Easy to deliver small amount of data where as giving for higher level system)

Disadvantages

• A working system is not available until all modules are tested.(No hierarchy)
• Higher level errors may cause change in lower level modules.

Lecture 13 - Data Structures and Algorithms

Array Searching
Here we are looking at algorithms which are used to lookup for a particular value in an array. There are two main techniques considered; binary search and rinear search.

1. Linear Search
Is a very simple technique where the array is looked up for the search item stating from the first element one after the other until the value is found or array end is reached. Can be used on both ordered and un-ordered arrays

Pascal function which performs a Linear search on an integer array. Assuming that array is defined globally.

FUNCTION LinearSearch (ITEM: Integer): Boolean;
VAR
lndex : integer;
Found . Boolean;
BEGIN
Index := 1;
Found := False;

WHILE Found=False AND Index <= TableSize DO
BEGIN
IF ITEM = Table I [index ] THEN
Found :=True
ELSE
Index := Index +1;
END;

LinearSearch := Found;
END;

2. Binary Search
This is a more efficient technique that can be used on a sorted .array. Here the search item is compared with the middle element of the array and if found search ends. If not found the process is continued selecting the upper or lower half of the array. With this chosen half same procedure is continued by selecting it's middle element.

Pascal function which performs a Binary search on an Integer array. Assuming that array is defined globally and sorted in ascending order.

FUNCTION BinarySearch( ITEM : lnteger) : Boolean;
VAR
Low, High, Mid : Integer;
Found : Boolean;

BEGIN
Low := 1;
High := TableSize;
Found := False:

WHILE (Found=Fatse) AND (Low <= High) DO

BEGIN

Mid := ( Low + High )DIV 2;
 
IF ITEM = Table [Mid] THEN
Found := True
ELSE IF ITEM > Table [Mid] THEN
Low := Mid +1
ELSE
High := Mid - 1;
END;

BinarySearch := Found;

END;


Array Sorting

There are number of well defined techniques used for arranging the contents of any array in ascending or descending order..some simple techniques are described in the following section.

1. Selection Sort
If the array has N number of elements there will be N-1 Passes. In each pass the smallest element from the unsorted part of the array is selected and moved at the end of the pass to the head element of the unsorted part. The following diagram illustrates the first pass of the process.

Pascal procedure which performs a Selection sort on an Integer array. Assuming that array is defined globally.


PROCEDURE SelectionSort;
VAR
Index, Small, Current : integer;
Begin
Index := 1;
WHILE Index < TableSize DO
BEGIN
Small := Index;
Current := Index + 1;

WHILE Current <= TableSize DO
BEGIN
IF Table [Current ] < Table [Small ] THEN
Small := Current;
Current := Current + '1;
END;

Swap ( Table[Index], Table[Small] );
Index := Index + 1;
END;
END;


2. Bubble Sort

This sorting technique compares the adjacent elements of the array and interchange them if they are out of order. This process is done until a pass is completed without making any interchanges. Then the array is sorted.

Pascal procedure which performs a Bubble sort on an integer array. Assuming that array is defined globally.

PROCEDURE BubbleSort;
VAR
Right, Left, Target : integer;

BEGIN
Target := TableSize;

WHlLE Target > 1 DO
BEGIN
Left :=1;
Right := 2;

WHILE Right <= Target DO
BEGIN
IF Table [Left] > Table[Right] THEN
SWAP (Table[Left], Table[Right]);
Left := Left + 1;
Right := Right + 1;
END;

Target .= Target -1;
END;
END;


3. Insertion Sort
Insertion sort is a different technique where each item is inserted to the proper place by shifting down the already sorted elements to get space for the new one. This technique is quite useful when adding new items one by one to an already sorted list. The process starts with inserting second element and then third, fourth and so on up to the last.

Pascal procedure which performs an insertion sort on an integer array. Assuming that array is defined globally.

PROCEDURE InsertionSort;
VAR
Next, Prev, Insert_Item : integer;

BEGIN
Next := 2;

WHILE Next <= TableSize DO
BEGIN
Insert_Item := Table [Next];
Prev := Next - 1;

WHILE Prev > 0 AND Insert_Item < Table [Prev] DO
BEGIN
Table[ Prev + 1 ] := Table[ Prev]; { Shifting down elements }
Prev := Prev - 1;
END;

Table [Prev + 1] := Insert_Item;
END;
END;


Linked List

This is a dynamic data structure that can be created by using pointers. Unlike arrays a linked list can grow and compressed according to the requirements as the memory is allocated at run-time using pointers.

First we take a look at pointers and how they are used before we construction of linked list.

What is Pointer ?
It is a variable that can point to another memory location. These pointers can be used create dynamic variables, which are allocated memory at run-time.

Constructing a Linked List with Pointers to Records
To construct linked list we need to have a special record type where one filed is a pointer to another similar record. This allows us to link one node to another forming a chain of nodes. This can be very useful creating data structures such as stack, queue, list, trees and graphs.