CH 1

Concept of data type. Basic and user defined data types. Concept of data structure and its uses. Definition and use of ADT. Benefits of using ADTs.
Concept of dynamic memory allocation.
Definition of algorithm. What is a good algorithm? Different structures used in algorithms.
Time and space complexity. Big Oh (O) notation.
Data Type

- Data => represents value or set of values.

- Data Type => classification that specifies what value a variable can hold and
what operation can be performed.
- Programming Languages have own implementation of various data types.
- Ex: C = int, char, float, long, and so on …
Python = String, List, Tuples and so on …
- Types
- Primitive => basic building blocks, stores single value (ex: int, float, boolean, char etc)
- Composite => made by composing primitive or other composite types (ex: struct, array, string
etc)
- Abstract => defined by the behaviour exhibited. (ex: set, stack, queue, graph, tree etc)
Data Types [2]

In C programming, the data types are classified as:

Data Structure
● A data structure is a way of storing data in a computer so that it can be used efficiently and it will allow the most efficient
algorithm to be used.
● It represents the logical or mathematical model of how data are organised in memory.
● A well-designed data structure allows a variety of critical operations to be performed, using as few resources, both execution
time and memory space, as possible.
● Data structure refers to a scheme for organizing data, or in other words it is an arrangement of data in computer's memory in
such a way that it could make the data quickly available to the processor for required calculations.
● A data structure should be seen as a logical concept that must address four fundamental concerns.
○ First, how the data will be stored, and
○ Second, what operations will be performed on it.
○ Third, how are the data associated
○ Fourth, how can they be accessed.
● As data structure is a scheme for data organization so the functional definition of a data structure should be independent of its
implementation.
● The functional definition of a data structure is known as ADT (Abstract Data Type) which is independent of implementation.
● The way in which the data is organized affects the performance of a program for different tasks.
● Computer programmers decide which data structures to use based on the nature of the data and the processes that need to
be performed on that data.
● Some of the more commonly used data structures include lists, arrays, stacks, queues, heaps, trees, and graphs.
Classification of Data Structures

Data structures can be classified as:

Classification of Data Structures [2]
Simple Data Structure

● Simple data structure can be constructed with the help of primitive data structure.
● A primitive data structure used to represent the standard data types of any one of the computer languages.
● Variables, arrays, pointers, structures, unions, etc. are examples of primitive data structures.

Compound Data structure:

● Compound data structure can be constructed with the help of any one of the primitive data structure and it
is having a specific functionality.
● It can be designed by user. It can be classified as
○ Linear data structure
○ Non-linear data structure

Linear Data Structure:

● Linear data structures can be constructed as a continuous arrangement of data elements in the memory.
● It can be constructed by using array data type.
● In the linear Data Structures the relationship of adjacency is maintained between the data elements.
Classification of Data Structures [3]
● The following list of operations applied on linear data structures
1. Add an element
2. Delete an element
3. Traverse
4. Sort the list of elements
5. Search for a data element
For example Stack, Queue, Tables, List, and Linked Lists.
Classification of Data Structures [4]
Non-linear Data Structure:

● Non-linear data structure can be constructed as a collection of randomly distributed set of data item
joined together by using a special pointer (tag).
● In non-linear Data structure the relationship of adjacency is not maintained between the data items.
● The following list of operations applied on non-linear data structures.

1. Add elements

2. Delete elements

3. Display the elements

4. Sort the list of elements

5. Search for a data element

For example Tree, Decision tree, Graph and Forest

Abstract Data Type
● An abstract data type, sometimes abbreviated ADT, is a logical description of how we view the
data and the operations that are allowed without regard to how they will be implemented.
● This means that we are concerned only with what data is representing and not with how it will
eventually be constructed.
● By providing this level of abstraction, we are creating an encapsulation around the data.
● The idea is that by encapsulating the details of the implementation, we are hiding them from the
user’s view. This is called information hiding.
● ADT consists of interface & implementation. Interface defines the logical properties and signature of
the its operations.
● The implementation of an abstract data type, often referred to as a data structure, will require that
we provide a physical view of the data using some collection of programming constructs and
primitive data types.
=> ADT simply defines what is does, and hides how it does?
Abstract Data Type [2]
Array as ADT

• Array is a group of same type of variables that have common name

• Each item in the group is called an element of the array

• Each element is distinguished from another by an index

• All elements are stored contiguously in memory

• The elements of the array can be of any valid type- integers, characters, floating-

point types or user-defined types.

Array as ADT [2]
● 1 D array declaration in C
data_type array_name[size]={element1,element2,..............,element n};
● 2 D array declaration in C
data_type array_name[row_size][column_size];
● Common operations on array:
○ Creating of an array
○ Inserting new element at required position
○ Deletion of any element
○ Modification of any element
○ Traversing of an array
○ Merging of arrays
Array as ADT [3]
● How is array an ADT?
Let A be an array of type T and has n elements then it satisfied the following operations:
• CREATE(A): Create an array A
• INSERT(A,X): Insert an element X into an array A in any location
• DELETE(A,X): Delete an element X from an array A
• MODIFY(A,X,Y): modify element X by Y of an array A
• TRAVELS(A): Access all elements of an array A
• MERGE(A,B): Merging elements of A and B into a third array C
Structure as an ADT
● A structure is a collection of one or more variables, possibly of different types, grouped
together under a single name.
● An array is a data structure in which all the members are of the same data type. Structure is
another data structure in which the individual elements can differ in type.
● T hus, a single structure might contain integer elements, floating-point elements and
character elements.
● The individual structure elements are referred to as members.
A structure is defined as
Declaration of variable:
Structure as an ADT [2]

Accessing members of a structure:

There are two types of operators to access members of a structure. Which are:

• Member operator (dot operator or period operator (.))

• Structure pointer operator (->).

Q>> How is structure an ADT?

Importance of ADT
Dynamic Memory Allocation in C
Dynamic Memory Allocation in C [2]
Dynamic Memory Allocation in C [3]
Dynamic Memory Allocation in C [4]
Dynamic Memory Allocation in C [5]
Algorithm
• Concept and definition
• Design of algorithm
• Characteristic of algorithm
• Big O notation
Algorithm
● An algorithm is a precise specification of a sequence of instructions to be carried out in order
to solve a given problem.
● Each instruction tells what task is to be done.
● There should be a finite number of instructions in an algorithm and each instruction should be
executed in a finite amount of time.
Properties of Algorithms:
1. Input: A number of quantities are provided to an algorithm initially before the algorithm
begins. These quantities are inputs which are processed by the algorithm.
2. Definiteness: Each step must be clear and unambiguous.
3. Effectiveness: Each step must be carried out in finite time.
4. Finiteness: Algorithms must terminate after finite time or step
5. Output: An algorithm must have output.
6. Correctness: Correct set of output values must be produced from the each set of inputs.
Algorithm Analysis

● Analysing an algorithm means determining the amount of resources needed

to execute it.
● An algorithm is said to be effective if it takes less resources (less time to
execute & consumes less memory space).
● The performance of an algorithm can be therefore be measured in terms of:
○ Time Complexity
○ Space Complexity
Algorithm Analysis [2]

● Algorithms are generally designed to work with an arbitrary number of

inputs,so the efficiency or complexity of an algorithm is stated in terms of
time and space complexity.
● The time complexity of an algorithm is basically the running time of a
program as a function of the input size.
● Similarly, the space complexity of an algorithm is the amount of computer
memory that is required during the program execution as a function of the
input size .
Time Complexity
● Time Complexity of an algorithm is the representation of the amount of time required by the
algorithm to execute to completion.
● Time requirements can be denoted or defined as a numerical function t(N), where t(N) can
be measured as the number of steps, provided each step takes constant time.
● For example, in case of addition of two n-bit integers, N steps are taken.

● Consequently, the total computational time is t(N) = c*n, where c is the time consumed for
addition of two bits. Here, we observe that t(N) grows linearly as input size increases.
Time Complexity[2]
Determined in terms of 3 types of time:

1. Worst-case running time: The worst-case running time of an algorithm is an upper bound on the
running time for any input.
Therefore, having the knowledge of worst-case running time gives us an assurance that the algorithm will
never go beyond this time limit.
2. Average-case running time: The average-case running time of an algorithm is an estimate of the running
time for an `average' input.
It specifies the expected behaviour of the algorithm when the input is randomly drawn from a given
distribution. Average-case running time assumes that all inputs of a given size are equally likely.
3. Best-case running time: The term 'best-case performance' is used to analyse an algorithm under optimal
conditions.
For example, the best case for a simple linear search on an array occurs when the desired element is the
first in the list.

=>It is always recommended to improve the average performance and the worst-case performance of an
algorithm.
Space Complexity
● Space complex of an algorithm represents the amount of memory space needed by the algorithm in
its life cycle.
● Space needed by an algorithm is equal to the sum of the following two components:
○ A fixed part that is a space required to store certain data and variables (i.e. simple variables and constants, program
size etc.), that are not dependent of the size of the problem.
○ A variable part is a space required by variables, whose size is totally dependent on the size of the problem. For
example, recursion stack space, dynamic memory allocation etc.
● Space complexity S(p) of any algorithm p is S(p) = A + Sp( I) ,where A is treated as the fixed part
and S(I) is treated as the variable part of the algorithm which depends on instance characteristic I.
● Following is a simple example that tries to explain the concept:

● Here we have three variables P, Q and R and one constant. Hence S( p) = 1+3.
● Now space is dependent on data types of given constant types and variables and it will be multiplied
accordingly.
Asymptotic Notations
● Asymptotic analysis of an algorithm refers to defining the mathematical
bounding /framing of its run-time performance.
● Asymptotic analysis is input bound i.e., if there's no input to the algorithm, it is
concluded to work in a constant time.
● Other than the "input" all other factors are considered constant.
● Asymptotic analysis refers to computing the running time of any operation in
mathematical units of computation.
● The Running time of Algorithm is defined as : the time needed by an algorithm
in order to deliver its output when presented with legal input .
● In Asymptotic notation, algorithm is treated as a function.
● Usually, the time required by an algorithm falls under three types
○ Best Case — Minimum time required for program execution.
○ Average Case — Average time required for program execution.
○ Worst Case — Maximum time required for program execution
Types of Asymptotic Notations

Mostly used 3 types:

Big O notation
DEFINITION : For a given function g(n), we denote by O(g(n)) (pronounced "big-oh of g of n" or
sometimes just "oh of g of n") the set of functions:
0(g(n)) = { f(n) : there exist positive constant c, n such that 0< f(n) < c g(n) for all n >
no}
● For all values of n at and to the right of n0, the value of f(n) lies at or below cg(n).
● So, g(n) is an asymptotically upper bound for f(n).

● Example: Suppose f(n) = 4n2+5n+3. Is f(n) is 0(n2)? .

Omega Notation
Theta Notation
Exercises[2]

1. f(n) = n2+ 100n + log10n + 1,000

2. f(n) = 2n2 + 3n + 1
3.
Exercises

5.
Lab 1
1. Write a program in C to get 2 numbers and display the max and min.
2. Write a program in C to find out the factorial of a user entered number using
iterative method.
3. Perform 2 using recursive function.
4. Write a program in C to get “n” numbers and obtain their sum, average, max and min using
the concept of dynamic memory allocation. (malloc)
5. Implement array as an ADT. Your Array ADT should implement the following functions:
a. Creating of an array
b. Inserting new element at required position
c. Deletion of any element
d. Modification of any element
e. Traversing of an array
f. Merging of arrays