Data Structures CS205 Note-Module 1

CS205 Data Structures

First Module Full Note

DSA First Module Syllabus

Introduction to programming methodologies – structuredapproach, stepwise refinement techniques, programming style,documentation – analysis of algorithms: frequency count,definition of Big O notation, asymptotic analysis of simple algorithms. Recursive and iterative algorithms.

Introduction to programming methodologies

Programming methodology deals with the analysis, design and implementation of programs.

Algorithm

Algorithm is a step-by-step finite sequence of instruction, to solve a well-defined computational problem.That is, in practice to solve any complex real life problems; first we have to define the problems. Second step is to design the algorithm to solve that problem.Writing and executing programs and then optimizing them may be effective for small programs. Optimization of a program is directly concerned with algorithm design. But for a large program, each part of the program must be well organized before writing the program. There are few steps of refinement involved when a problem is converted to program; this method is called stepwise refinement method. There are two approaches for algorithm design;they are top-down and bottom-up algorithm design.

Stepwise Refinement Techniques

We can write an informal algorithm, if we have an appropriate mathematical model for a problem. The initial version of the algorithm will contain general statements, i.e., informal instructions. Then we convert this informal algorithm to formal algorithm, that is, more definite instructions by applying any programming language syntax and semantics partially. Finally a program can be developed by converting the formal algorithm by a programming language manual. From the above discussion we have understood that there are several steps to reach a program from a mathematical model. In every step there is a refinement (or conversion).That is to convert an informal algorithm to a program, we must go through several stages of formalization until we arrive at a program — whose meaning is formally defined by a programming language manual — is called stepwise refinement techniques.There are three steps in refinement process, which is illustrated in Figure

1. In the first stage, modeling, we try to represent the problem using an appropriate mathematical model such as a graph, tree etc. At this stage, the solution to the problem is an algorithm expressed very informally.

2. At the next stage, the algorithm is written in pseudo-language (or formal algorithm) that is, a mixture of any programming language constructs and less formal English statements. The operations to be performed on the various types of data become fixed.

3. In the final stage we choose an implementation for each abstract data type and write the procedures for the various operations on that type. The remaining informal statements in the pseudo-language algorithm are replaced by (or any programming language) C/C++ code.

Programming style

Following sections will discuss different programming methodologies to design a program.

1. Procedural

2. Modular

3. Structured

4. Object oriented

1.Procedural Programming

Procedural programming is a paradigm based on the concept of using procedures. Procedure (sometimes also called subprogram, routine or method) is a sequence of commands to be executed. Any procedure can be called from any point within the general program, including other procedures or even itself(resulting in a recursion).

Procedural programming is widely used in large-scale projects, when the

following benefits are important:

 re-usability of pieces code designed as procedures

 ease of following the logic of program;

 Maintainability of code.

 Emphasis is on doing things (algorithms).

 Most of the functions share global data.

 Data move openly around the system from function to function.

 Functions transform data from one form to another.

Download Full pdf