Module 1: Basic Concepts of Data Structures
System Life Cycle, Algorithms, Performance Analysis, Space Complexity, Time Complexity,
Asymptotic Notation, Complexity Calculation of Simple Algorithms.
SYSTEM LIFE CYCLE (SLC)
● SLC is a series of stages that are worked through during the development of a new
information system
● A lot of time and money can be wasted if a system is developed that doesn’t work
properly
Different Phases of System Life Cycle
1. Requirements
2. Analysis
3. Design
4. Refinement and coding
5. Verification
1. Requirement Phase:
● All programming projects begin with a set of specifications that defines the purpose of that
program.
● Requirements describe the information that the programmers are given (input) and the results
(output) that must be produced.
● Frequently the initial specifications are defined vaguely and we must develop rigorous input
and output descriptions that include all cases.
2. Analysis Phase
● In this phase the problem is break down into manageable pieces.
● There are two approaches to analysis:-bottom up and top down.
, ● Bottom up approach is an older, unstructured strategy that places an early emphasis on coding
fine points. Since the programmer does not have a master plan for the project, the resulting
program frequently has many loosely connected, error ridden segments.
● Top down approach is a structured approach divide the program into manageable segments.
● This phase generates diagrams that are used to design the system.
● Several alternate solutions to the programming problem are developed and compared during
this phase
3. Design Phase
● This phase continues the work done in the analysis phase.
● The designer approaches the system from the perspectives of both data objects that the
program needs and the operations performed on them.
● The first perspective leads to the creation of abstract data types while the second requires the
specification of algorithms and a consideration of algorithm design strategies.
Ex: Designing a scheduling system for university
Data objects: Students, courses, professors etc
Operations: insert, remove search etc
ie. We might add a course to the list of university courses, search for the courses taught
by some professor etc.
● Since abstract data types and algorithm specifications are language independent.
● We must specify the information required for each data object and ignore coding details.
Ex: Student object should include name, phone number, social security number etc.
4. Refinement and Coding Phase
● In this phase we choose representations for data objects and write algorithms for each
operation on them.
, ● Data objects representation can determine the efficiency of the algorithm related to it. So we
should write algorithms that are independent of data objects first.
● Frequently we realize that we could have created a much better system. (May be we realize that
one of our alternate design is superior than this). If our original design is good, it can absorb
changes easily.
5. Verification Phase
● This phase consists of
⮚ developing correctness proofs for the program
⮚ Testing the program with a variety of input data.
⮚ Removing errors.
Correctness of Proofs
● Programs can be proven correct using proofs.(like mathematics theorem)
● Proofs are very time consuming and difficult to develop for large projects.
● Scheduling constraints prevent the development of complete sets of proofs for a larger
system.
● However, selecting algorithm that have been proven correct can reduce the number of
errors.
Testing
● Testing can be done only after coding.
● Testing requires working code and set of test data.
● Test data should be chosen carefully so that it includes all possible scenarios.
System Life Cycle, Algorithms, Performance Analysis, Space Complexity, Time Complexity,
Asymptotic Notation, Complexity Calculation of Simple Algorithms.
SYSTEM LIFE CYCLE (SLC)
● SLC is a series of stages that are worked through during the development of a new
information system
● A lot of time and money can be wasted if a system is developed that doesn’t work
properly
Different Phases of System Life Cycle
1. Requirements
2. Analysis
3. Design
4. Refinement and coding
5. Verification
1. Requirement Phase:
● All programming projects begin with a set of specifications that defines the purpose of that
program.
● Requirements describe the information that the programmers are given (input) and the results
(output) that must be produced.
● Frequently the initial specifications are defined vaguely and we must develop rigorous input
and output descriptions that include all cases.
2. Analysis Phase
● In this phase the problem is break down into manageable pieces.
● There are two approaches to analysis:-bottom up and top down.
, ● Bottom up approach is an older, unstructured strategy that places an early emphasis on coding
fine points. Since the programmer does not have a master plan for the project, the resulting
program frequently has many loosely connected, error ridden segments.
● Top down approach is a structured approach divide the program into manageable segments.
● This phase generates diagrams that are used to design the system.
● Several alternate solutions to the programming problem are developed and compared during
this phase
3. Design Phase
● This phase continues the work done in the analysis phase.
● The designer approaches the system from the perspectives of both data objects that the
program needs and the operations performed on them.
● The first perspective leads to the creation of abstract data types while the second requires the
specification of algorithms and a consideration of algorithm design strategies.
Ex: Designing a scheduling system for university
Data objects: Students, courses, professors etc
Operations: insert, remove search etc
ie. We might add a course to the list of university courses, search for the courses taught
by some professor etc.
● Since abstract data types and algorithm specifications are language independent.
● We must specify the information required for each data object and ignore coding details.
Ex: Student object should include name, phone number, social security number etc.
4. Refinement and Coding Phase
● In this phase we choose representations for data objects and write algorithms for each
operation on them.
, ● Data objects representation can determine the efficiency of the algorithm related to it. So we
should write algorithms that are independent of data objects first.
● Frequently we realize that we could have created a much better system. (May be we realize that
one of our alternate design is superior than this). If our original design is good, it can absorb
changes easily.
5. Verification Phase
● This phase consists of
⮚ developing correctness proofs for the program
⮚ Testing the program with a variety of input data.
⮚ Removing errors.
Correctness of Proofs
● Programs can be proven correct using proofs.(like mathematics theorem)
● Proofs are very time consuming and difficult to develop for large projects.
● Scheduling constraints prevent the development of complete sets of proofs for a larger
system.
● However, selecting algorithm that have been proven correct can reduce the number of
errors.
Testing
● Testing can be done only after coding.
● Testing requires working code and set of test data.
● Test data should be chosen carefully so that it includes all possible scenarios.
