INTRODUCTION TO DATA STRUCTURES AND ALGORITHMS

Data structures

A fixed-length, ordered collection of values of the same type stored in contiguous memory locations.

elements

The collection may be ordered in several dimensions. It consists of a collection of

array index or key.

each identified by at least one (1)

(matrix)

An array can be considered as the simplest type of data structure and can be either a one dimensional array or a two-dimensional array

List

An abstract data type that represents a sequence of values, where the same value may occur more than once.

instance

of a list is a computer representation of the mathematical concept of a finite sequence

stream

infinite analog of a list is a

Linked List

Consists of chains of nodes where each node contains information such as data and a pointer to the next node in the chain.

reference (a link)

Each node is composed of data and a ___ to the next node in the sequence; more complex variants add additional links.

Stack

A kind of abstract data type or collection in which the principal operations on the collection are the addition of an entity to the collection (push) and the removal of an entity (pop).

Last-In-First-Out (LIFO)

data structure that the last element added to the structure must be the first one to be removed.

top of the stack

The push and pop operations occur only at one end of the structure, referred to as the ___

peek

top operation can also be implemented, returning the value of the top element without removing it.

Queue

A kind of abstract data type or collection in which the entities in the collection are kept in order, and the principal operations on the collection are the addition of entities to the rear terminal position and the removal of entities from the front terminal position.

First-In-First-Out (FIFO)

data structure where the first element added to the queue will be the first one to be removed.

Hashing

A method for storing and retrieving records from a database. It allows one to insert, delete, and search for records based on a search key value.

hash table

A hash system stores records in an array called a ___

hash function

The calculations are done by a function called

Trees

A data structure made up of nodes or vertices and edges without having any cycles.

null or empty tree

A tree with no nodes is called the

root node

A tree that is not empty consists of a ___ and potentially many levels of additional nodes that form a hierarchy.

starting at a root node

A tree data structure can be defined recursively as a collection of nodes

children

where each node is a data structure consisting of a value, together with a list of references to nodes

Abstract Array

• Adding elements

• Sorting elements

• Searching elements

• Re-arranging the elements

• Performing matrix operations

• Pre-fix and post-fix operations

Abstract List

• Inserting

• Searching

• Deletion

Abstract Link

• Checking whether the list is empty

• Accessing a node to modify it or to obtain the information in it

• Traversing the list to access all elements, such as to print them or to find a specific element

• Determining the size (i.e., the number of elements) of the list

• Inserting or removing a specific element

• Creating a list by reading the elements from an input stream

• Converting a list to and from an array, string, etc.

Abstract Stack

• Push, which inserts some data item into the structure

• Pop, which extracts an item from it

• Peek or top, which allows data on top of the structure to be examined without removal.

Abstract Queue

• Enqueue, to join the queue

• Dequeue, to remove the first element from the queue

• Front, to access and serve the first element in the queue

Abstract Hashing

• Add (Insert)

• Delete (Removing)

Abstract Tree

• Searching

• Insertion

• Deletion

• Traversal

• Sort

algorithm

a finite sequence of steps for accomplishing a computational task.

input

An algorithm can be considered as a computational procedure that consists of a set of instructions that takes some value or set of values as

output

produces some value or set of values as

• Each step of an algorithm must be exact.
• Algorithms must terminate.
• It must be effective.
• It must be general.
• It must be unique.
• Finiteness.
• Output.

Characteristics of an Algorithm:

Each step of an algorithm must be exact.

An algorithm must be precise and unambiguously described. This eliminates any uncertainty.

Algorithms must terminate.

Since the ultimate aim of an algorithm is to solve a problem, it must terminate; otherwise, there will not be a solution to the problem. This leads to the fact that an algorithm must have a finite number of steps in its execution. The presence of endless loops must be avoided.

It must be effective.

An algorithm must provide the correct answers at all times.

It must be general.

An algorithm must solve every instance of a problem.

It must be unique.

Results of each step are uniquely defined and only depend on the input and the result of the preceding steps.

Finiteness.

The algorithm stops after a finite number of instructions are executed.

Output.

The algorithm always produces output.

Human Language

Expressing algorithms means describing a sequence of steps or instructions using plain, natural language instead of formal programming code or mathematical notation. This method is typically used to make the logic of an algorithm understandable to people without requiring technical syntax or specific tools.

Pseudocode

An informal high-level description of the operating principle of a computer program or other algorithm. It is a procedure for solving a problem based on the actions to be executed and the order in which those actions are to be executed.

Flowchart

A type of diagram that represents an algorithm, workflow, or process. It shows the steps in the form of boxes of various kinds and their order by connecting them with arrows.