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 is 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 is 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 is 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 is 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