MCS-011, PROBLEM SOLVING AND PROGRAMMING, AN INTRODUCTION TO C, C++, MCA - MASTER OF COMPUTER APPLICATIONS; IGNOU; Indira Gandhi National Open University, School of Computer and Information Science; & Question Papers, Assignments; STUDENTS FORUM;
NOTE : As these are my personal Notes, So I Strongly Request you to follow your own Books and Notes provided by the Concern University, as these notes are for my personal use only, Thanks, Regards.
STUDY MATERIAL NO. - 1 (AN INTRODUCTION TO C)
COURSE INTRODUCTION : "The best way to escape from a problem is to solve it."- Alan Saporta
Solving a problem means finding a way out of a difficulty, a way around an obstacle, attaining an aim which was not immediately attainable. Solving problems is a specific achievement of intelligence, and intelligence is the specific gift of mankind: solving problems can be regarded as the most characteristically human activity; It is an art, e.g. if you want to learn swimming - you need to go into the water, so - to fight a problem you need to solve it ! :-)
Today, the usage of computers appears everywhere, especially in the educational, business, research & scientific fields. Computer is Simply a Logic Machine that performs computations and calculations at an incredible speed. Introducing the usage of computers to solve problems will help them immensely when they enter the job market. The purpose of this course is to act as an introduction to the thinking world of computers, to help students develop the LOGIC, ABILITY TO SOLVE THE PROBLEMS EFFICIENTLY.
Students in every discipline(अनुशासन) need to appriciate computers not only for the applications they can run, but also for the problems they cann solve. Problem Solving with Computers introduces the concepts of Algorithms, iteration and conditionals, top-down design, testing and debugging and analysis of solution using any programming language or any package.
Knowledge in a programming language is prerequisite(शर्त) to the study of most of computer science courses. This knowledge area consists of those skills and concepts that are essential to problem solving and programming practice independent of the Underlying Paradigm(मिसाल, अंतर्निहित प्रतिमान, आधारभूत-उदाहरण/ आदर्श). All programming languages will share one similarity, i.e., all Languages are based on logic. A programming language is a programmer's principal interface with the computer. More than just knowing how to program in a single language, programmers need to understand the different styles of programming promoted by different languages. Later in your professional life, you will be working with many different programming languages and styles at once, and will encounter many different languages over the course of your career. Understanding the variety of programming language and the design tradeoffs between the different programming paradigms makes it much easier to master new languages quickly.
We will discuss various concepts about learning an techniques for problem solving; emphasizing(बल) structured programming. In this course, you will learn concepts of computer programming, and how to implement those ideas using C programs.
This course introduces you the fundamental techniques of C programming as a foundation for more advanced study of computer science. We will discuss various concepts about learning and techniques for problem solving, emphasizing structured programming. Our goal will be to improve your reasoning and thinking skills, which should prove helpful, not only in future programming, but throughout your academic and professional career. In this course, the topics included the problem solving strategies, concept of an algorithm, flow-charting, standard C programming constructs, primitive data types and fundamental data structures (strings, arrays, and structures and unions), files and pointers.
Upon completing this course, you should be able to :
- Apply problem solving techniques ;
- Design Algorithms and Flowcharts;
- Develop a working knowledge of the C language and its uses, characteristics, and capabilities;
- Define problems and crate solutions that can be converted into modular, structured C programs;
- Use of Libraries of C functions;
- To use Arrays and Structures to organize data (Data Structures C++);
- To make a righteous stab (धर्मी वार) at understanding pointers;
- Read and write data to and from files.
BLOCK - 1 : Covers the Problem Solving Skills and the Basic Programming Constructs of C.
BLOCK - 2 : Covers the Control Statements, Arrys, Strings and Functions;
BLOCK - 3 : Covers the Structures, Pointers and the File Handling in C.After going through this course, yo shoule be able to write fairly complex programs using C programming language. to get the maximum benefit from this, it is necessary that you should understand and execute all the example programs given in the course, as well, complete the assignment problems given in the LAB MANUAL also.
===================== page =========================
BLOCK INTRODUCTION : (BLOCK - 1) :
This Block is on problem solving techniques and basic programming constructs of C Language.
This Block consists of 4 units / as follows :
UNIT - 1 : Overview of Problem Solving Techniques, Algorithm Design, Top - Down Design, Analysis os Algorithm Efficiency and Complixity.
UNIT - 2 : Introduces the History of C Language, Salient Features(मुख्य बातें) of C,Structure of a C Program, way to write, compile, link and run a C Program.
UNIT - 3 : Outlines the basic programming constructs of C Language.
UNIT - 4 : Provides the overview of the various operators and primitive data types in C.
========================= page ======================
UNIT - 1 : PROBLEM SOLVING :This Block consists of 4 units / as follows :
UNIT - 1 : Overview of Problem Solving Techniques, Algorithm Design, Top - Down Design, Analysis os Algorithm Efficiency and Complixity.
UNIT - 2 : Introduces the History of C Language, Salient Features(मुख्य बातें) of C,Structure of a C Program, way to write, compile, link and run a C Program.
UNIT - 3 : Outlines the basic programming constructs of C Language.
UNIT - 4 : Provides the overview of the various operators and primitive data types in C.
========================= page ======================
Structure
1.0 - Introduction
1.1 - Objectives
1.2 - Problem - Solving Techniques
----- 1.2.1 -- Step for Problem Solving
----- 1.2.2 -- Using Computer as a Problem Solving Tool
1.3 - Design of Algorithms
----- 1.3.1 -- Definition
----- 1.3.2 -- Features of Algorithm
----- 1.3.3 -- Criteria to be followed by an Algorithm
----- 1.3.4 -- Top Down Design
1.4 - Analysis of Algorithm Efficiency
----- 1.4.1 -- Redundant Computations
----- 1.4.2 -- Referencing Array Elements
----- 1.4.3 -- Inefficiency Due to Late Termination
----- 1.4.4 -- Early Detection of Desired Output Condition
----- 1.4.5 -- Trading Storage for Efficient Gains
1.5 - Analysis of Algorithm Complexity
----- 1.5.1 -- Computational Complexity
----- 1.5.2 -- The Order of Notation
----- 1.5.3 -- Rules for using the Big - O Notation
----- 1.5.4 -- Worst and Average Case Behavior
1.6 - Flowcharts
----- 1.6.1 -- Basic Symbols used in Flowchart Design
1.7 - Summary
1.8 - Solution /
1.9 - Further Readings
-----------------------------------------------------------------
1.0 - INTRODUCTION
-----------------------------------------------------------------In daily life, we routinely encounter and solve problems. We pose problems that we need or want to solve. For this we make use of a available resources, and solve them. Some are Simple and Some are Complex.
In this Unit we introduce you to the concept of problem solving.
the problem-solving is a skill and there are no universal approaches one can take to solving problems. In general, as one gains experience in solving problems, one develops one's own techniques and strategies, though they are often intangible. Problem-solving skills are recognized as an integral component of computer programming. It is a demand and intricat process which is equally important throughout the project life cycle especially - study, designing, development, testing and implementation stages. The computer problem solving process requires :
- Problem Anticipation (पूर्वानुमान,संभावना,अपेक्षा)
- Careful Planning
- Proper Thought Process
- Logical Analysis
- Persistence(दृढ़ता,हठ,जड़ता,अटलता,ज़िद) and Attention
Computer is a very powerful tool, It performs these manipulations very quickly and has memory for storing input, lists of commands and output. A computer cannot think in the way we associate with humans. Several Steps need to be considered before writing a program. DEBUGGING : The process of finding and removing errors in a program is Debugging; It should also make the act of problem solving with a computer a much simpler task.
SOFTWARE : ALL PROGRAMS ARE ==> SOFTWARE
HARDWARE : ALL ELECTRONIC I/O DEVICES, STORAGE MEDIA (we can touch them physically)
SOURCE PROGRAM : INSTRUCTIONS OF HLL USED TO CODE A PROBLEM TO FIND SOLUTION.
COMPILER (or INTERPRETER) : WHO TRANSLATE A SOURCE PROGRAM INTO THE OBJECT PROGRAM.
OBJECT PROGRAM : IF THERE IS NO ERROR - THE SOURCE PROG. IS TRANSFORMED INTO THE MACHINE LANGUAGE PROG. CALLED OBJECT PROGRAM. (The object program is executed to perform calculations - is the execution phase).
╔---------------------------------------------------\
| SOURCE --> COMPUTER --> OBJECT --> DATE IF |
| PROGRAM SYSTEM PROGRAM REQUIRED |
| ------- -------- ------- -------- |
| || |
| \/ |
| \/ |
| R E S U L T |
|===================================================|
------------------------- PAGE -------------------
1.1 OBJECTIVES :
--------------------------------------------------------------------------------
After going through this unit, you should be able to :
------------------------- PAGE -------------------
1.1 OBJECTIVES :
--------------------------------------------------------------------------------
After going through this unit, you should be able to :
- Apply problem solving techniques ;
- Define an algorithm and its features;
- Describe the Analysis of Algorithm efficiency;
- Discuss the analysis of Algorighm complexity; and
- Design Flowcharts.
1.2 PROBLEM - SOLVING TECHNIQUES
--------------------------------------------------
It is a Creative process which defines systematization and mechanization. There are a number of steps that can be taken to raise the level of one's performance in problem solving.
--------------------------------------------------
1.2.1 STEPS FOR PROBLEM - SOLVING :
--------------------------------------------------
It is a Creative process which defines systematization and mechanization. There are a number of steps that can be taken to raise the level of one's performance in problem solving.
--------------------------------------------------
1.2.1 STEPS FOR PROBLEM - SOLVING :
--------------------------------------------------
- ==== 1. PROBLEM DEFINITION PHASE : Understood the Problem
- ==== 2. GETTING STARTED ON A PROBLEM :
- ==== 3. THE USE OF SPECIFIC EXAMPLES :
- ==== 4. THE USE OF SPECIFIC EXAMPLES :
- ==== 5. SIMILARITY AMONG PROBLEMS :
- ==== 6. WORKING BACKWARDS FROM THE SOLUTION :
- Problem Definition Phase[UNDERSTOOD THE PROBLEM] : First Most Step is - we should - Fully Understand the problem. In problem definition phase, we must emphasize what must be done rather that how is it to be done. i.e. - we try to extract the precisely(निश्चित रूप से, हूबहू, विधि पूर्वक,ठीक रीति से) defined set of tasks from the problem statement.
. - Getting Started on a Problem[UNDERSTOOD THE COMPLICATIONS OF THE PROBLEM] : there are MANY WAYS TO SOLVE A PROBLEM, and sometime there are SEVERAL SOLUTIONS of a Single Problem !!!!; -- So if you don's Understand The Problem Carefully - You CAN'T SOLVE IT !!!; so first make Important Points FIRST - instead of making a PERMANENT solution (mostly for big problems).
. - The use of Specific Examples : To Start a Solution - we can make use of HEURISTICS i.e. - THE RULE OF THUMB - This approach of focusing on a particular problem can give us the foothold (पैर जमाना) we need for making a start.
(NOTE : HEURISTICS = "find" or "discover"= experience-based techniques for problem solving, learning, and discovery, used to speed up the process of finding a satisfactory solution, where an exhaustive search is impractical. Examples of this method include using a "rule of thumb", an educated guess, an intuitive judgment, or common sense. In more precise terms, heuristics are strategies using readily accessible, though loosely applicable, information to control problem solving in human beings and machines.)
. - Similarties Among Problems : One way to make a start is by considering a specific example. Another approach is to bring the experience to bear on the current problem. So, it is important to see if there are any similarities between the current problem and the past problems which we have solved. The more experience one has toe more tools and techniques one can bring to bear in tackling the given problem. But sometimes, it blocks us from discovering a desirable or better solution to the problem. One must be able to metaphorically turn a problem upside down, inside out, sideways, backwards, forwards and so on. Once one has developed this skill it should be possible to get started on any problem.
. - Working Backwards from the Solution : In come case we can assume that we already have the solution to the problem and then try to work backwards to the starting point. We can systematize the investigations. Another practice that helps to develop the problem solving skills is -- once we have solved a problem, to consciously reflect back on the way we went about discovering the solution.
-----------------------------------------------------------------------------------
- Computer is a very powerful general purpose tool.
- It is a TIME SAVING TOOL.
- It can Minimize the LABOR & COST of the PROJECT.
- It can Reduce the ERROR CHANCES.
.
SOME ERROR MINIMIZATION TOOLS :
- Developing an Alghrithm and Flowchart.
- Use Computer HLL or MLL like C, C++, Turbo C etc.
- Enter the program using some editor.
- Test and debug the program.
- Run the program, input data, and get the results.
1.3. DESIGN OF ALGORITHMS :
-----------------------------------------------------------------------------------
1.3.4 TOP DOWN DESIGN : Once we have defined the problem and have an indea of how to solve it, we can then use a powerful techniques for design algorithms. Hence for Complex Problems - A technique is known as TOP- DON DESIGN OR STEPWISE REFINEMENT.
Every Algorithm uses some of the computer's resources like central processing time and internal memory to complete its task. Because of High cost of computing resources, hence analysis of Algorithm is less obviously necessary, but has several purposes :
1.4.1 REDUNDANT(अनावश्यक) COMPUTATIONS : or Redundant(अनावश्यक) Computations result in inefficiency in the implementation of the Algorithms.Do Short Method instead of Long Method : Like :
for i=0 to n
x=x+1;
y=(a*a*a*c)*x*x+b*b*x;
print x,y
NOW the more simpler and short way : like :
x=0
d=a*a*a*c;
e=b*b;
for i = 0 to n
x=x_1;
y=d*x*x+e*x;
print x,y
1.4.2. REFERENCING ARRAY ELEMENTS : Using Reference instead of repeating - the same Array again and again; e.g. :
Version (1) x=1;
for i=0 to n
if (a[i] > a[x]) x=i;
next i
max = a[x];
Version (2) x=1;
max=a[1];
for i=0 to n
if(a[i]>max)
x=i;
max=a[i]
next i
1.4.3 INEFFICIENCY (अदक्षता,अक्षमता) DUE TO LATE TERMINATION : where more testa are done than are required, e.g. if in the liner search process, all the list elements are checked for a pearticular element even if the point is reached where it was known that the element cannot occur later (in case of sorted list).
SECOND EXAMPLE : in case of BUBBLE SORT ALGORITHM - where the inner loop should not proceed beyond n-i, because last i elements are already sorted:
1.4.4 EARLY DETECTION OF DESIRED OUTPUT CONDITION : Sometimes the loops can be terminated early, if the desired output conditions are met. This SAVES A LOT OF UNFRUITFUL EXECUTION.
(For example in the bubble sort algorithm, if during the current pass of the inner loop there are no exchange in the data, then the list can be assumed to be sorted and the search can be terminated before running the outer loop for n times).
1.4.5 TRADING STORAGE FOR EFFICIENT GAINS : Trading between Storage and Efficiency is often used to improve the performance of an Algorithm. In Short MINIMIZATION OF LOOPS is a Good Idea.
--------------------------------------------------------------------------------------------------------
1.5 ANALYSIS OF ALGORITHM COMPLEXITY : (QUALITIES AND COMPLEXITY OF ALGORITHMS) :
--------------------------------------------------------------------------------------------------------
- The Plan, expressed as a sequence of operations - is called ALGORITHM.
- An Algorithm is just an outline or idea behind a program.
- One could translate each pseudo-code statement to small number of lines of actual codes.
- An ALGORITHM is a Finite Set of Steps defining the solution of a particular problem.
- An ALGORITHM is expressed in PSEUDO CODE.
- ALGORITHM is a Language Independent.
- ALGORITHM will enable the programmer to translate into a computer program using High- Level Language.
- Proper Understanding of the Problem : Algorithm should be clearely defined so that the person developing the Algorithm can understand the expectations from it.
- Use of Procedures / Functions to Emphasize (ज़ोर देना) Modularity (प्रतिरूपकता): The program then can be implemented as calls to the various procedures that will be needed in the final implementations.
- Choice of Variable Names : A Clear definition of all Variables and Constants is Helpful. (For Example : it is better to use variable day for the day for the weeks, instead of the variable a or something else).
- Documentation of the Program : A related part of the documentation is the information that the programmer present to the user during the execution of the program (Like - USER MANUAL).
- INPUT : There should be zero or more values which are to be supplied.
- OUTPUT : At least one result is to be produced.
- DEFINITENESS (निश्चितता) : Each step must be clear and unambiguous (स्पष्ट).
- FINITENESS (परिमितता, सीमित) : If we trace the steps of an Algorithm, then for all cause, the Algorithm must terminate after a finite number of steps.
- EFFECTIVENESS: Each step must be sufficiently basic that a person using only paper and pencil and in principle carry it out in addition, not only each step is definite, it must also be feasible.
- START
- Read two numbers a and b
- Calculate the sum of a and b
- Store it in Sum
- Stop
- Start
- Set the sum of the data values and the count to zero.
- As long as the data value exist, add the data value to the sum and add 1 to the count.
- To compute the average, divide the sum by the count.
- Display the average.
- Stop
- Start
- Read the number n
- [Initialize]
- i <-- 1, fact <-- 1
- Repeat step 4 through 6 until i=n
- fact <-- fact * i
- i <-- i + 1
- Print fact
- Stop
- Start
- Read the number num
- i <-- 2, flag <--1
- Repeat step 4 throgh 6 until i< num or flag=0
- rem <-- num mod i
- if rem = 0 then
flag <-- 0
else
i <-- i + 1 - if flag = 0 then
Print Number is not prime
Else
Print Number is prime - Stop
1.3.4 TOP DOWN DESIGN : Once we have defined the problem and have an indea of how to solve it, we can then use a powerful techniques for design algorithms. Hence for Complex Problems - A technique is known as TOP- DON DESIGN OR STEPWISE REFINEMENT.
- Top Down Design is useful in Large and Logical Complexities & Details.
- Helps in Step by Step Problem Solving.
- Before applying Top Down Design - we must at least have the outline of a solution.
- Before Solution - we need to Divide the Solutions into SUB TASK / SUB PROBLEMS.
- If needed - then Break / Divide - each Sub-Task into SMALLER SUB TASK.
Every Algorithm uses some of the computer's resources like central processing time and internal memory to complete its task. Because of High cost of computing resources, hence analysis of Algorithm is less obviously necessary, but has several purposes :
- Analysis can be more reliable than experimentation.
- As there are many problems and many solutions for a single problem - hence careful analysis tells us - that which solution is Best and Less - Time / Money Consuming.
- If we waited until after all the code was written to discover that something runs very slowly, it could be a major disaster, but if we do the analysis first - we have time to discover SPEED PROBLEMS.
- Careful Analysis of / on - fast and slow parts
1.4.1 REDUNDANT(अनावश्यक) COMPUTATIONS : or Redundant(अनावश्यक) Computations result in inefficiency in the implementation of the Algorithms.Do Short Method instead of Long Method : Like :
for i=0 to n
x=x+1;
y=(a*a*a*c)*x*x+b*b*x;
print x,y
NOW the more simpler and short way : like :
x=0
d=a*a*a*c;
e=b*b;
for i = 0 to n
x=x_1;
y=d*x*x+e*x;
print x,y
1.4.2. REFERENCING ARRAY ELEMENTS : Using Reference instead of repeating - the same Array again and again; e.g. :
Version (1) x=1;
for i=0 to n
if (a[i] > a[x]) x=i;
next i
max = a[x];
Version (2) x=1;
max=a[1];
for i=0 to n
if(a[i]>max)
x=i;
max=a[i]
next i
Here Version (2) is more efficient than Version (1) Algo.
1.4.3 INEFFICIENCY (अदक्षता,अक्षमता) DUE TO LATE TERMINATION : where more testa are done than are required, e.g. if in the liner search process, all the list elements are checked for a pearticular element even if the point is reached where it was known that the element cannot occur later (in case of sorted list).
SECOND EXAMPLE : in case of BUBBLE SORT ALGORITHM - where the inner loop should not proceed beyond n-i, because last i elements are already sorted:
1.4.4 EARLY DETECTION OF DESIRED OUTPUT CONDITION : Sometimes the loops can be terminated early, if the desired output conditions are met. This SAVES A LOT OF UNFRUITFUL EXECUTION.
(For example in the bubble sort algorithm, if during the current pass of the inner loop there are no exchange in the data, then the list can be assumed to be sorted and the search can be terminated before running the outer loop for n times).
1.4.5 TRADING STORAGE FOR EFFICIENT GAINS : Trading between Storage and Efficiency is often used to improve the performance of an Algorithm. In Short MINIMIZATION OF LOOPS is a Good Idea.
--------------------------------------------------------------------------------------------------------
1.5 ANALYSIS OF ALGORITHM COMPLEXITY : (QUALITIES AND COMPLEXITY OF ALGORITHMS) :
--------------------------------------------------------------------------------------------------------
- EASILY MODIFIABLE.
- SHOULD BE CORRECT AND CLEARLY DEFINED.
- LESS TIME CONSUMING, MORE ECONOMICAL.
- WELL DOCUMENTED, DON'T HAVE A DETAILED KNOWLEDGE OF THE INNER WORKING.
- MAY RUN ON ALL COMPUTERS - ALL PLATFORMS.
- THE SOLUTION SHOULD BE PLEASING AND SATISFYING TO ITS USER.
- ARE ABLE TO BE USED AS A SUB-PROCEDURE FOR OTHER PROBLEMS.
1.5.1 COMPUTATIONAL COMPLEXITY :More computing resources are needed to solve larger problems in the same class. To decide how to characterize the behavior of an algorithm as a function of size of the problem n, we must study the mechanism very carefully to decide just what constitutes the dominant mechanism. It may be the number of times a particular expression is evaluated, or the number of comparisons or exchange that must be made as n grows. For example, comparisons, exchanges, and moves count most in sorting algorithm. The number of comparisons usually dominated so we use comparisons in computational model for sorting algorithms.
1.5.2 THE ORDER OF NOTATION (संकेत पद्धति) : O-notation gives an upper bound to a function within a constant factor.
For a given function g(n), we denote by O(g(n)) the set of functions.
For example a double nested loop structure of the following algorithm immediately yields O(n2) upper bound on the worst case running time.
What we mean by saying "the running times is O(n2)" is that the worst case running time (which is a function of n) is O(n2). Or equivalently, no matter what particular input of size n is chosen for each value of n, the running time on the set of inputs is O(n2).
1.5.3 RULES FOR USING THE BIG-O NOTATION : Big-O bounds, because they ignore constants, usually allow for very simple exprssion for the runnign time bounds, Below are some properties of Big-O gives an upper bound only. If an algorithm is O(N2), it doesn't have to take N2 steps (or a constant multiple of N2 ). But it can't take more than N2. so any algorithm that is O(N), is also an O(NO2) algorithm. If this seems confusing, think of big-O as being like "<". Any number that is <N is also <NO2.
In many practical applications it is very important to have a measure of the expected complexity of an algorithm rather than the worst case behavior. The expected complexity gives a measure of the behavior of the algorithm averaged over all possible problems of size n.
As a simple example : suppose we wish to characterize the behavior of an algorithm that linearly searches an ordered list of elements for some value x. 1 2 3 4 5 .......... N
In the worst case, the algorithm examines all n values in the list before terminating.
In the worst case, the algorithm examines all n values in the list before terminating.
In the average case, the probability that x will be found at position 1 is 1/n, at position 2 is 2/n and so on. Therefore :
1.6 FLOWCHARTS
---------------------------------------------------------------------------------------------
Example 1.5 - Flow Chart Sample
to Count Sum of Two Numbers a and b i.e. TOTAL = a + b (where a and b are Integers)
Example 1.7 (Pleare refer your Book Page 20)
FOR UNIT 2 - BASICS OF C -- (CLICK HERE)
1.5.2 THE ORDER OF NOTATION (संकेत पद्धति) : O-notation gives an upper bound to a function within a constant factor.
For a given function g(n), we denote by O(g(n)) the set of functions.
O(g(n)) = { f(n) : there exist positive constants c and n0,
such that 0 <= f(n) <=cg(n) for all n >=n0 }
For example a double nested loop structure of the following algorithm immediately yields O(n2) upper bound on the worst case running time.
for i=0 to n
for j=0 to n
print i j
next j
next i
What we mean by saying "the running times is O(n2)" is that the worst case running time (which is a function of n) is O(n2). Or equivalently, no matter what particular input of size n is chosen for each value of n, the running time on the set of inputs is O(n2).
1.5.3 RULES FOR USING THE BIG-O NOTATION : Big-O bounds, because they ignore constants, usually allow for very simple exprssion for the runnign time bounds, Below are some properties of Big-O gives an upper bound only. If an algorithm is O(N2), it doesn't have to take N2 steps (or a constant multiple of N2 ). But it can't take more than N2. so any algorithm that is O(N), is also an O(NO2) algorithm. If this seems confusing, think of big-O as being like "<". Any number that is <N is also <NO2.
- Ignoring constant factors: O(c f(N)) = O(f(N)), where c is a constant; e.g. O(20 N3) =O(N3)
- Ignoring smaller terms: If a<b then O(a+b)=O(b), for example, O(N2 + N)= O(N2).
- Upper bound only: If a<b then an O(a) algorithm is also an O(b) algorithm. For example, an O(N) algorithm is also an O(N2) algorithm (but not vice versa).
- N and log N are bigger than any constant, from an asymptotic (अनन्तस्पर्शी, पास रहते हुए भी कभी न मिलने वाली स्थिति) view(that means for large enough N). So if k is a constant, an O(N +k) algorithm is also O(N), by ignoring smaller terms. similarly, an O(log N + k) algorithm is also O(log N).
- Another consequence of the last item is that an O(N log N + N) algorithm, which is O(N(log N+1)), can be simplified to O(N log N).
In many practical applications it is very important to have a measure of the expected complexity of an algorithm rather than the worst case behavior. The expected complexity gives a measure of the behavior of the algorithm averaged over all possible problems of size n.
As a simple example : suppose we wish to characterize the behavior of an algorithm that linearly searches an ordered list of elements for some value x. 1 2 3 4 5 .......... N
In the worst case, the algorithm examines all n values in the list before terminating.
In the worst case, the algorithm examines all n values in the list before terminating.
In the average case, the probability that x will be found at position 1 is 1/n, at position 2 is 2/n and so on. Therefore :
Average search cost = 1/n(1+2+3+ ........ +n)
= 1/n(n/2(n+1)) = (n+1)/2
Let us see how to represent the Algorithm in a graphical form using FLOWCHARTS : 1.6 FLOWCHARTS
---------------------------------------------------------------------------------------------
- The Next Step after Algorithm is FLOWCHART.
- FLOWCHART is a GRAPHICAL REPRESENTATION of an ALGORITHM.
- in FLOWCHARTS we use Symbols, Arrows, Shapes to indicate the flow of information and processing.
- FLOWCHART shows the general Outline of how to solve a problem of perform a Task.
----------------------------------->
------------------------------------------>
------------------------------------------------->
------------------------------------------>
----------------------------------->
Example 1.5 - Flow Chart Sample
to Count Sum of Two Numbers a and b i.e. TOTAL = a + b (where a and b are Integers)
___________ _____________ ________
/ \ / / | Sum = |
| START |----> / READ a b /---->| a + b |
\___________/ /____________/ |________|
| ___________ _______\/____
EXAMPLE 1.6
/ \ / /
| START |----> / READ a b /
\___________/ /____________/
EXAMPLE 1.6
Example 1.7 (Pleare refer your Book Page 20)
FOR UNIT 2 - BASICS OF C -- (CLICK HERE)
