DATA STRUCTURES AND ALGORITHMS
Data Structures and Algorithms-course content.
Introduction to data structures and algorithms: definitions and uses of data structures and algorithms, role
of data structures and algorithms programming, choice of data structures and algorithms. Elementary data
structures: list, queue, stack, tree, records, arrays; types of list: linear-linked list, doubly linked list, circular
linked list, circular doubly linked list; types of queue: circular queue; types of trees: AVL tree, red black
trees, b-trees; graphs; array based and pointer-based implementation of data structures, hashing, heap,
linear, binary search algorithms; sorting algorithms; depth-first, breadth, hill-climbing, least-cost search
algorithms using either a structured programming language or an OOP language such as C++, JAVA, C#
1.0 Overview.
- Data representation in a program/ memory deals with the generalization of data in terms of type.
- A data type is a well-defined collection of data with a well-defined set of operations on it.
- Data type of a variable is the set of values that the variable may assume.
- A type is a set, and the elements of the set are called the value of the type. Examples: Type integer
represents the set of all integers; type real represents the set of all real numbers. i.e. in C int, double,
- Variable: - A variable is a named data storage location in your computer’s memory.
- Variable names are used in a program to refer to the data stored memory.
1.1 Definitions
What Are Data Structures and Algorithms?
We begin with a definition for “algorithm:
1.1.1 Algorithm- A finite sequence of steps for accomplishing some computational task. An algorithm must:
Have steps that are simple and definite enough to be done by a computer, and
Terminate after finitely many steps
Notice that an algorithm is a sequence of steps, not a program.
You might use the same algorithm in different programs, or express the same algorithm in different
languages, because an algorithm is an entity that is abstracted from implementation details.
1.1.2 Abstract data type (ADT)-:
Def 1: A set of values (the carrier set), and operations on those values.
Def 2: ADT is defined as a mathematical model with a collection of operations defined on that model.
-Abstract Data Type (ADT)-defines the type of data that can be stored in a structure, and the available
methods to operate on the data.
- Example. In Java, an ADT is modelled as an interface and implemented as a class.
- Classes specify how a given operation on the ADT's data is to be performed.
N.B: A Data Structure is an actual implementation of an ADT i.e. a translation of ADT into statements of a
programming language and consists of the following:
The declarations that define a variable to be of that ADT type.
The operations defined on the ADT (using procedures of the programming language).
1
, Properties of ADT
Generalization
Encapsulation
(NB: Find out what the above two properties mean)
- ADT’s are simplification of primitive data types, e.g int, float, char etc.
- The ADT encapsulates a data type in the sense of the type, such that all operations on that type are localized to
one section of the program. i.e. hide implementation details.
Advantages of encapsulation include:
- Loose coupling between classes - programmer only needs to meet interface specification and not to worry
about the details of a given method's functionality.
Adaptability -code can be changed without adversely affecting program functionality, due to the presence of a
uniform interface.
Modularity - the presence of an organized structure that partitions software systems into functional units.
EXAMPLES OF ADTS:
Boolean-The carrier set of the Boolean ADT is the set {true, false}.The operations on these values are
negation, conjunction, disjunction, conditional, is equal to, and perhaps some others.
Integer-The carrier set of the Integer ADT is the set { . . ., -2, -1, 0, 1, 2, . . }, and the operations on these
values are addition, subtraction, multiplication, division, remainder, is equal to, is less than, is greater than,
and so on.
-Note that although some of these operations yield other Integer values, some yield values from other ADTs
(like true and false), but all have at least one Integer value argument.
String-The carrier set of the String ADT is the set of all finite sequences of characters from some alphabet,
including the empty sequence (the empty string).Operations on string values include concatenation, length
of, substring, index of, and so forth.
Bit String-The carrier set of the Bit String ADT is the set of all finite sequences of bits, including the empty
strings of bits, which we denote λ: {λ, 0, 1, 00, 01, 10, 11, 000, . . .}.Operations on bit strings include
complement (which reverses all the bits), shifts (which rotates a bit string left or right), conjunction and
disjunction (which combine bits at corresponding locations in the strings, and concatenation and truncation.
The thing that makes an abstract data type abstract is that its carrier set and its operations are
mathematical entities, like numbers or geometric objects; all details of implementation on a computer
are ignored. This makes it easier to reason about them and to understand what they are. For example,
we can decide how div and mod should work for negative numbers in the Integer ADT without having to
worry about how to make this work on real computers.
-Then we can deal with implementation of our decisions as a separate problem.
Once an abstract data type is implemented on a computer, we call it a data type.
1.1.3 Data type- An implementation of an abstract data type on a computer. Thus, for example, the Boolean
ADT is implemented as the Boolean type in Java, and the bool type in C++; the Integer ADT is realized
2
, as the int and long types in Java, and the Integer class in Ruby; the String ADT is implemented as the
String class in Java and Ruby.
Abstract data types are very useful for helping us understand the mathematical objects that we use in our
computations, but, of course, we cannot use them directly in our programs. To use ADTs in
programming, we must figure out how to implement them on a computer.
Implementing an ADT requires two things:
Representing the values in the carrier set of the ADT by data stored in computer memory,
and
Realizing computational mechanisms for the operations of the ADT.
Finding ways to represent carrier set values in a computer’s memory requires that we determine how to
arrange data (ultimately bits) in memory locations so that each value of the carrier set has a unique
representation. Such things are data structures.
1.1.4 Data structure- An arrangement of data in memory locations to represent values of the carrier set of an
abstract data type and how to access it. It is the organization for data in main memory. It’s not the same
as File structure which is an organization for data on peripheral device such as a disk drive or tape.
- An example of several common data structures are arrays, records, lists, queues, stacks, binary trees, and
hash tables.
- It is a logical model of a particular organization of data and programs have to follow certain rules to
access and process the structured data
- Realizing computational mechanisms for performing operations of the type really means finding
algorithms that use the data structures for the carrier set to implement the operations of the ADT.
That’s why data structures and algorithms together: to implement an ADT, we must find data structures
to represent the values of its carrier set and algorithms to work with these data structures to implement
its operations.
Representation of data structure
NB: Data structure = Organized data + Allowed operations
- The study of data structures deals with the following:
i. Logical description of the data structure
ii. Implementation of the data structure
iii. Quantitive analysis of the data structure
- There are two categories of data structures:
o Linear Data structures-The elements forms a sequence, i.e. Linear list, Examples of linear a data
structures are arrays, linked lists, stacks and queues.
o Non linear Data structures-The elements do not form a sequence. Examples of non linear data
structures are trees and graphs
Why study data structures and algorithms?
- The use of data structures and algorithms provides ways used by programmers to store and manipulate data.
- Data structures and algorithms assists in developing good software’s that are correct and efficient
Characteristics of good software
3
, Correctness -- a data structure or algorithm is designed, to work as required for all possible inputs.
Example: A sorting algorithm must arrange its inputs in ascending or descending order only.
Efficiency implies fast runtime, and minimal use of computational resources.
Robustness -- a program produces correct outputs for all inputs on any hardware platform on which
the program is implemented.
N.B Robustness includes the concept of scalability -- the capability of a data structure or algorithm to handle
expanding input size without incurring complexity or causing inaccuracy or failure.
Adaptability -- software must be able to be modified or evolved over time to meet environmental
changes (e.g., increased CPU speed, client-server implementation, or new functionality to increase
market demand).
Example: The Year 2000 Problem is an excellent example of poor software design, where date fields in old
software were not designed to be large enough to accommodate date codes for an interval greater than 100
years.
Reusability -- a given piece of code must be able to be used as a component in different systems or in
different application domains without significant modification.
Selecting a Data Structure
1. Analyze the problem to determine the resource constraints.
2. Determine the basic operations that must be supported.
3. Select the data structure that best meets these requirements.
Guiding questions.
• Are all data inserted into the data structure at the beginning, or are insertions Interspersed with other
operations?
• Can data be deleted?
• Are all data processed in some well-defined order, or is random access allowed?
1.1.5 Simple and Structured Data Types
Virtually all programming languages have implementations of several ADTs built into them, thus
providing the set of types provided by the language. There are two sorts of built-in types:
Simple types:-The values of the carrier set are atomic, that is, they cannot be divided into parts.
Common examples of simple types are integers, Booleans, floating point numbers, enumerations,
and characters. Some languages also provide strings as built-in types.
Structured types-: The values of the carrier set are not atomic, consisting instead of several atomic
values arranged in some way. Common examples of structured types are arrays, records, classes, and
sets. Some languages treat strings as structured types.
2.0 Data (Memory) Allocation
2.1 Memory blocks are allocated for program entities during execution phase and randomly done inside the
RAM.
- Memory allocation is of two types:
4
