Data Structures and Algorithms Fundamentals

Today's Agenda Introduction to data Structures Linear data structures Nonlinear data structures Applications Real time applications Algorithms Analysis (Complexities) Summary

What is Programming ? Programming is the process of creating a set of instructions that tell a computer how to perform a task. Programming can be done using a variety of computer programming languages, such as Python, JAVA C++, etc.

What is Data Structures ? In computer science, a data structure is a data organization, management, and storage format that enables efficient access and modification. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

• Data Structure is a way of collecting and organising data in such a way that we can perform operations on these data in an effective way. • Data Structures is about rendering data elements in terms of some relationship, for better organization and storage.

EXAMPLE we have some data which has, player's name "Virat" and age 26. Here "Virat" is of String data type and 26 is of integer data type. We can organize this data as a record like Player record, which will have both player's name and age in it. Now we can collect and store player's records in a file or database as a data structure. For example: "Dhoni" 30, "Gambhir" 31, "Sehwag" 33

Linear Data Structure Data structure where data elements are arranged sequentially or linearly where the elements are attached to its previous and next adjacent in what is called a linear data structure. In linear data structure, single level is involved. Therefore, we can traverse all the elements in single run only. Linear data structures are easy to implement because computer memory is arranged in a linear way.

Linear Data structure Array Stack Queue Linked List

Array • Array consisting of a collection of elements (values or variables), each identified by at least one array index or key. • They are also used to implement many other data structures, such as lists and strings.

Basic Operations in 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.

Types of Arrays There are two types of Array One Dimensional Array Multidimensional Array

One Dimensional Array • One dimensional (1-D) arrays or Linear arrays • In it each element is represented by a single subscript. • The elements are stored in consecutive memory locations.

Multidimensional Array • Multidimensional arrays (a) Two dimensional (2-D) arrays or Matrix Arrays • In it each element is represented by two subscripts.

Applications • Implement mathematical vectors and matrices. • Implement other data structures, such as lists, hash tables, deques, queues and stacks.

Linked list • In linked list, the elements are not stored at contiguous memory locations. • The elements in a linked list are linked using pointers

Structure of Linked list • List can be represented by Nodes. • Each nodes contains Head and Tail.

Types of Linked list Single linked list Doubly linked list Circular Linked list

Double Linked list • Contains an extra memory to store the address of the previous node, together with the address of the next node. • we are storing the address of the next as well as the previous nodes.

Circular Linked list • It is either a singly or doubly linked list in which there are no NULL values. • we can implement the Circular Linked List by making the use of Singly or Doubly Linked List. • In the case of a singly linked list, the next of the last node contains the address of the first node • In case of a doubly-linked list, the next of last node contains the address of the first node and previous of the first node contains the address of the last node.

Operations on list Traversal Insertion Searching Updating Sorting

Applications • Implementation of stacks and queues • Performing arithmetic operations on long integers • Manipulation of polynomials by storing constants in the node of linked list

Real Time Applications • Train - here each coach is connected to its previous and next coach (Except first and last). • Image viewer – Previous and next images are linked, hence can be accessed by next and previous button. • Previous and next page in web browser – We can access previous and next URL searched in web browser by pressing back and next button since, they are linked as linked list. • Music Player – Songs in music player are linked to previous and next song. you can play songs either from starting or ending of the list.

Stack • Stack is a linear data structure which follows a particular order in which the operations are performed. • The order may be LIFO(Last In First Out)

Operations on Stack Push • Adds an item in the stack using Push() function. • If the stack is full, then it is said to be an Overflow condition.

POP • Removes an item from the stack by using Pop() function. • The items are popped in the reversed order in which they are pushed. • If the stack is empty, then it is said to be an Underflow condition.

Applications Towers of Hanoi problem. Balancing of symbols. Infix to postfix conversions. Histogram problems. N –Queen problem. Sudoku problem.

Queue • A Queue follows a particular order in which the operations are performed. • The order is First In First Out (FIFO). • The difference between Stacks and queues is in removing. • In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.

Operations on Queue There are two types of operations namely, Enqueue Dequeue

Enqueue Enqueue is a function in a queue which adds a new element in the queue.

Dequeue Dequeue is opposite of enqueue. It returns and removes a node from the front of a queue.

Types of Queue There are four types of Queue data stucture Simple Queue Circular Queue Double Ended Queue Priority Queue

Circular Queue • Unlike the simple queues, in a circular queue each node is connected to the next node in sequence • the last node’s pointer is also connected to the first node’s address.

Double Ended Queue • The doubly ended queue or dequeue allows the insert and delete • Operations from both ends (front and rear) of the queue.

Priority Queue • Priority queue makes data retrieval possible only through a pre- determined priority number assigned to the data items. • While the deletion is performed in accordance to priority number (the data item with highest priority is removed first), insertion is performed only in the order.

Applications of Queue To implement printer spooler so that jobs can be printed in the order of their arrival Round robin scheduling technique is implemented using queue All types of customer service(like railway reservation) centers are designed using the concept of queues.

Real Time Applications Queue • Queue of people at any service point such as ticketing etc. 1 Queue • Queue of processes in OS. 2 Queue • Queue of packets in data communication. 3 Queue • Queue of air planes waiting for landing instructions. 4

Non Linear Data Structures The data structure where data items are not organized sequentially is called nonlinear data structure. All the data elements in nonlinear data structure cannot be traversed in single run.

Types of Non Linear Data Structures Graphs Trees

Graphs A graph is a pictorial representation of a set of objects where some pairs of objects are connected by links. A graph data structure is a collection of nodes that have data and are connected to other nodes. Formally, a graph is a pair of sets (V, E), where V is the set of vertices and E is the set of edges, connecting the pairs of vertices.

Example On face book, everything is a node. That includes User, Photo, Album, Event, Group, Page, Comment, Story, Video, Link, Note...anything that has data is a node. Every relationship is an edge from one node to another. Whether you post a photo, join a group, like a page etc., a new edge is created for that relationship.

Example Contd... All of face book is then, a collection of these nodes and edges. This is because face book uses a graph data structure to store its data.

Structure of graph Graph is a data structure (V,E) that consists of • A collection of vertices V • A collection of edges E, represented as ordered pairs of vertices (u,v) In this graph, V= {0, 1, 2, 3} E = {(0,1), (0,2), (0,3), (1,2)} G = {V, E}

Graph Terminology • Adjacency: A vertex is said to be adjacent to another vertex if there is an edge connecting them. Vertices 2 and 3 are not adjacent because there is no edge between them. • Path: A sequence of edges that allows you to go from vertex A to vertex B is called a path. 0-1, 1-2 and 0-2 are paths from vertex 0 to vertex 2. • Directed Graph: A graph in which an edge (U,V) doesn't necessary mean that there is an edge (V,U) as well. The edges in such a graph are represented by arrows to show the direction of the edge.

Graph Representation Adjacency Matrix Adjacency List

Adjacency Matrix • An adjacency matrix is 2D array of V x V vertices. Each row and column represent a vertex. • If the value of any element a[i][j] is 1, it represents that there is an edge connecting vertex i and vertex j . • Since it is an undirected graph, for edge (0,2), we also need to mark edge (2,0); making the adjacency matrix symmetric about the diagonal. • Edge lookup(checking if an edge exists between vertex A and vertex B) is extremely fast in adjacency matrix representation but we have to reserve space for every possible link between all vertices(V x V), so it requires more space.

Adjacency List • An adjacency list represents a graph as an array of linked list. • The index of the array represents a vertex and each element in its linked list represents the other vertices that form an angle with the vertex. • An adjacency list is efficient in terms of storage because we only need to store the values for the edges. For a graph with millions of vertices, this can mean a lot of saved space..

Operations On graph There are 4 types of operations Check if element is present in graph Graph Traversal Add elements(vertex, edges) to graph Finding path from one vertex to another

Types of Graphs There are 15 types of graphs : 1.Finite graph 8.Pseudo graph 15. Cyclic graph 2.Infinite graph 9.Rectangular graph 3.Trivial graph 10.Bipartite graph 4.Simple graph 11.Weighted graph 5.Multi graph 12.Digraph 6.Null graph 13.Subgraph 7.Complete graph 14.Connected graph

Finite Graph A graph is said to be finite if it has finite number of vertices and finite number of edges.

Infinite graph A graph is said to be infinite if it has infinite number of vertices as well as infinite number of edges.

Trivial Graph A graph is said to be trivial if a finite graph contains only one vertex and no edge.

Simple Graph A simple graph is a graph which does not contains more than one edge between the pair of vertices. A simple railway tracks connecting different cities is an example of simple graph.

Multi Graph • Any graph which contain some parallel edges but doesn’t contain any self-loop is called multi graph. For example A Road Map. • Parallel Edges: If two vertices are connected with more than one edge than such edges are called parallel edges that is many roots but one destination. • Loop: An edge of a graph which join a vertex to itself is called loop or a self-loop.

Null Graph A graph of order n and size zero that is a graph which contain n number of vertices but do not contain any edge.

Complete Graph • A simple graph with n vertices is called a complete graph. • if the degree of each vertex is n-1, that is, one vertex is attach with n-1 edges. • A complete graph is also called Full Graph.

Pseudo Graph A graph G with a self loop and some multiple edges is called pseudo graph.

Rectangular Graph A simple graph is said to be regular if all vertices of a graph G are of equal degree. All complete graphs are regular but vice versa is not possible.

Bipartite Graph • A graph G = (V, E) is said to be bipartite graph if its vertex set V(G) can be partitioned into two non-empty disjoint subsets. • V1(G) and V2(G) in such a way that each edge e of E(G) has its one end in V1(G) and other end in V2(G). • The partition V1 U V2 = V is called Bipartite of G. Here in the figure: V1(G)={V5, V4, V3} V2(G)={V1, V2}

Weighted Graph If the vertices and edges of a graph are labelled with name, data or weight then it is called labelled graph. It is also called Weighted Graph.

Digraph A graph G = (V, E) with a mapping f such that every edge maps onto some ordered pair of vertices (Vi, Vj) is called Digraph. It is also called Directed Graph. Ordered pair (Vi, Vj) means an edge between Vi and Vj with an arrow directed from Vi to Vj. Here in the figure: e1 = (V1, V2) e2 = (V2, V3) e4 = (V2, V4)

Subgraph A graph G = (V1, E1) is called subgraph of a graph G(V, E) if V1(G) is a subset of V(G) and E1(G) is a subset of E(G) such that each edge of G1 has same end vertices as in G.

Connected Graph • A graph G is said to be connected if for any pair of vertices (Vi, Vj) of a graph G are reachable from one another. • Or a graph is said to be connected if there exist at least one path between each and every pair of vertices in graph G, otherwise it is disconnected. • A null graph with n vertices is disconnected graph consisting of n components. Each component consist of one vertex and no edge.

Cyclic graph A graph G consisting of n vertices and n> = 3 that is V1, V2, V3- – – – – – – – Vn and edges (V1, V2), (V2, V3), (V3, V4)- – – – – – – – — -(Vn, V1) are called cyclic graph.

Applications of Graphs Computer Science: In computer science, graph is used to represent networks of communication, data organization, computational devices etc. Physics and Chemistry: Graph theory is also used to study molecules in chemistry and physics. Social Science: Graph theory is also widely used in sociology. Mathematics: In this, graphs are useful in geometry and certain parts of topology such as knot theory. Biology: Graph theory is useful in biology and conservation efforts.

Real Time Applications Social graphs (Face book graph API) Knowledge graphs (Google's Knowledge graphs) Recommendation Engines (Local graph API) Path optimization Algorithms ( Google Maps, Flight Network, GPS Navigation systems)

Trees A tree is a nonlinear hierarchical data structure that consists of nodes connected by edges.

Why Tree Data Structure ? • Other data structures such as arrays, linked list, stack, and queue are linear data structures that store data sequentially. In order to perform any operation in a linear data structure, the time complexity increases with the increase in the data size. But, it is not acceptable in today's computational world. • Different tree data structures allow quicker and easier access to the data as it is a non-linear data structure.

Tree Terminology Node • A node is an entity that contains a key or value and pointers to its child nodes. • The last nodes of each path are called leaf nodes or external nodes that do not contain a link/pointer to child nodes. • The node having at least a child node is called an internal node. Edge It is the link between any two nodes.

Cond... Root It is the topmost node of a tree. Height of a Node The height of a node is the number of edges from the node to the deepest leaf (ie. the longest path from the node to a leaf node). Depth of a Node The depth of a node is the number of edges from the root to the node.

Height of a tree The height of a Tree is the height of the root node or the depth of the deepest node.

Types of trees Binary Tree Binary search Tree AVL Tree B Tree

Binary Tree A binary tree is a tree data structure in which each parent node can have at most two children. For example: In the image below, each element has at most two children.

Types of Binary Tree Full Binary Tree A full Binary tree is a special type of binary tree in which every parent node / internal node has either two or no children.

Perfect Binary Tree A perfect binary tree is a type of binary tree in which every internal node has exactly two child nodes and all the leaf nodes are at the same level.

Complete Binary Tree • A complete binary tree is just like a full binary tree, but with two major differences • Every level must be completely filled • All the leaf elements must lean towards the left. • The last leaf element might not have a right sibling i.e. a complete binary tree doesn't have to be a full binary tree.

Degenerate or Pathological Tree A degenerate or pathological tree is the tree having a single child either left or right

Skewed Binary Tree A skewed binary tree is a pathological/degenerate tree in which the tree is either dominated by the left nodes or the right nodes. Thus, there are two types of skewed binary tree: left-skewed binary tree and right-skewed binary tree.

Binary Tree Representation Code : struct node { int data; struct node *left; struct node *right; }; A node of a binary tree is represented by a structure containing a data part and two pointers to other structures of the same type.

Binary Tree Applications • To easy and quick access to data • In router algorithms • To implement the Heap data structures

Binary Search tree Binary search tree is a data structure that quickly allows us to maintain a sorted list of numbers. It is called a binary tree because each tree node has maximum of two children. It is called a search tree because it can be used to search for the presence of a number in O(log(n)) time. The properties that separates a binary search tree from a regular binary tree is All nodes of left subtree are less than root node All nodes of right subtree are more than root node Both subtrees of each node are also BSTs i.e. they have the above two properties

Representation of Binary tree The binary tree on the right isn't a binary search tree because the right subtree of the node "3" contains a value smaller that it.

AVL Tree AVL tree is a self-balancing binary search tree in which each node maintains an extra information called as balance factor whose value is either -1, 0 or +1. AVL tree got its name after its inventor Georgy Adelson-Velssky and Landis.

Balance Factor • Balance factor of a node in an AVL tree is the difference between the height of the left subtree and that of right subtree of that node. • Balance Factor = (Height of Left Subtree - Height of Right Subtree) or (Height of Right Subtree - Height of Left Subtree) • The self balancing property of an AVL tree is maintained by the balance factor. The value of balance factor should always be -1, 0 or +1.

AVL Tree Applications For indexing large records in databases For searching in large databases

B -Tree • B-tree is a special type of self-balancing search tree in which each node can contain more than one key and can have more than two children. It is a generalized form of the binary search tree. • It is also known as a height-balanced m-way tree.

Why B-Tree ? The need for B-tree arose with the rise in the need for lesser time in accessing the physical storage media like a hard disk. The secondary storage devices are slower with a larger capacity. There was a need for such types of data structures that minimize the disk accesses. Other data structures such as a binary search tree, avl tree, red-black tree, etc can store only one key in one node. If you have to store a large number of keys, then the height of such trees becomes very large and the access time increases. However, B-tree can store many keys in a single node and can have multiple child nodes. This decreases the height significantly allowing faster disk accesses.

B-Tree Applications Databases and file systems To store blocks of data (secondary storage media) Multilevel indexing

Refresh.... Types of data structures Real time applications Applications Data Structures concepts

What is an Algorithm ? In CS , programming, and math, an algorithm is a sequence of instructions where the main goal is to solve a specific problem, perform a certain action, or computation. In some way, an algorithm is a very clear specification for processing data, for doing calculations, among many other tasks.

Search Algorithm Searching Algorithms are designed to check for an element or retrieve an element from any data structure where it is stored.

Some Basic Search Algorithms 1. Linear Search 2. Binary Search 3. Jump search 4. Fibonacci search 5. Interpolation Search

1.Linear Search Linear search is used on a collections of items. It relies on the technique of traversing a list from start to end by exploring properties of all the elements that are found on the way. For example, consider an array of integers of size . You should find the value 10

Binary Search Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one.

Jump Search Like Binary Search, Jump Search is a searching algorithm for sorted arrays. The basic idea is to check fewer elements (than linear search) by jumping ahead by fixed steps or skipping some elements in place of searching all elements.

Fibonacci Search • Fibonacci Search is a comparison-based technique that uses Fibonacci numbers to search an element in a sorted array.

Interpolation Search Interpolation search is an algorithm for searching for a key in an array that has been ordered by numerical values assigned to the keys.

Some Basic Sorting Algorithms 1. Insertion Sort 2. Merge Sort 3. Selection Sort 4. Bubble Sort 5. Quick Sort 6. Heap Sort

Insertion Sort Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

Merge Sort Merge sort repeatedly breaks down a list into several sub lists until each sub list consists of a single element and merging those sub lists in a manner that results into a sorted list.

Selection Sort Selection sort is an algorithm that selects the smallest element from an unsorted list in each iteration and places that element at the beginning of the unsorted list.

Bubble Sort Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.

Quick Sort It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. Sub arrays are then sorted recursively.

Heap Sort Heap sort is a comparison based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for the remaining elements.

Analysis of Algorithm • Analysis of the algorithm is the process of analyzing the problem- solving capability of the algorithm in terms of the time and size. • Time and performance are the main concerns of analysis of algorithm.

Complexites of an Algorithm • The complexity of an algorithm computes the amount of time and spaces required by an algorithm for an input of size (n). • The time complexity and the space complexity are the two complexities.

Time Complexity • The time complexity is defined as the process of determining a formula for total time required towards the execution of that algorithm. • This calculation is totally independent of implementation and programming language.

Space Complexity • Space complexity is defining as the process of defining a formula for prediction of how much memory space is required for the successful execution of the algorithm. • The memory space is generally considered as the primary memory.

Refresh.... Searching Sorting Complexities What is Algorithms ?

Data Structures and Algorithms Fundamentals

Data Structures and Algorithms Fundamentals

More Related Content

What's hot

Similar to Data Structures and Algorithms Fundamentals

Recently uploaded

Data Structures and Algorithms Fundamentals