**Design and Analysis of Algorithms Notes**

In these “* Design and Analysis of Algorithms Notes PDF*“, We will study a collection of algorithms, examining their design, analysis and sometimes even implementation. The aim of these notes is to give you sufficient background to understand and appreciate the issues involved in the design and analysis of algorithms.

The topics we will cover will be taken from the following list:

**Algorithm Design Techniques: **Iterative technique: Applications to Sorting and Searching (review), their correctness and analysis. Divide and Conquer: Application to Sorting and Searching (review of binary search), merge sort, quick sort, their correctness and analysis.

**Dynamic Programming: **Application to various problems (for reference; Weighted Interval Scheduling, Sequence Alignment, Knapsack), their correctness and analysis. Greedy Algorithms: Application to various problems, their correctness and analysis.

**Sorting and Searching: **Heapsort, Lower Bounds using decision trees, sorting in Linear Time – Bucket Sort, Radix Sort and Count Sort, Medians & Order Statistics, complexity analysis and their correctness.

**Advanced Analysis Technique:** Amortized analysis

**Graph Algorithms:** Breadth First Search, Depth First Search and its Applications

This Design and Analysis of Algorithms Lecture Notes PDF will require the following basic knowledge:

**Java Programming:**classes, control structures, recursion, testing, etc**Data Structures:**stacks, queues, lists, trees, etc.**Complexity:**definition of “big O”, Θ notation, amortized analysis etc.**Some maths:**proof methods, such as proof by induction, some understanding of continuous functions

An algorithm is a well-defined finite set of rules that specifies a sequential series of elementary operations to be applied to some data called the input, producing after a finite amount of time some data called the output. Algorithms (along with data structures) are the fundamental “building blocks” from which programs are constructed. An algorithmic solution to a computational problem will usually involve designing an algorithm, and then analyzing its performance.

A good algorithm designer must have a thorough background knowledge of algorithmic techniques, but especially substantial creativity and imagination.

A good algorithm analyst must be able to carefully estimate or calculate the resources (time, space or other) that the algorithm will use when running. This requires logic and often some mathematical ability.