3. Programming Concepts

Foundation Course in Applications: Programming Concepts UNIT – 3: PROGRAMMING CONCEPTS Structure 3.0 Learning Objectives 3.1 Introduction 3.2 Object-oriented Programming 3.3 Data Structures & Algorithms 3.4 Summary 3.5 Glossary 3.6 References 3.0 Learning Objectives After studying this unit, you will be able to: • Explain Major Concepts of Object-Oriented Programming • Apply Data Structure and Algorithm in Programming 3.1Introduction The core idea is thinking in an object-oriented way is a great way to understand the problem you are trying to solve. It allows you to build software that is more maintainable and easily understandable for other people. Data structures and algorithms (DSA) go through solutions to standard problems in detail and give you an insight into how efficient it is to use each one of them. It also teaches you the science of evaluating the efficiency of an algorithm. This enables you to choose the best of various choices. 3.2Object Oriented Programming Object-Oriented Programming is a methodology or paradigm to design a program using classes and objects. It simplifies the software Page 1 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts development and maintenance by providing some concepts defined below ● Object ● Class ● Polymorphism ● Inheritance ● Abstraction ● Encapsulation Object The object is a run-time entity. It is an instance of the class. An object can represent a person, place or any other item. An object can operate on both data members and member functions. Page 2 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts Class Class is a user-defined data type that defines its properties and its functions. Class is the only logical representation of the data. For example, a Human being is a class. The body parts of a human being are its properties, and the actions performed by the body parts are known as functions. The class does not occupy any memory space till the time an object is instantiated. Example 1: class Student { String name; int age; public void getInfo() { System.out.println(\"The name of this Student is \" + this.name); System.out.println(\"The age of this Student is \" + this.age); } } public class OOPS { public static void main(String args[]) { Student s1 = new Student(); s1.name = \"Aman\"; s1.age = 24; s1.getInfo(); Student s2 = new Student(); s2.name = \"Shradha\"; s2.age = 22; s2.getInfo(); } } Page 3 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts Example 2: class Pen { String color; public void printColor() { System.out.println(\"The color of this Pen is \" + this.color); } } public class OOPS { public static void main(String args[]) { Pen p1 = new Pen(); p1.color = blue; Pen p2 = new Pen(); p2.color = black;ṣ Pen p3 = new Pen(); p3.color = red; p1.printColor(); p2.printColor(); p3.printColor(); } } Polymorphism Polymorphism is the ability to present the same interface for differing underlying forms (data types). With polymorphism, each of these classes will have different underlying data. Precisely, Poly means ‘many’ and morphism means ‘forms’. Types of Polymorphism 1. Compile Time Polymorphism (Static) 2. Runtime Polymorphism (Dynamic) Compile Time Polymorphism: Page 4 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts The polymorphism which is implemented at the compile time is known as compile-time polymorphism. Example - Method Overloading Method Overloading: Method overloading is a technique that allows you to have more than one function with the same function name but with different functionality. Method overloading can be possible on the following basis: 1. The return type of the overloaded function. 2. The type of the parameters passed to the function. 3. The number of parameters passed to the function. class Student { String name; int age; public void displayInfo(String name) { System.out.println(name); } public void displayInfo(int age) { System.out.println(age); } public void displayInfo(String name, int age) { System.out.println(name); System.out.println(age); } } Runtime Polymorphism Runtime polymorphism is also known as dynamic polymorphism. Function overriding is an example of runtime polymorphism. Function overriding means when the child class contains the method which is already present in the parent class. Hence, the child class overrides the method of the parent class. In case of function overriding, parent and Page 5 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts child classes both contain the same function with a different definition. The call to the function is determined at runtime is known as runtime polymorphism. class Shape { public void area() { System.out.println(\"Displays Area of Shape\"); } } class Triangle extends Shape { public void area(int h, int b) { System.out.println((1/2)*b*h); } } class Circle extends Shape { public void area(int r) { System.out.println((3.14)*r*r); } } Inheritance Inheritance is a process in which one object acquires all the properties and behaviours of its parent object automatically. In such a way, you can reuse, extend or modify the attributes and behaviours which are defined in other classes. The class which inherits the members of another class is called derived class and the class whose members are inherited is called base class. The derived class is the specialized class for the base class. Types of Inheritance: 1. Single inheritance: When one class inherits another class, it is known as single level inheritance Page 6 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts class Shape { public void area() { System.out.println(\"Displays Area of Shape\"); } } class Triangle extends Shape { public void area(int h, int b) { System.out.println((1/2)*b*h); } } 2. Hierarchical inheritance: Hierarchical inheritance is defined as the process of deriving more than one class from a base class. Page 7 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts class Shape { public void area() { System.out.println(\"Displays Area of Shape\"); } } class Triangle extends Shape { public void area(int h, int b) { System.out.println((1/2)*b*h); } } class Circle extends Shape { public void area(int r) { System.out.println((3.14)*r*r); } } 3. Multilevel inheritance: Multilevel inheritance is the process of deriving a class from another derived class. Page 8 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts class Shape { public void area() { System.out.println(\"Displays Area of Shape\"); } } class Triangle extends Shape { public void area(int h, int b) { System.out.println((1/2)*b*h); } } class EquilateralTriangle extends Triangle { int side; } 4. Multiple inheritance: Multiple Inheritance is one of the inheritances where one class extends more than one class. Page 9 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts 5. Hybrid inheritance: Hybrid inheritance is a combination of simple, multiple inheritance and hierarchical inheritance. Page 10 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts Encapsulation Encapsulation is the process of combining data and functions into a single unit called class. In Encapsulation, the data is not accessed directly; it is accessed through the functions present inside the class. In simpler words, attributes of the class are kept private and public getter and setter methods are provided to manipulate these attributes. Thus, encapsulation makes the concept of data hiding possible. (Data hiding: a language feature to restrict access to members of an object, reducing the negative effect due to dependencies. e.g., \"protected\", \"private\" feature in Java). Abstraction We try to obtain an abstract view, model or structure of a real-life problem, and reduce its unnecessary details. With definition of properties of problems, including the data which are affected and the operations which are identified, the model abstracted from problems can be a standard solution to this type of problems. It is an efficient way since there are nebulous real-life problems that have similar properties. In simple terms, it is hiding the unnecessary details & Page 11 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts showing only the essential parts/functionalities to the user. Data binding: Data binding is a process of binding the application UI and business logic. Any change made in the business logic will reflect directly to the application UI. Abstraction is achieved in 2 ways: ● Abstract class ● Interfaces (Pure Abstraction) Abstract Class ● An abstract class must be declared with an abstract keyword. ● It can have abstract and non-abstract methods. ● It cannot be instantiated. ● It can have constructors and static methods also. ● It can have final methods which will force the subclass not to change the body of the method. abstract class Animal { abstract void walk(); void breathe() { System.out.println(\"This animal breathes air\"); } Animal() { System.out.println(\"You are about to create an Animal.\"); } } class Horse extends Animal { Page 12 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts Horse() { System.out.println(\"Wow, you have created a Horse!\"); } void walk() { System.out.println(\"Horse walks on 4 legs\"); } } class Chicken extends Animal { Chicken() { System.out.println(\"Wow, you have created a Chicken!\"); } void walk() { System.out.println(\"Chicken walks on 2 legs\"); } } public class OOPS { public static void main(String args[]) { Horse horse = new Horse(); horse.walk(); horse.breathe(); Page 13 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts } } 2. Interfaces ● All the fields in interfaces are public, static and final by default. ● All methods are public & abstract by default. ● A class that implements an interface must implement all the methods declared in the interface. ● Interfaces support the functionality of multiple inheritance. interface Animal { void walk(); } class Horse implements Animal { public void walk() { System.out.println(\"Horse walks on 4 legs\"); } } class Chicken implements Animal { Page 14 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts public void walk() { System.out.println(\"Chicken walks on 2 legs\"); } } public class OOPS { public static void main(String args[]) { Horse horse = new Horse(); horse.walk(); } } 3.3 Data Structures & Algorithms Data structure is a particular way of organizing data in a computer so that it can be used effectively. Data structure and Algorithm (DSA) is applied in all disciplines of software development. DSA is the building block of the software development process. It is not limited to a single programming language. Some Core Concepts are ● Array ● Linked List ● Stack Page 15 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts ● Queue ● Searching Techniques ● Sorting Techniques ● Graph ● Tree ● Recursion ● Advanced Data Structure ● Dynamic Programming Array An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together. This makes it easier to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element of the array (generally denoted by the name of the array). The base value is index 0 and the difference between the two indexes is offset. #include <iostream> using namespace std; int main() { // Creating an integer array named arr of size 10. int arr[10]; Page 16 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts // accessing element at 0 index and setting its value // to 5. arr[0] = 5; // access and print value at 0 index we get the output // as 5. cout << arr[0]; return 0; } Array’s size Array has a fixed size meaning once the size is given to it, it cannot be changed i.e. you can’t shrink it neither can you expand it. The reason was that for expanding if we change the size we can’t be sure (it’s not possible every time) that we get the next memory location to us as free. The shrinking will not work because the array, when declared, gets memory statically allocated, and thus compiler is the only one can destroy it. Types of indexing in an array: ● 0 (zero-based indexing): The first element of the array is indexed by a subscript of 0. ● 1 (one-based indexing): The first element of the array is indexed by the subscript of 1. ● n (n-based indexing): The base index of an array can be freely chosen. Usually, programming languages allowing n-based indexing also allow negative index values, and other scalar data types like enumerations, or characters may be used as an array index. Linked List Linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image: Page 17 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts // A linked list node struct Node { int data; struct Node* next; }; Types of Linked List Singly Linked List A singly linked list is the most common type of linked list. Each node has data and an address field that contains a reference to the next node Doubly Linked List There are two pointer storage blocks in the doubly linked list. The first pointer block in each node stores the address of the previous node. Hence, in the doubly linked inventory, there are three fields that are the previous pointers, that contain a reference to the previous node. Then there is the data, and last you have the next pointer, which points to the next node. Thus, you can go in both directions (backward and forward). Page 18 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts Circular Linked List The circular linked list is extremely similar to the singly linked list. The only difference is that the last node is connected with the first node, forming a circular loop in the circular linked list. Essential Operation on Linked Lists ● Traversing: To traverse all nodes one by one. ● Insertion: To insert new nodes at specific positions. ● Deletion: To delete nodes from specific positions. ● Searching: To search for an element from the linked list. Stack Stack is a linear data structure that follows the principle of Last In First Out (LIFO). This means the last element inserted inside the stack is removed first. Page 19 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts Here, you can: ● Put a new plate on top ● Remove the top plate And, if you want the plate at the bottom, you must first remove all the plates on top. This is exactly how the stack data structure works. LIFO Principle of Stack In programming terms, putting an item on top of the stack is called push and removing an item is called pop. This is exactly how the LIFO (Last In First Out) Principle works. Basic Operations of Stack Page 20 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts ● Push: Add an element to the top of a stack ● Pop: Remove an element from the top of a stack ● IsEmpty: Check if the stack is empty ● IsFull: Check if the stack is full ● Peek: Get the value of the top element without removing it Queue Queue is a useful data structure in programming. It is similar to the ticket queue outside a cinema hall, where the first person entering the queue is the first person who gets the ticket. Queue follows the First In First Out (FIFO) rule - the item that goes in first is the item that comes out first. Basic Operations of Queue ● Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition. ● Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition. Types of Queue Priority Queue Priority Queue is an abstract data type, which is similar to a queue, however, in the priority queue, every element has some priority. Page 21 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts Priority Queue is an extension of the queue with the following properties. • Every item has a priority associated with it. • An element with high priority is dequeued before an element with low priority. • If two elements have the same priority, they are served according to their order in the queue. Priority queue supports the following operations: Insertion: element is inserted in a priority queue, it moves to the empty slot from top to bottom and left to right Deletion: the maximum element is the root node. And it will remove the element which has maximum priority first Page 22 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts Peek: This operation helps to return the maximum element from Max Heap or minimum element from Min Heap without deleting the node from the priority queue. Types of Priority Queue: Ascending Order: Ascending order priority queue, the element with a lower priority value is given a higher priority in the priority list. Descending Order: Remove the element with the highest priority first. As a result, the root node is removed from the queue. Deque Deque or Double Ended Queue is a type of queue in which insertion and removal of elements can either be performed from the front or the rear. Thus, it does not follow FIFO rule (First In First Out). Circular queue circular queue is the extended version of a regular queue where the last element is connected to the first element. Thus forming a circle-like structure. Page 23 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts Searching techniques Searching in data structure refers to the process of finding the required information from a collection of items stored as elements in the computer memory. These sets of items are in different forms, such as an array, linked list, graph, or tree. Another way to define searching in the data structures is by locating the desired element of specific characteristics in a collection of items. Page 24 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts Searching in the data structure can be done by applying searching algorithms to check for or extract an element from any form of stored data structure. These algorithms are classified according to the type of search operation they perform, such as: Sequential search The list or array of elements is traversed sequentially while checking every component of the set. For example – Linear Search. Interval Search The interval search includes algorithms that are explicitly designed for searching in sorted data structures. In terms of efficiency, these algorithms are far better than linear search algorithms. Example- Logarithmic Search, Binary search. Linear Search The linear search algorithm iteratively searches all elements of the array. It has the best execution time of one and the worst execution time of n, where n is the total number of items in the search array. It is the simplest search algorithm in data structure and checks each item in the set of elements until it matches the searched element till the end of data collection. When the given data is unsorted, a linear search algorithm is preferred over other search algorithms. procedure linear_search (list, value) for each item in the list if match item == value return the item's location end if end for Page 25 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts end procedure Binary Search This algorithm locates specific items by comparing the middlemost items in the data collection. When a match is found, it returns the index of the item. When the middle item is greater than the search item, it looks for a central item of the left sub-array. If, on the other hand, the middle item is smaller than the search item, it explores for the middle item in the right sub-array. It keeps looking for an item until it finds it or the size of the sub-arrays reaches zero. Binary search needs sorted order of items of the array. It works faster than a linear search algorithm. The binary search uses the divide and conquers principle. Procedure binary_search A ← sorted array n ← size of array x ← value to be searched Set lowerBound = 1 Set upperBound = n while x not found if upperBound < lowerBound EXIT: x does not exists. set midPoint = lowerBound + ( upperBound - lowerBound ) / 2 if A[midPoint] x set upperBound = midPoint - 1 Page 26 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts if A[midPoint] = x EXIT: x found at location midPoint end while end procedure Interpolation Search It’s a better version of the binary search algorithm that focuses on the probing position of the search element. It only works on sorted data collection, similar to binary search algorithms. A → Array list N → Size of A X → Target Value Procedure Interpolation_Search() Set Lo → 0 Set Mid → -1 Set Hi → N-1 While X does not match if Lo equals to Hi OR A[Lo] equals to A[Hi] EXIT: Failure, Target not found end if Set Mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo]) if A[Mid] = X Page 27 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts EXIT: Success, Target found at Mid else if A[Mid] X Set Hi to Mid-1 end if end if End While End Procedure Hashing Hashing is a technique to convert a range of key values into a range of indexes of an array. We're going to use modulo operator to get a range of key values. Consider an example of hash table of size 20, and the following items are to be stored. Item are in the (key, value) format. Basic Operations Search Operation Whenever an element is to be searched, compute the hash code of the key passed and locate the element using that hash code as index in the array. Use linear probing to get the element ahead if the element is not found at the computed hash code. Insert Operation Page 28 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts Whenever an element is to be inserted, compute the hash code of the key passed and locate the index using that hash code as an index in the array. Use linear probing for empty location, if an element is found at the computed hash code. Delete Operation Whenever an element is to be deleted, compute the hash code of the key passed and locate the index using that hash code as an index in the array. Use linear probing to get the element ahead if an element is not found at the computed hash code. When found, store a dummy item there to keep the performance of the hash table intact. Sorting Algorithm Sorting refers to arranging data in a particular format. Sorting algorithm specifies the way to arrange data in a particular order. most common orders are in numerical or lexicographical order. The importance of sorting lies in the fact that data searching can be optimized to a very high level, if data is stored in a sorted manner. Sorting is also used to represent data in more readable formats. Sorting Techniques are as follows Page 29 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts Bubble sort Bubble sort is a sorting algorithm that compares two adjacent elements and swaps them until they are not in the intended order. just like the movement of air bubbles in the water that rise up to the surface, each element of the array moves to the end in each iteration. Therefore, it is called a bubble sort. Bubble sort algorithm bubbleSort(array) for i <- 1 to indexOfLastUnsortedElement-1 if leftElement > rightElement swap leftElement and rightElement end bubbleSort insertion sort Insertion sort is a sorting algorithm that places an unsorted element at its suitable place in each iteration. Insertion sort works similarly as we sort cards in our hand in a card game. We assume that the first card is already sorted then, we select an unsorted card. If the unsorted card is greater than the card in hand, it is placed on the right otherwise, to the left. In the same way, other unsorted cards are taken and put in their right place. Similar approach is used by insertion sort. Insertion sort algorithm insertionSort(array) mark first element as sorted for each unsorted element X 'extract' the element X for j <- lastSortedIndex down to 0 if current element j > X move sorted element to the right by 1 Page 30 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts break loop and insert X here end insertionSort Selection sort Selection sort is a sorting algorithm that selects the smallest element from an unsorted list in each iteration and places that element at the beginning of the unsorted list. Selection sort algorithm selectionSort(array, size) repeat (size - 1) times set the first unsorted element as the minimum for each of the unsorted elements if element < currentMinimum set element as new minimum swap minimum with first unsorted position end selectionSort Merge Sort Merge Sort is one of the most popular sorting algorithms that is based on the principle of Divide and Conquer Algorithm. Problem is divided into multiple sub-problems. Each sub-problem is solved individually. Finally, sub-problems are combined to form the final solution. Merge sort algorithm Have we reached the end of any of the arrays? No: Compare current elements of both arrays Copy smaller element into sorted array Move pointer of element containing smaller element Yes: Copy all remaining elements of non-empty array Page 31 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts Shell sort Shell sort is a generalized version of the insertion sort algorithm. It first sorts elements that are far apart from each other and successively reduces the interval between the elements to be sorted. The interval between the elements is reduced based on the sequence used Shell sort algorithm shellSort(array, size) for interval i <- size/2n down to 1 for each interval \"i\" in array sort all the elements at interval \"i\" end shellSort Quick sort Quicksort is a sorting algorithm based on the divide and conquer approach where An array is divided into subarrays by selecting a pivot element (element selected from the array). while dividing the array, the pivot element should be positioned in such a way that elements less than pivot are kept on the left side and elements greater than pivot are on the right side of the pivot. The left and right subarrays are also divided using the same approach. this process continues until each subarray contains a single element.at this point, elements are already sorted. Finally, elements are combined to form a sorted array. Quick sort algorithm quickSort(array, leftmostIndex, rightmostIndex) if (leftmostIndex < rightmostIndex) pivotIndex <- partition(array,leftmostIndex, rightmostIndex) quickSort(array, leftmostIndex, pivotIndex - 1) quickSort(array, pivotIndex, rightmostIndex) partition(array, leftmostIndex, rightmostIndex) set rightmostIndex as pivotIndex Page 32 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts storeIndex <- leftmostIndex - 1 for i <- leftmostIndex + 1 to rightmostIndex if element[i] < pivotElement swap element[i] and element[storeIndex] storeIndex++ swap pivotElement and element[storeIndex+1] return storeIndex + 1 Graph Graph is a collection of nodes that have data and are connected to other nodes. Let's try to understand this through an example. On Facebook, 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. Graph Terminology Page 33 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts Vertex − Each node of the graph is represented as a vertex. Edge − Edge represents a path between two vertices or a line between two vertices. Adjacency − Two node or vertices are adjacent if they are connected to each other through an edge. Path − Path represents a sequence of edges between the two vertices. Depth First Search(DFS) Depth first Search or Depth first traversal is a recursive algorithm for searching all the vertices of a graph or tree data structure. Traversal means visiting all the nodes of a graph. Depth First Search Algorithm A standard DFS implementation puts each vertex of the graph into one of two categories: Page 34 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts ● Visited ● Not Visited The purpose of the algorithm is to mark each vertex as visited while avoiding cycles. The DFS algorithm works as follows: ● Start by putting any one of the graph's vertices on top of a stack. ● Take the top item of the stack and add it to the visited list. ● Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to the top of the stack. ● Keep repeating steps 2 and 3 until the stack is empty. DFS(G, u) u.visited = true for each v ∈ G.Adj[u] if v.visited == false DFS(G,v) init() { For each u ∈ G u.visited = false For each u ∈ G DFS(G, u) } Breadth first search(BFS) Page 35 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts Traversal means visiting all the nodes of a graph. Breadth First Traversal or Breadth First Search is a recursive algorithm for searching all the vertices of a graph or tree data structure. BFS algorithm A standard BFS implementation puts each vertex of the graph into one of two categories: ● Visited ● Not Visited The purpose of the algorithm is to mark each vertex as visited while avoiding cycles. The algorithm works as follows: ● Start by putting any one of the graph's vertices at the back of a queue. ● Take the front item of the queue and add it to the visited list. ● Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to the back of the queue. ● Keep repeating steps 2 and 3 until the queue is empty. create a queue Q Page 36 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts mark v as visited and put v into Q while Q is non-empty remove the head u of Q mark and enqueue all (unvisited) neighbours of u Tree Tree is a nonlinear hierarchical data structure that consists of nodes connected by edges. Important terms of tree. Path − Path refers to the sequence of nodes along the edges of a tree. Root − The node at the top of the tree is called root. There is only one root per tree and one path from the root node to any node. Parent − Any node except the root node has one edge upward to a node called parent. Child − The node below a given node connected by its edge downward is called its child node. Leaf − The node which does not have any child node is called the leaf node. Subtree − Subtree represents the descendants of a node. Page 37 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts Visiting − Visiting refers to checking the value of a node when control is on the node. Traversing − Traversing means passing through nodes in a specific order. Levels − Level of a node represents the generation of a node. If the root node is at level 0, then its next child node is at level 1, its grandchild is at level 2, and so on. Keys − Key represents a value of a node based on which a search operation is to be carried out for a node Tree traversal Traversal is a process to visit all the nodes of a tree and may print their values too. Because, all nodes are connected via edges (links) we always start from the root (head) node. That is, we cannot randomly access a node in a tree. There are three ways which we use to traverse a tree In-order Traversal In this traversal method, the left subtree is visited first, then the root and later the right sub-tree. We should always remember that every node may represent a subtree itself. if a binary tree is traversed in-order, the output will produce sorted key values in an ascending order. ● First, visit all the nodes in the left subtree ● Then the root node ● Visit all the nodes in the right subtree public void inorderTraversal(TreeNode root) { Page 38 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts if (root != null) { inorderTraversal(root.left); System.out.print(root.data + \" \"); inorderTraversal(root.right); } } Pre-order Traversal In this traversal method, the left subtree is visited first, then the root and later the right sub-tree. We should always remember that every node may represent a subtree itself. If a binary tree is traversed in-order, the output will produce sorted key values in an ascending order. ● Visit root node ● Visit all the nodes in the left subtree ● Visit all the nodes in the right subtree public void preorderTraversal(TreeNode root) { if (root != null) { System.out.print(root.data + \" \"); preorderTraversal(root.left); preorderTraversal(root.right); } } Post-order Traversal In this traversal method, the left subtree is visited first, then the root and later the right sub-tree. We should always remember that every node may represent a subtree itself. If a binary tree is traversed in-order, the output will produce sorted key values in an ascending order. ● Visit all the nodes in the left subtree ● Visit all the nodes in the right subtree ● Visit the root node Page 39 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts public void postorderTraversal(TreeNode root) { if (root != null) { postorderTraversal(root.left); postorderTraversal(root.right); System.out.print(root.data + \" \"); } } AVL Tree Adelson, Velski & Landis, AVL trees are height balancing binary search trees. AVL tree checks the height of the left and the right sub-trees and assures that the difference is not more than 1. This difference is called the Balance Factor To balance itself, an AVL tree may perform the following four kinds of rotations − ● Left rotation ● Right rotation ● Left-Right rotation ● Right-Left rotation Page 40 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts Single Rotation Left Rotation If a tree becomes unbalanced, when a node is inserted into the right subtree of the right subtree, then we perform a single left rotation. Right Rotation AVL tree may become unbalanced, if a node is inserted in the left subtree of the left subtree. The tree then needs a right rotation. Page 41 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts Double Rotation Left-Right Rotation The First type of double rotation is Left-Right Rotation. It is a combination of left rotation followed by right rotation. Right-Left Rotation The second type of double rotation is Right-Left Rotation. It is a combination of right rotation followed by left rotation. Spanning Tree Spanning tree is a tree that connects all the vertices of a graph with the minimum possible number of edges. Thus, a spanning tree is always connected. Also, a spanning tree never contains a cycle. A spanning tree is always defined for a graph and it is always a subset of that graph. Thus, a disconnected graph can never have a spanning tree. Page 42 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts Spanning Trees Terminologies: ● Connected Graph: A connected graph is a graph in which we can reach any vertex from any vertex. Thus, in a connected graph, all vertices are connected to each other through at least one path. ● Undirected Graph: It is a graph in which the edges don’t have a particular direction. In an undirected graph, the edges are bidirectional. ● Directed Graph: In this case, the edges are unidirectional. Thus, we can go from only one end to the other ends. For every edge, there is an associated direction. ● Simple graph: A simple graph is a graph that does not contain cycles and loops. Heap Heap is a special case of balanced binary tree data structure where the root-node key is compared with its children and arranged accordingly. Heap can be of two types − Page 43 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts Min-Heap − always smaller than the child node/s and the key of the root node is the smallest among all other nodes. This property is also called min heap property. Max-Heap − Always greater than its child node/s and the key of the root node is the largest among all other nodes. This property is also called max heap property. Heapify Page 44 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts Heapify is the process of creating a heap data structure from a binary tree. It is used to create a Min-Heap or a Max-Heap. Heapify(array, size, i) set i as largest leftChild = 2i + 1 rightChild = 2i + 2 if leftChild > array[largest] set leftChildIndex as largest if rightChild > array[largest] set rightChildIndex as largest swap array[i] and array[largest] Recursion The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function. recursive function can go infinite like a loop. To avoid infinite running of recursive function, there are two properties that a recursive function must have − Base criteria − There must be at least one base criteria or condition, such that, when this condition is met the function stops calling itself recursively. Progressive approach − The recursive calls should progress in such a way that each time a recursive call is made it comes closer to the base criteria Page 45 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts int fact(int n) { if (n < = 1) // base case return 1; else return n*fact(n-1); } In the above example, base case for n < = 1 is defined and larger value of number can be solved by converting to smaller one till base case is reached. Time Complexity Time Complexity is the study of the efficiency of algorithms. It tells us how much time is taken by an algorithm to process a given input. Calculating Order in terms of Input Size: In order to calculate the order (time complexity), the most impactful term containing n is taken into account (Here n refers to Size of input). And the rest of the smaller terms are ignored. Let us assume the following formula for the algorithms in terms of input size n: Page 46 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts Big O Notation Big O stands for ‘order of’ in our industry, but this is pretty different from the mathematical definition of the big O. Big O in mathematics stands for all those complexities our program runs in. But in industry, we are asked the minimum of them. So this was a subtle difference. Space complexity Space complexity is an amount of memory used by the algorithm (including the input values of the algorithm), to execute it completely and produce the result. Page 47 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts We know that to execute an algorithm it must be loaded in the main memory. The memory can be used in different forms: ● Variables (This includes the constant values and temporary values) ● Program Instruction ● Execution Auxiliary Space Auxiliary space is extra space or temporary space used by the algorithms during its execution. Memory Usage during program execution Instruction Space is used to save compiled instruction in the memory. environmental stack is used to storing the addresses while a module calls another module or functions during execution. Fibonacci series Fibonacci series generates the subsequent number by adding two previous numbers. Fibonacci series starts from two numbers − F0 & F1. The initial values of F0 & F1 can be taken 0, 1 or 1, 1 respectively. Fibonacci series satisfies the following conditions − Fn = Fn-1 + Fn-2 Recursion tree were to be implemented then this would have been the tree but now for n times the recursion function is called Original tree for recursion Data space is used to store data, variables, and constants which are stored by the program and it is updated during execution. Page 48 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts //Fibonacci Series using Recursion #include<stdio.h> int fib(int n) { if (n <= 1) return n; return fib(n-1) + fib(n-2); } int main () { int n = 9; printf(\"%d\", fib(n)); getchar(); return 0; } Page 49 of 57 All Rights Reserved. Vol. TLE001/03-2022

Foundation Course in Applications: Programming Concepts Tower of Hanoi Tower of Hanoi, is a mathematical puzzle which consists of three towers (pegs) and more than one rings Rules The mission is to move all the disks to some another tower without violating the sequence of arrangement. few rules to be followed for Tower of Hanoi are: ● Only one disk can be moved among the towers at any given time. ● Only the \"top\" disk can be removed. ● No large disk can sit over a small disk. Algorithm If we have 2 disks Step 1 − Move n-1 disks from source to auxiliary Step 2 − Move nth disk from source to destination Step 3 − Move n-1 disks from aux to destination Page 50 of 57 All Rights Reserved. Vol. TLE001/03-2022