Design and Analysis of Algorithm

Problems that can be solved by Algorithms

Sorting Selection Bubble Quick Heap Insertion Radix Merge Searching Numerical Methods Combinatorial problem Graphs problem String Processing Problem Binary Search Tree

Backward Substitution

Backward substitution, like forward substitution, tries to find a pattern from which we can guess a solution that we then prove using other techniques—but now we start with T(n)...

Forward Substitution

Forward substitution Let’s consider the recurrence T(n) = T(n-1) + 2n – 1 T(0) = 0 The method of forward substitution proceeds by generating the first half-dozen or so...

Time Complexity

the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input....

Order of Growth

Let’s assume that your computer can perform 10,000 operations (e.g., data structure manipulations, database inserts, etc.) per second. Given algorithms that require lg n, n½, n, n2, n3, n4, n6,...

Linear inequality

In mathematics a linear inequality is an inequality which involves a linear function. A linear inequality contains one of the symbols of inequality: < is less than > is...

Matrices

Matrix A matrix is an ordered set of numbers listed rectangular form. Example. Let A denote the matrix [2 5 7 8] [5 6 8 9] [3 9 0...

Vectors

A vector is an object that has certain properties. What are these properties? We usually say that these properties are: a vector has a magnitude (or length) a vector...

Functions and Relations

A relation is any association between elements of one set, called the domain or (less formally) the set of inputs, and another set, called the range or set of...

Set Theory

Set: A set can be defined as a collection of things that are brought together because they obey a certain rule. These ‘things’ may be anything you like: numbers,...