Chapter 1: Introduction to Data Structures and Algorihtm

Data

It is the information processed by computers.

Structure, Unstructured

It is the two types of data.

Structured Data

It follows a fixed and organized format.

Unstructured Data

It follows an unfixed, scattered format.

Data Structure and Algorithm

Provide a set of techniques to the programmer for handling the data efficiently.

Data Structure and Algorithm

Allow programmers to write code in any programming language with minimal effort.

Pre-defined Algorithmic Techniques

If a programmer does not know these techniques, it may take a longer time to resolve the problem.

Data Structure

Study of various ways of organizing data in a computer.

Data Structure

Programmatic way of storing data so that data can be used efficiently.

Data Structure

A systematic way to organize data in order to use it efficiently.

Data Structure

Method of storing data to be used efficiently.

Structure, Algorithms

Adding _______ to data can make ________ much simple, easier to maintain, and often makes algorithm faster.

Program

are comprised of two things: data and algorithms.

Data

information processed or stored by a computer.

Algorithm

Describes the way the data is to be transformed.

Interface

Represents the set of operations that a data structure supports.

Interface

Provides the list of supported operations.

Interface

Specifies the type of parameters operations can accept.

Interface

Specifies the return type of operations.

Interface

It is considered the front-end section of a data structure.

Implementation

Provides the internal representation of a data structure.

Implementation

Provides the definition of the algorithms used in the operations of the data structure.

Implementation

It pertains to the underlying process that makes the interface work.

Characteristics of a Data Structure

These are the traits needed in order to cater to the demands expected from a data structure. In short, these traits are what makes up a GOOD data structure.

Characteristics of a Data Structure

• Correctness

• Time Complexity

• Space Complexity

Correctness

Data structure implementation should implement its interface correctly.

Time Complexity Efficient

Running time or execution time of operations of data structure must be as small as possible.

Space Complexity Efficient

Memory usage of a data structure operation should be as little as possible.

Needs of a Data Structure

These are the reasons why data structured is needed.

Needs of a Data structure

• Data Search

• Processor Speed

• Multiple Requests

Data Search

Searching 1 million items every time slows down the search process. As data grows, search will become slower. A good data structure will be able to help efficiently search for the needed data.

Processor Speed

_______________ although being very high, falls limited if the data grows to billion records. A good data structure will help maintain the processor speed at stable.

Multiple Requests

Thousands of users can search data simultaneously on a web server, even the fast server fails while searching the data.

Execution Time Cases

These pertains to the case scenarios that give the measurement of resources: time and space used.

Worse, Average, Best

This is the types of Execution Time Cases.

Worst Case

Scenario where a data structure operation takes maximum time.

Average Case

Scenario depicting the average execution time of a data structure operation.

Best Case

Scenario depicting the least possible execution time of a data structure operation.

Algorithm

A step-by-step procedure defining a set of instructions to be executed in a certain order to get the desired output.

Algorithm

Created independent of underlying programming languages.

Algorithm

Can be implemented in more than one programming language.

Algorithm

It performs the “implementation” part or what these data is supposed to do.

Categories of Algorithm

• Search

• Sort

• Insert

• Update

• Delete

Search, Sort, Insert, Update, Delete

These are the categories of algorithms.

Search Algorithm

Algorithm to search an item in a data structure.

Sort Algorithm

Algorithm to sort items in a certain order.

Insert Algorithm

Algorithm to insert an item in a data structure.

Update Algorithm

Algorithm to update an existing item in a data structure.

Delete Algorithm

Algorithm to delete an existing item from a data structure.

Characteristics of an Algorithm

• Unambiguous

• Input

• Output

• Finiteness/Feasibility

• Independent

Unambiguous, Input, Output, Finiteness/Feasibility, Independent

These are the characteristics of an algorithm. UIOFFI

Unambiguous

Algorithm steps and inputs/outputs must be clear and lead to only one meaning.

Input

Algorithm should have zero or more well-defined inputs.

Output

Algorithm should have one or more well-defined outputs matching the desired output.

Finiteness

Algorithm must terminate after a finite number of steps.

Feasibility

Algorithm should be feasible with available resources.

Independent

Algorithm steps should be independent of any programming code.

Algorithm Writing Standard

There are no well-defined standards for writing algorithms.

Algorithm Writing

Problem and resource dependent.

Algorithm

They are never written to support a particular programming code.

Algorithm Writing

It is a process executed after the problem domain is well-defined.

Problem Domain

Must be known before designing a solution or writing an algorithm.

Algorithm Examples

• Taxi Algorithm

• Call Me Algorithm

• Rent A Car Algorithm

• Bus Algorithm

Taxi Algorithm

Go to taxi stand, get in a taxi, give the driver my address.

Call-Me Algorithm

Call when plane arrives and meet outside baggage claim.

Rent-a-Car Algorithm

Take shuttle, rent a car, follow directions home.

Bus Algorithm

Catch bus 70, transfer to bus 14, get off on Elmo Street, walk to house.

Algorithm Analysis

It pertains to the method used to analyze the efficient of an algorithm: before and after implementation.

• A Priori Analysis

• A Posterior Analysis

Two Types of Algorithm Analysis.

A Priori Analysis

It is a theoretical analysis of an algorithm.

A Priori Analysis

The efficiency of an algorithm is measured by assuming that all other factors, for example, processor speed, are constant and have no effect on the implementation.

A Posterior Analysis

Empirical analysis using actual implementation and execution.

A Posterior Analysis

Collects actual running time and space statistics. This is then executed on target computer machine.

A Posterior Analysis

The selected algorithm is implemented using programming language.

Algorithm Complexity

Determined by time and space used by algorithm X.

algorithm, input data

Suppose X is an _______ and n is the size of ________, the time and space used by the algorithm X are the two main factors, which decide the efficiency of X.

Efficiency

The time and space used by the algorithm X are the two main factors, which decide the ________ of X.

Time Factor

It is measured by counting key operations such as comparisons in the sorting algorithm.

Space Factor

Measured by counting maximum memory space required by the algorithm.

Complexity of an Algorithms

Gives running time and/or storage space required by the algorithm in terms of input size n.

Space Complexity

Amount of memory space required by an algorithm during its life cycle.

Space

The _____ required by an algorithm is equal to the sum of the following two components: fixed and variable part.

Fixed Part

It is a space required to store certain data and variables, that are independent of the size of the problem.

Fixed Part

For example, simple variables and constants used, program size, etc.

Variable Part

It is a space required by variables, whose size depends on the size of the problem.

Variable Part

Example of this are Dynamic memory allocation and recursion stack space.

Time Complexity

Amount of time required by an algorithm to run to completion.

Time Complexity

Its requirements can be defined as a numerical function T(n), where T(n) can be measured as the number of steps, provided each step consumes constant time.