Algorithm Analysis

Framework for Algorithm Analysis

We may design many algorithms for solving many different kind of problems.If we want to compare these algorithm & even just plain evaluate them, we require sound mathematical bases and that is what we are going to do.Building a formal framework using which we can evaluate and also compare them.

Basic Idea

mathematical model of computer-mentally execute algorithms on computer model and evaluate the time.

This is the basic Scheme/idea we are going to develop.In order to develop this idea we need to answer certain question-

Mathematical model-

• What is the time required by model for every operation that a algorithm might perform.
• What should be the input data.
• How does our model relate to real computers.

Outline

• Formally define some basic terms
• mathematical model.
• Analysis Strategy.
• Examples of Algorithm and their analysis.
• Discussion of limitation of models.

ALGORITHMS

In mathematics, computer science, and related subjects, an algorithm is an effective method for solving a problem expressed as a finite sequence of instructions.

Each algorithm is a list of well-defined instructions for completing a task.

In Context of Computers-

To make a computer do anything, you have to write a computer program. To write a computer program, you have to tell the computer, step by step, exactly what you want it to do. The computer then "executes" the program, following each step mechanically, to accomplish the end goal.

When you are telling the computer what to do, you also get to choose how it's going to do it. That's where computer algorithms come in. The algorithm is the basic technique used to get the job done.

UNIT 1 INTRODUCTION

Introduction: Algorithms, analysis of algorithms, Growth of Functions, Master's Theorem,

Designing of Algorithms. Sorting and order Statistics: Heap sort, Quick sort, Sorting in Linear

time, Medians and Order Statistics.

Analysis And Design Of Algorithms-Overview

Welcome to the course on Design and Analysis of Algorithm.

In subsequent articles we will cover all the important topics in this course which help the student gating the concepts clearly.

First of all we are going to take the overview of the course and I am going to introduce you the main problem in the course & also the spirit of the course.

Algorithm

An algorithm (pronounced AL-go-rith-um) is a procedure or formula for solving a problem.

Given a set of problems, We have to solve the problem on a computer.We can solve most of the problems & design the algorithm.However awareness is needed to make a fast and optimized algorithm.

Designing a fast algorithm is a major challenge of the course.

Analysis And Design Of Algorithms-UPTU Syllabus

DESIGN & ANALYSIS OF ALGORITHMS (TCS-503)

Unit -I

Introduction: Algorithms, analysis of algorithms, Growth of Functions, Master's Theorem,

Designing of Algorithms. Sorting and order Statistics: Heap sort, Quick sort, Sorting in Linear

time, Medians and Order Statistics.

Unit -II

Advanced Data Structure: Red-Black Trees, Augmenting Data Structure. B-Trees, Binomial

Heaps, Fibonacci Heaps, Data Stricture for Disjoint Sets.

Unit -III

Advanced Design and Analysis Techniques: Dynamic Programming, Greedy Algorithms,

Amortized Analysis, Back Tracking.

Unit -IV

Graph Algorithms: Elementary Graphs Algorithms, Minimum Spanning Trees, Single-source

Shortest Paths, All-Pairs Shortest Paths, Maximum Flow, Traveling Salesman Problem.

Unit -V

Selected Topics: Randomized Algorithms, String Matching, NP Completeness, Approximation

Algorithms.

Object Oriented System (3rd sem)

What is OOS-

A software model or system designed using object oriented approach is basically a object oriented system

Object Oriented Approach

In software development, we generally uses either a function oriented approach or Object oriented Approach.

Function oriented approach is basically what you have done or observed while programming in C.

Our overall system is divided into functions that performs various operation on data.Function are the basic element of our system.

For eg. While you are going to build a software system for Library management.Using Function oriented approach while designing the system we try to identify the function making up the system.Some of the possible function might be-"returning of books by student to librarian","issuing of books","putting books on shelf" etc.

So while designing the actual system , we consider these system for carrying out the manipulation of data and providing the desired result.

Object Oriented Approach is something which is very easy to understand and implement. Actully all real world Problems can be viewed as object oriented.

Its a real world programming concept.

In this approach of design,we considers the object making up the system,and objects has the data and related function that can be used by it.

So take a real world problem for understanding it-

If you want to build a system for library management then the possible objects that make up the system are "student","librarian","shelf" etc.All these object has data(attributes of object) and methods(operations performed on data) with in them.