OBJECTIVES

After going through this Unit, you should be able to:

SOME PRE-REQUISITES AND Asymptotic Bounds ASYMPTOTIC BOUNDS INTRODUCTION

We have already mentioned that there may be more than one algorithms, that solve a
given problem. In Section 3.3, we shall discuss eight algorithms to sort a given list of
numbers, each algorithm having its own merits and demerits. Analysis of algorithms,
the basics of which we study in Unit 3, is an essential tool for making well-informed
decision in order to choose the most suitable algorithm, out of the available ones if
any, for the problem or application under consideration.

ELEMEMTARY ALGORITHMICS SUMMARY

1. In this unit the following concepts have been formally or informally defined and discussed:

Problem, Solution of a Problem, Algorithm, Program, Process (all section 1.1) . Instance of a problem (Section 1.2)

OUTLINE OF ALGORITHMICS

We have already mentioned that not every problem has an algorithmic solution. The problem, which has at least one algorithmic solution, is called algorithmic or computable problem. Also, we should note that there is no systematic method (i.e., algorithm) for designing algorithms even for algorithmic problems.

BUILDING BLOCKS OF ALGORITHMS

Next, we enumerate the basic actions and corresponding instructions used in a
computer system based on a Von Neuman architecture. We may recall that an
instruction is a notation for an action and a sequence of instructions defines a
program whereas a sequence of actions constitutes a process. An instruction is also
called a statement.

PROBLEMS, AVAILABLE TOOLS & ALGORITHMS

In order to explain an important point in respect of the available tools, of which one must take care while designing an algorithm for a given problem, we consider some alternative algorithms for finding the product m*n of two natural numbers m and n.

CHARACTERISTICS OF AN ALGORITHM

Next, we consider the concept of algorithm in more detail. While designing an algorithm as a solution to a given problem, we must take care of the following five important characteristics of an algorithm:

EXAMPLE OF AN ALGORITHM

Before going into the details of problem-solving with algorithms, just to have an idea of what an algorithm is, we consider a well-known algorithm for finding Greatest Common Divisor (G.C.D) of two natural numbers and also mention some related historical facts. First, the algorithm is expressed in English. Then, we express the algorithm in a notation resembling a programming language.

ELEMEMTARY ALGORITHMICS INTRODUCTION

We are constantly involved in solving problem. The problems may concern our survival in a competitive and hostile environment, may concern our curiosity to know more and more of various facets of nature or may be about any other issues of interest to us. Problem may be a state of mind of a living being, of not being satisfied with some situation. However, for our purpose, we may take the unsatisfactory/ unacceptable/ undesirable situation itself, as a problem.

SOFTWARE DEVELOPMENT MODELS (Iterative Enhancement Model)

This model was developed to remove the shortcomings of waterfall model. In this model, the phases of software development remain the same, but the construction and delivery is done in the iterative mode. In the first iteration, a less capable product is developed and delivered for use.

SOFTWARE DEVELOPMENT MODELS (Build and Fix Model)

It is a simple two phase model. In one phase, code is developed and in another, code is fixed.depicts the Build and Fix model.

SOFTWARE DEVELOPMENT MODELS (Waterfall Model)

It is the simplest, oldest and most widely used process model. In this model, each phase of the life cycle is completed before the start of a new phase. It is actually the first engineering approach of software development.

SOFTWARE DEVELOPMENT MODELS

Software Engineering deals with the development of software. Hence, understanding the basic characteristics of software is essential. Software is different from other engineering products in the following ways: 

EVOLUTION OF SOFTWARE ENGINEERING

Any application on computer runs through software. As computer technologies have changed tremendously in the last five decades, accordingly, the software development has undergone significant changes in the last few decades of 20th century. In the early years, the software size used to be small and those were developed either by a single programmer or by a small programming team.

SOFTWARE ENGINEERING AND ITS MODELS

The field of software engineering is related to the development of software. Large software needs systematic development unlike simple programs which can be developed in isolation and there may not be any systematic approach being followed. In the last few decades, the computer industry has undergone revolutionary changes in hardware. That is, processor technology, memory technology, and integration of devices have changed very rapidly.

Arrange the following growth rates in increasing order

Question: Arrange the following growth rates in increasing order : 0 (4n), 0(n4), 0(1), 0(n3 logn), where '0' denotes 'big O'.

Solurion:

Using Insertion Sort or Bubble Sort

Question :Using Insertion Sort or Bubble Sort 
(state before starting the solution, which algorithm for sorting, you are using),
sort the following sequence of integers in decreasing order :
85 36 34 109 49 36

Solution: 

Let Lx denote floor function of x and Fx denote ceiling function of x. Find values of :

Question:  Let Lx denote floor function of x and Fx  denote ceiling function of x. Find values of :

  


Solution:

State any four characteristics of an algorithm, with an appropriate examples.

Question :State any four characteristics of an algorithm, with an appropriate examples.

Solution:

The Four - Colour Problem & The Fermat's Last Theorem

Question: State and describe any one of the following two problems :
(i)The Four - Colour Problem
(ii)The Fermat's Last Theorem


Solution:

Explain the relation/difference between a problem and its instance through an example of each.

Question : Explain the relation/difference between a problem and its instance through an example of each.

Solution:

Let f (n) denote the nth term of a sequence of integers given (5 marks) by the equation f(n) = f(n-1) +f(n-2) for n > 2 and f(1) = 1 and f(2) = 1, then using principle of mathematical induction, show that √ 5 f( n ) = {(1+ √ 5) / 2} n -- {(1 -- √ 5) / 2}n for all n > = 1

(b) Let f (n) denote the nth term of a sequence of integers given (5 marks)
by the equation f(n) = f(n-1) +f(n-2) for n > 2 and f(1) = 1
and f(2) = 1, then using principle of mathematical induction, show
that √ 5 f( n ) = {(1+ √ 5) / 2} n -- {(1 -- √ 5) / 2}n for all n > = 1

Show, through appropriate examples or otherwise, that the following three characteristics of an algorithm are independent of each other: (i.e., a method may have one of these properties, without having the other two) (i) finiteness (ii) definiteness (iii) effectiveness

 Question 1:
(a) Show, through appropriate examples or otherwise, that the following three characteristics of an algorithm are independent
of each other: (i.e., a method may have one of these properties,
without having the other two)
(i) finiteness (ii) definiteness (iii) effectiveness

MCA (3rd Semester) SOLVED ASSIGNMENT IGNOU MCA III 3rd Samester Solved Assignment 2013 2014 MCS-031 Design and Analysis of Algorithms

Course Code : MCS-031 | Course Title : Design and Analysis of Algorithms | Assignment Number : MCA (3)/031/Assign/13 | Maximum Marks : 100 | Weightage : 25%

Question 1:
(a) Show, through appropriate examples or otherwise, that the following three characteristics of an algorithm are independent of each other: (i.e., a method may have one of these properties,without having the other two) (i) finiteness  (ii) definiteness  (iii) effectiveness

MCA (3rd Semester) SOLVED ASSIGNMENT IGNOU MCA III 3rd Samester Solved Assignment 2013 2014 MCS-031 MCS-032 MCS-033 MCS-034 MCS-035

IGNOU MCA III 3rd Samester Solved Assignment 2013 2014
 (MCS-031, MCS-032, MCS-033, MCS-034, MCS-035 ,MCSL-036)
MCA (3rd Semester) SOLVED ASSIGNMENT IGNOU MCA III 3rd Samester Solved Assignment 2013 2014  MCS-031 MCS-032 MCS-033 MCS-034 MCS-035

BINARY SEARCH (MCA Related Topic) this is not BINARY SEARCH TREE

BINARY SEARCH (MCA Related Topic) this is  not BINARY SEARCH TREE