Data Structure and Algorithm

Data Type

1. Defines a certain domain of values
2. Defines Operations allowed on those values
   • Example: Allowed Operations on floating point values are addition, subtraction, multiplication, division, etc. Bitwise and % operations are not allowed.

Include:

• Primitive data types - integers, char, etc..
• user defined data types - Structure, union and enumeration.

Abstract Data Types

They are simillar to user defined data types which defines operations on values using functions without specifying what is there inside the function and how the operations are performed (ABSTRACTION).

Example Stack - Consists of elements of same type arranged in a sequential order

Operations:

• initialize()
• Push()
• Pop()
• isEmpty()
• isFull()

NOTE: There are multiple ways to implement an Abstract Data Type (ADT)
Example: A stack ADT can be implemented using arays or linked lists.

Why use adt?
The program with uses data structure is called a client program.
The client has access to the ADT, i.e. interfece.
The program which implements the data structure is known as the implementation.

• The user can use the Operations without knowing its implementation
• The client program will work the same without being affected when an implementation is changed.

---

Data structures is the programmatic/system way of storing/organizing data so that data can be used efficiently. Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output.
A data structure is used to implement an Abstract Data Type

ADT tells us what ***(BLUEPRINT)***is to be done and data structures tells us how (IMPLEMENTATION) to do it.
Different implementations of ADT are compared for time and space efficiency. The one best suited according to the current requirement wof the user will be selected.

Advantages of Data Structure

• Efficiency - Proper choice of data strcutures make program efficient in terms of space and time
• Reusability - One implementation can be used by multiple client programs
• Abstraction - Data structure is specified by an ADT which provides a level of abstraction. The client program doesn't have to worry about the implementation details.

Types of Data Structure

• Linear Data Structures - All elements are arranged in a linear (sequential) order

• Non-Linear Data Structures All elements are not arranged in a linear (sequantial) order. There is no linear arrangements of the elements. Example: Tree, Graph

• Static Data Structures Memory is allocated at compile time. Maximum size is fixed. Example: Array
  Advantages: Fast access.
  Disadvantages: Slower insertion and deletion.

• Dynamic Data Strcuture Memory is allocated at run time. Maximum size is flexible. Example: Linked List
  Advantages: Faster insertion and deletion Disadvantages: Slower access

Asymptotic Analysis.

Efficiency of data structures is always measures in terms of TIME and SPACE

We compare the time complexity of the data structure on the basis of operations performed on them.
Example: Inserting an element at the beginning of the list is way faster in the linked list than arrays.

NOTE

• Measuring the actual running time is not practical at all
• The running time generally depends on the size of the input
  Therefore, if the size of the input is n, then f(n) is a funciton of n denotes the time complexity. In other words, f(n) represents the number of instructions for the input value n.
  We can compare two data structures for a particular operation by comparing their f(n) values. We are interested in growth rate of f(n) with respect to n because it might be possible that for smaller input size, one data strcuture may seem better than the other but for larger input size it may not.
  This concept is application in caomparing the two algorithms as well.

Example

f(n) = 5n² + 6n + 12

n	5n2	6n	12
1	21.74%	26.09%	52.17%
10	87.41%	10.49%	2.09%
100	98.79%	1.19%	0.02%
1000	99.88%	0.12%	0.0002%

It is a clear observation that for larger values of n, the squared term consumes almost 99% of the time, so there is no harm if we can eliminate the rest of the terms as they are not contributing much of the time.
Hence:

f(n) = 5n²

We are getting the approximate time complexity and we are satisfies with the results because this approximate result is very near to the actual result.
This approximate measure of time complexity is called Asymptotic Complexity

Big O notation

Big O notation is used to measure the performance of any algorithm by providing the order of growth of the function.
It gives the upper bound of a function by which we can make sure that the function will never grow faster than this upper bound.
We want the approximate runtime, not the exact runtime, of the operations performed on data structures.

If f(n) and g(n) are the 2 functions,then

f(n) = O(g(n))

if and only if, there exists constants c and n_o such that

f(n) <= c.g(n)

for all n >= n_o

This simply means that f(n) does not grow faster than g(n)

Example 1

---

$$f(n) = n g(n) = 2n$$

Is f(n) = O(g(n)) ?
f(n) <= c.g(n)
Take

c = 1 and n_o = 1

then

n <= c.2n

---

Example 2

---

$$f(n) = 4n + 3 g(n) = n$$

Is f(n) = O(g(n)) ?
f(n) <= c.g(n)

4n+3 <= c.n

Take

c = 5

then

$$4n+3 <= 5n 3 <= 5n - 4n n >= 3$$

Therefore; f(n) <= c.g(n) for all n >= 3 where c = 5 and n_o = 3

---

n	f(n)	g(n)
1	7	5
2	11	10
3	15	15
4	19	20
5	23	25
6	27	30
7	31	35
8	35	40
9	39	45

Big O notation helps us in finding the growth rate of the function without plugging in different values of n
It gives the least upper bound on the function which gives the surety that the function under consideration will never grow faster than this upper bound. The least upper bound tells how worst an algorithm can perform.
Big O notation simplifies tasks. It elminates all the unnecessary terms from the function which are not contribting much in the overall running time.

Growth Rate of Standard Functions

n				g(n)
n	log2n	n	nlog2n	n2	n3	2n
1	0	1	0	1	1	2
2	1	2	2	4	8	4
4	2	4	8	16	64	16
8	3	8	24	64	512	256
16	4	16	64	256	4096	65536
32	5	32	160	1024	32768	429*107

Guidelines to Asymptotic Analysis

Loops	O(n)
Nested Loops	O(n2)
Consecutive Statements	O(n2)
if-then-else statement	O(n)
Logarithm Complexity (eg. log28 = 3)	O(log2n)

NOTE: Logarithmic time complexity is achieved when the problem size is cut down by a fraction.

(k-1=log₂n) = (k=log₂n + 1)

Problem 1 Finding the time complexity of:

void fun(int n)
{
    int i, j, k, count = 0;
    
    for (i = n/2; i <= n; i++)
        for (j = 1; j+n/2 < n; j++>)
            for (k = 1; k <= n; k = k*2)
                count++
}

line 1: O(1)
line 2: (k - 1 = n - n/2) => (k - 1 = (2n - n)/2) => (k = n/2 + 1) => O(n)
line 3: (j <= n - n/2 = n/2) => (j = k = n/2) => (k = n/2) => O(n)
line 4: (k = 2^p-1 = n) => (n = 2^p-1) => (p - 1 = log₂n) => (p = log₂ n + 1) => O(logn)

Solution

n * n * logn = O(n²logn)

---

Categories of algorithm

• Search
• Sort
• Insert
• Update
• Delete

Following computer problems can be solved using Data Structures

• Fibonaccui number series
• Knapsack problem
• Tower of Hanoi
• All pair shortest path by Floyd-Warshall
• Shortest path by Dijkstra
• Project scheduling

Foundation terms of a data structure

• Interface: A set of operations that a data structure supports.
  • Provider the list of supported operations
  • Type of parameters they can accept
  • Return type of these operations
• Implementation:
  • Provides the internal representation of a data structure
  • Provides the definition of the algorithms used in the oprerations of the data structure.

Characteristics of a data structure

• Correctness: Implementation
• Time complexity: Execution time
  • Worse Case
  • Avergae case
  • Best case
• Space complexity: Memory usage

Basic Terminology

• Data: Values or set of values
• Data Item: Single unit of values
• Group Items: Data items that are divided into sub items
• Elementary Items: Data items that cannot be divided
• Attribute and entity: That which contains certain properties, which may be assigned values.
• Entity Set: Entities of similar properties
• Field: A single elementary unit of information representing an attribute of an entity.
• Record: A collection of field values of a given entity.
• File: A collection of records of the entities in a given entity.

Data Definition

This defines a particular data with the following characteristics.

• Atomic - Definition should define a single concept.
• Traceable - Definitions should be able to be mapped to some dta element.
• Accurate - Definition should be unambiguos.
• Clear and Concise - Definition shpuld be understandable.

Data Object

This represents an object having a data

Data Type

This is a way to classify various types of data such as interger string, etc. which determines the values that can be used with the corresponding type of data, and the type of operations that can be performed on the corresponding type of data.

• Built-in Data Type

  These are data types for which a language has built-in support for.

  • Intergers
  • Boolean
  • Floating (Decimal numbers)
  • Character and Strings

• Derived Data Type

  Those data types which are implementation independent as they can be implemented in one or the other way.
  These data types are normally built by the combination of primary or built-in data types and associated operations on them

  • List
  • Array
  • Stack
  • Queue

Basic Operations

The data in the data structures are processed by certain operations. The particular data structure chosen largely depends on the frequency of the operation that needs to be performed on the data structure.

• Traversing
• Searching
• Insertion
• Deletion
• Sorting
• Merging

---

Data Structures and Types

Data types represent the nature of the data while data structures are just a collection of similar or different data types in one.

There are usually just two types of data structures

• Linear Data Structures
• Non-Linear Data Structures

Linear Data Structures

The data is stored in linear data structures sequentially. These are rudimentary structures since the elements are stored one after the other without applying any mathematical operations.

Linear data structures are usually easy to implement but since the memory allocation might become complicated, time and space complexities increase.

Examples Include:

• Arrays
• Linked Lists
• Stacks
• Queues

Sub-types

• Static Linear Data Structures
  In Static Linear Data Structures, the memory allocation is not scalable.
  • Example includes an array

• Dynamic Linear Data Structures
  In Dynamic linear data structures, the memory allocation can be done dynamically when required.
  • Examples include: linked lists, stacks and queues.

Non-Linear Data Structures

Non-Linear data structures store the data in the form of a hierarchy.
The data can be found in multiple levels and are difficult to traverse through.

Few types of non-linear data structures are

• Graphs
• Trees
• Tries
• Maps

---

Arrays

Array is a type of linear data structure that is defined as a collection of elements with same or different data types.
They exist in both single dimension and multiple dimensions.

• Element − Each item stored in an array is called an element.
• Index − Each location of an element in an array has a numerical index, which is used to identify the element.

Syntax

data_type array_name[array_size] = {elements separated using commas}
or,
data_type array_name[array_size];

Need for Arrays

Arrays are used as solutions to many problems from the small sorting problems to more complex problems like travelling salesperson problem.

Arrays provide O(1) random access lookup time. That means, accessing the 1st index of the array and the 1000th index of the array will both take the same time. This is due to the fact that array comes with a pointer and an offset value. The pointer points to the right location of the memory and the offset value shows how far to look in the said memory.

  array_name[index]
     |         |
  Pointer    Offset

Array Representation

Arrays are represented as a collection of buckets where each bucket stores one element. These buckets are indexed from ‘0’ to ‘n-1’, where n is the size of that particular array.

This indexing will be similar for the multidimensional arrays as well.

Basic Operations in the Arrays

These operations are usually performed to either modify the data in the array or to report the status of the array.

• Traverse − print all the array elements one by one.
• Insertion − Adds an element at the given index.
• Deletion − Deletes an element at the given index.
• Search − Searches an element using the given index or by the value.
• Update − Updates an element at the given index.
• Display − Displays the contents of the array.

Linked List

A linked list is a collection of “nodes” connected together via links. These nodes consist of the data to be stored and a pointer to the address of the next node within the linked list. Any amount of data can be stored in it and can be deleted from it.

Types of Linked Lists

• Singly Link List - The nodes only point to the address of the next node in the list
• Doubly Linked List - The nodes point to the addresses of both previous and next nodes
• Circular Linked List - The last node in the list will point to the first node on the list. It can either be singly linked or double linked.

Singly Linked List

Singly linked lists contain two “buckets” in one node; one bucket holds the data and the other bucket holds the address of the next node of the list. Traversals can be done in one direction only as there is only a single link between two nodes of the same list.

Doubly Linked Lists

Doubly Linked Lists contain three “buckets” in one node; one bucket holds the data and the other buckets hold the addresses of the previous and next nodes in the list. The list is traversed twice as the nodes in the list are connected to each other from both sides.

Circular Linked Lists

Circular linked lists can exist in both singly linked list and doubly linked list.
Since the last node and the first node of the circular linked list are connected, the traversal in this linked list will go on forever until it is broken.

Basic Operations in the Linked Lists

• Insertion − Adds an element at the beginning of the list.
• Deletion − Deletes an element at the beginning of the list.
• Display − Displays the complete list.
• Search − Searches an element using the given key.
• Delete − Deletes an element using the given key.