The field of approximation algorithms has
developed in response to the difficulty in solving a good many optimization
problems exactly. This note will present general techniques that underly these
This note explains the
following topics related to Algorithm Analysis and Design:
Introduction to Design and analysis of algorithms, Growth of
Functions, Recurrences, Solution of Recurrences by
substitution,Recursion tree method, Master Method, Design and
analysis of Divide and Conquer Algorithms, Worst case analysis of
merge sort, quick sort and binary search, Heaps and Heap sort,
Priority Queue, Lower Bounds for Sorting.
Author(s): Mr. S.K.
Sathua, Dr. M.R. Kabat and Dr. R. Mohanty
note will examine various data structures for storing and accessing information
together with relationships between the items being stored, and algorithms for efficiently
finding solutions to various problems, both relative to the data structures and
queries and operations based on the relationships between the items stored.
Topics covered includes: Algorithm analysis, List, stacks and queues, Trees and
hierarchical orders, Ordered trees, Search trees, Priority queues, Sorting
algorithms, Hash functions and hash tables, Equivalence relations and disjoint
sets, Graph algorithms, Algorithm design and Theory of computation.
note covers the following topics related to Algorithm Analysis and Design: Model
and Analysis, Warm up problems, Brute force and Greedy strategy, Dynamic
Programming, Searching, Multidimensional Searching and Geometric algorithms,
Fast Fourier Transform and Applictions, String matching and finger printing,
Graph Algorithms, NP Completeness and Approximation Algorithms.
The material of this book is aimed at advanced
undergraduate information (or computer) science students,
postgraduate library science students, and research workers in the
field of IR. Some of the chapters, particular chapter 6, make simple
use of a little advanced mathematics.
These notes were prepared for the Programming Languages and
System Design course in the BE (Information Technology) course at
the University of Western Australia. The course note covers the
following topics: Algorithm Complexity, Classes of Efficient
Algorithms, Searching, Queues, Sorting, Graphs, Huffman Encoding,
Fast Fourier Transforms, Matrix Chain Multiplication, Intractible
Problems and Alpha-Beta search.