## chapter 2

**An algorithm**is a finite set of precise instructions for performing a computation or for solving a problem.**A linear search or sequential search**is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched.**Binary Search**is used to find the position of an element in the array only if the array is sorted .**Bubble sort i**s a sorting algorithm that compares two adjacent elements and swaps them until they are not in the intended order.**A greedy algorithm**is an approach for solving a problem by selecting the best option available at the moment.**Insertion sort**is a simple sorting algorithm that works similar to the way you sort playing cards in your hands.The array elements are compared with each other sequentially and then arranged simultaneously in some particular order**Big-O**gives the upper bound of a function O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n)**Omega**gives the lower bound of a function Ω(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n)**Theta bounds**the function within constants factorsFor a function g(n), Θ(g(n)) is given by the relation: Θ(g(n)) = { f(n): there exist positive constants c1, c2 and n0 such that 0 ≤ c1g(n) ≤ f(n)**The greatest common divisor (GCD)**refers to the greatest positive integer that is a common divisor for a given set of positive integers.**Modular arithmetic i**s a system of arithmetic for integers, which considers the remainder.

**Chapter 3 mathematics reasoning **

**A recurrence relation**is an equation that recursively defines a sequence where the next term is a function of the previous terms .**A summation,**also called a sum, is the result of arithmetically adding numbers or quantities.**Mathematical Induction**is a technique of proving a statement, theorem or formula which is thought to be true, for each and every natural number n.**Merge sort**is a sorting technique based on divide and conquer technique.

## chapter 7 – Tree

**Tree i**s a discrete structure that represents hierarchical relationships between individual elements or nodes**A node (or vertex)**of a network is one of the objects that are connected together. The connections between the nodes are called edges or links,**A root node**is either the topmost or the bottom node in a tree .- The number of subtrees of a node is called
**its degree.** - Two nodes connected to the same node which are same distance from the root vertex in a rooted tree are called
**siblings.** **The depth of a node**is the number of edges from that node to the tree’s root node.- In graph theory
**, a forest**is an undirected, disconnected, acyclic graph. In other words, a disjoint collection of trees is known as forest. Each component of a forest is tree. **A minimum spanning tree**is a special kind of tree that minimizes the lengths (or “weights”) of the edges of the tree.**BFS (Breadth First Search)**− It is a tree traversal algorithm that is also known as Level Order Tree Traversal. In this traversal we will traverse the tree row by row i.e. 1st row, then 2nd row, and so on.**DFS (Depth First Search ) −**It is a tree traversal algorithm that traverses the structure to its deepest node.**A minimum spanning tree i**s a spanning tree in which the sum of the weight of the edges is as minimum as possible.**Kruskal’s algorithm**is a minimum spanning tree algorithm that takes a graph as input and finds the subset of the edges of that graph which. form a tree that includes every vertex. has the minimum sum of weights among all the trees that can be formed from the graph.**Prim’s algorithm**is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph.**Binary tree**is a tree data structure in which each node has at most two children .**A full binary tree**(sometimes proper binary tree or 2-tree or strictly binary tree) is a tree in which every node other than the leaves has two children**Full Binary Tree:-**A Binary Tree is a full binary tree if every node has 0 or 2 children.**Graph traversal**refers to the process of visiting (checking and/or updating) each node in a tree data structure, exactly once