An algorithm is a sequence of clear and precise step-by-step instructions for solving a problem in a

finite amount of time.

Algorithms are implemented by translating the step-by-step instructions into a computer program that
can be executed by a computer. This translation process is called computer programming or simply
programming. Computer programs are constructed using a programming language appropriate to the
problem.

Procedural abstraction is the use of a function or method knowing what it does but ignoring how its
accomplished.

(Example: Consider the mathematical square root function which you have probably used at some
point. You know the function will compute the square root of a given number, but do you know how
the square root is computed)

Data abstraction is the separation of the properties of a data type (its values and operations) from the
implementation of that data type.

Unit 1
Introduction to Data Structure
Definition:
Data Structure is a concept that deals with the way of arranging data on a computer
memory so that the data can be accessed and updated efficiently.

Primitive vs non-primitive data structure(ADT)

Data structure means organizing the data in the memory. The data can be organized
in two ways either linear or non-linear way.

There are two types of data structure:

o Primitive data structure (Primitive Data types)

o Non-primitive data structure (Abstract Data Types-ADT)

➢ Primitive data structure (Primitive Data types)

Primitive data structure contains fundamental data types such as integer, float,
character, pointer, and these fundamental data types can hold a single type of value.
For example, integer variable can hold integer type of value, float variable can hold
floating type of value, character variable can hold character type of value whereas the
pointer variable can hold pointer type of value.

The following are the four primitive data structures:

✓ Integer: The integer data type contains the numeric values. It contains
the whole numbers that can be either negative or positive. When the
 range of integer data type is not large enough then in that case, we can
use long.
✓ Float: The float is a data type that can hold decimal values. When the
precision of decimal value increases then the Double data type is used.
✓ Boolean: It is a data type that can hold either a True or a False value. It
is mainly used for checking the condition.
✓ Character: It is a data type that can hold a single character value both
uppercase and lowercase such as 'A' or 'a'.

➢ Non-primitive data structure (Abstract Data Types (ADT))

✓ An Abstract Data Type (or ADT) is a programmer-defined data type that
specifies a set of data values and a collection of well-defined operations that can
be performed on those values. A container is any data structure or abstract data
type that stores and organizes a collection.
✓ ADT is further divided into two types: Simple ADT and Complex ADT

➢ Simple ADT is composed of a single or several individually named data fields

such as those used to represent a date or rational number.

Example: Date ADT, Bag ADT, Sets and Maps

➢ Complex ADT is a kind of data structure that is composed of a collection of

data values stored either in a contiguous or random location. It is categorized
into two parts such as linear data structure and non-linear data structure.

✓ Linear data structure is a sequential type of data structure, in which

data elements are arranged sequentially or linearly, where each element
is attached to its previous and next adjacent elements.

Example: Array, Linked list, Stack, Queue

✓ Non-linear data structure is a kind of random type of data structure.

Example: Tree and Graph.

The differences between the primitive and non-primitive data structure.

Primitive data structure Non-primitive data structure (ADT)

Examples of primitive data structure are Examples of non-primitive data structure

integer, character, float. are Array, Linked list, stack.
 Primitive data structure will contain some Non-primitive data structure can consist of
value, i.e., it cannot be NULL. a NULL value.

The size depends on the type of the data In case of non-primitive data structure, size
structure. is not fixed.

It starts with a lowercase character. It starts with an uppercase character.

Primitive data structure can be used to call Non-primitive data structure cannot be used
the methods. to call the methods.

Traversals are very common operations, especially on containers. A traversal iterates over the entire
collection, providing access to each individual element. Traversals can be used for a number of
operations, including searching for a specific item or printing an entire collection.

An iterator is an object that provides a mechanism for performing generic traversals through a
container.

Simple ADTs
1. The Date Abstract Data Type
Define Date ADT

A date represents a single day in the proleptic Gregorian calendar.

Operations:

➢ Create:
Date(month, day, year): Creates a new Date instance initialized to the given Gregorian date
which must be valid. Year 1 BC and earlier are indicate by negative year components.
➢ Search:
day(): Returns the Gregorian day number of this date.
month(): Returns the Gregorian month number of this date.
year(): Returns the Gregorian year of this date.
monthName(): Returns the Gregorian month name of this date.
dayOfWeek(): Returns the day of the week as a number between 0 and 6 with 0 representing
Monday and 6 representing Sunday.
➢ Length:
numDays(otherDate): Returns the number of days as a positive integer between this date and
the otherDate.
➢ Test:
 isLeapYear(): Determines if this date falls in a leap year and returns the appropriate boolean
value.
➢ Increment/decrement:
advanceBy(days): Advances the date by the given number of days. The date is incremented if
days is positive and decremented if days is negative.
➢ Compare:
comparable(otherDate): Compares this date to the otherDate to determine their logical
ordering. This comparison can be done using any of the logical operators <, <=, >, >=, ==, !=.
➢ Convert:
toString(): Returns a string representing the Gregorian date in the format mm/dd/yyyy.
Implemented as the Python operator that is automatically called via the str() constructor.

2. Bag ADT
Define Bag ADT

A bag is a container that stores a collection in which duplicate values are allowed. The items, each of
which is individually stored, have no particular order but they must be comparable.

Operations:

➢ Create:
Bag(): Creates a bag that is initially empty.
➢ Search:
contains(item): Determines if the given target item is stored in the bag and returns the
appropriate boolean value. Accessed using the in operator.
➢ Insert:
add(item): Adds the given item to the bag.
➢ Delete:
remove(item): Removes and returns an occurrence of item from the bag. An exception is
raised if the element is not in the bag.
➢ Traverse:
iterator(): Creates and returns an iterator that can be used to iterate over the collection of
items.
➢ Length:
length(): Returns the number of items stored in the bag. Accessed using the len() function.

3. Define Set ADT

A set is a container that stores a collection of unique values over a given comparable domain in which
the stored values have no particular ordering.
 Logical representation of SETS Physical representation of SETS

Operations:

➢ Create:
Set(): Creates a new set initialized to the empty set.
➢ Search:
contains(element): Determines if the given value is an element of the set and returns the
appropriate boolean value. Accessed using the in operator.
➢ Insert:
add(element): Modifies the set by adding the given value or element to the set if the element
is not already a member. If the element is not unique, no action is taken and the operation is
skipped.
➢ Delete:
remove(element): Removes the given value from the set if the value is contained in the set
and raises an exception otherwise.
➢ Traverse:
iterator(): Creates and returns an iterator that can be used to iterate over the collection of
items
➢ Length:
length(): Returns the number of elements in the set, also known as the cardinality. Accessed
using the len() function.
➢ Compare:
equals(setB): Determines if the set is equal to another set and returns a boolean value. For
two sets, A and B, to be equal, both A and B must contain the same number of elements and
all elements in A must also be elements in B. If both sets are empty, the sets are equal. Access
with == or !=.
➢ Test:
isSubsetOf(setB): Determines if the set is a subset of another set and returns a boolean value.
For set A to be a subset of B, all elements in A must also be elements in B.
➢ Union:
union(setB): Creates and returns a new set that is the union of this set and setB. The new set
created from the union of two sets, A and B, contains all elements in A plus those elements in
B that are not in A. Neither set A nor set B is modified by this operation.
➢ Intersection:
intersect(setB): Creates and returns a new set that is the intersection of this set and setB. The
intersection of sets A and B contains only those elements that are in both A and B. Neither set
A nor set B is modi ed by this operation.
➢ Difference:
 difference(setB): Creates and returns a new set that is the difference of this set and setB. The
set difference, A B, contains only those elements that are in A but not in B. Neither set A nor
set B is modifed by this operation.

4. Map ADT
Define Map ADT

A map is a container for storing a collection of data records in which each record is associated with a
unique key. The key components must be comparable.

Operations:

➢ Create:
Map(): Creates a new empty map.
➢ Search:
✓ contains(key): Determines if the given key is in the map and returns True if the key is
found and False otherwise.
✓ valueof(key): Returns the data record associated with the given key. The key must exist
in the map or an exception is raised.
➢ Insert:
add(key, value): Adds a new key/value pair to the map if the key is not already in the map or
replaces the data associated with the key if the key is in the map. Returns True if this is a new
key and False if the data associated with the existing key is replaced.
➢ Delete:
remove(key): Removes the key/value pair for the given key if it is in the map and raises an
exception otherwise.
✓ Traverse:
iterator(): Creates and returns an iterator that can be used to iterate over the keys in the map.
➢ Length:
length(): Returns the number of key/value pairs in the map.