Data Structures PRELIM

Data Types

all programming language has a set of built-in ____ ____

Abstract Data Types

• specification of a set of data and set of operations performed in a data

• storage for data defined in terms of set of operations to be performed on the data

Algorithms

finite set of instructions that specify a sequence of operations to be carried out

• recipe for solving a problem

• Example of simple algorithm

  - Apply to wet hair

  - Massage gently

  - Leave on for a few moments

  - Rinse Off

Criteria for Algorithm

• Input - zero or more quantities are externally supplied

• Output - at least one quantity is produced

• Definiteness - each instruction must be clear and unambiguous

• Finiteness - all instructions of an algorithm will terminate after a finite number of steps

• Effectiveness - each operation must be definite, but must also be feasible

Input

zero or more quantities are externally supplied

Output

at least one quantity is produced

Definiteness

each instruction must be clear and unambiguous

Finiteness

all instructions of an algorithm will terminate after a finite

Effectiveness

each operation must be definite, but must also be feasible

Raw data

is an input to a computer and an algorithm is used to transform this into a refined data

PSEUDOCODE

• textual presentation of a flowchart

• close to a natural language

• the control structures impose the logic

• may become part of the program documentation

• could be translated into a program

STEPWISE REFINEMENT

• The process by which a programmer refines an initial idea to a problem's solution into more specific terms.

• The last phase of refinement results in a program ready to be coded for execution

Analysis of Algorithms

determining the amount of resources necessary to execute it

such as time and storage

usually in terms of CPU time and memory requirements

Best-case analysis

• Worst-case analysis

• Average-case analysis

Data structure

is a special format for storing and organizing data.

Two (2) types of data structure:

• Linear: Elements are accessed in a sequential order but may be stored

unsystematically.

• Non-Linear: Elements are stored and accessed in a non-sequential order.

Linear

Elements are accessed in a sequential order but may be stored

unsystematically.

Non-Linear

Elements are stored and accessed in a non-sequential order.

Abstract Data Type

is a logical description of how data is viewed as well

as the operations that are allowed without regard to how they will be

implemented.

Benefits of using ADT:

• Code is easier to understand. o Implementations of ADTs can be changed without requiring changes to the program that uses the ADTs.

• ADTs can be used in future programs.

Public or external

the data and the operations

Private or internal

the representation and the implementation

Linked list

is used for storing elements where each is a separate object.

Stack

is an ordered list in which insertion and deletion are done at one (1) end.

Queue

is an ordered list in which insertion and deletion are done at separate

ends.

Tree

represents a hierarchical nature of a structure in a graphical form.

Priority queue

is used for retrieving and removing either the minimum or

maximum element

Heap

is a partially sorted binary tree.

Set

represents a collection of elements that do not have to be in order.

Map

is a set of ordered pairs with elements known as key and value.

Graph

consists of a set of points/nodes (vertices) and set of links (edges) which

connects the pairs of vertices.

initializing, adding, accessing, and removing of data.

The four (4) main operations that could be defined for each ADT are _____

Algorithm

is a step-by-step set of instructions to be

executed in sequence for solving a problem.

Characteristics of an algorithm:

• Finiteness: An algorithm must terminate after a specified number of steps.

• Definiteness: Each instruction has to be clear and unambiguous.

• Input: An algorithm should have zero or more well- defined data given before

the algorithm begins.

• Output: An algorithm must have one (1) or more results, with specified relation

to the input.

• Uniqueness: The result of each step depends on the input and/or the result of the previous step.

Finiteness

An algorithm must terminate after a specified number of steps.

Definiteness

Each instruction has to be clear and unambiguous.

Uniqueness

The result of each step depends on the input and/or the result of

Elements of an algorithm:

Sequential operations

Actions based on the state of a data structure.

• Iteration – repeating an action multiple times.

• Recursion – when a function calls itself once or

  multiple times to solve a problem.

Sequential operations

Actions based on the state of a data structure.

Iteration

repeating an action multiple times.

Recursion

when a function calls itself once or

multiple times to solve a problem.

Algorithm design paradigms:

• Divide and Conquer – breaking a problem into smaller

subproblems.

• Greedy Algorithms – always chooses the optimal approach

in solving a problem.

• Dynamic Programming – similar to divide and conquer

except that the results of the subproblems are reused for

overlapping subproblems

Divide and Conquer

breaking a problem into smaller

subproblems.

Greedy Algorithms

always chooses the optimal approach

in solving a problem.

Dynamic Programming

similar to divide and conquer

except that the results of the subproblems are reused for

overlapping subproblems

Arrays

ordered collection of data items of the same type referred to collectively by a single name

Index

each variable or cell in an array

Elements

individual data / items in an array indicated by the array name followed by its dimensions appears in a square brackets

Dimensions

an integer from 1 – n called dimensioned variables

Operations in Arrays

• Insert

• Search

• Delete

Insert

• Adds item to the indicated place/cell

• The process is very fast because it only includes one step

• Every data inserted is placed in the first vacant cell

Search

• Another process that the algorithm carries out

• The red arrow from the figure states where the search starts

• Moves methodically downwards to search for the item

Delete

• The algorithm must first locate the item to delete it

• The deleted item causes hole in the array

Basics of Arrays in Java

Arrays are treated as primitive type, they are treated as objects

use the new operator to declare an array

int arrayLength //find array length

intArray.length;

intArray name is a reference to an array and not the array itself

The length field of an array can be used to find the size in bytes:

int[] intArray; // declares a reference to an array

intArray = new int[100]; // initialize the array, and sets // intArray to refer to it

the size of an array, when created, can no longer be modified

One-dimensional Array

Array1[j]

Two-dimensional Array

Array1[i][j]

Multi-dimensional Array

Array[i][j][k]…

One-Dimensional Array

• It is the basic array

• A vertical table with number of columns and only one row

An array of ints

int[] intArray;

An array of Random objects

Random[] randomArray;

Arrays are fixed-length structure

Indices

• used to access each location of arrays from 0 ranging up to the instantiated array

• An array of length 10, instantiated as

Two-Dimensional Array

• It is an array of an array

• Also called as tables or matrices

• Row – first dimension

• Column – second dimension

Row

first dimension

Column

second dimension

Matrix

is a mathematical object which arises in many physical problems

Magic Square

is an n x n matrix of the integers 1 to n2

Transpose

another operation that can be performed on matrices that computes for the transpose of matrix