Software Design for Engineers and Scientists (eBook)

Cover 1
Contents 6
Preface 12
Acknowledgements 14
Errors 15
1 Introduction 16
1.1 Theme 16
1.2 Audience 17
1.3 Three definitions and a controversy 17
1.4 Essential software design 18
1.5 Outline of the book 19
Foundations 19
Software technology 20
Applied software design 20
Case studies 21
1.6 Presentation conventions 21
1.7 Chapter end material 22
Bibliography 22
2 Fundamentals 23
2.1 Introduction 23
2.2 The nature of software 23
2.3 Software as mathematics 25
2.4 Software as literature 29
2.5 Organic software 33
2.6 Software design as engineering 38
2.7 Putting the program in its place 42
2.8 User-centred design 48
2.9 The craft of program construction 50
2.10 Programmers' programming 51
2.11 Living with ambiguity 52
2.12 Summary 53
2.13 Chapter end material 55
Bibliography 55
3 The craft of software design 58
3.1 Introduction 58
3.2 Collaboration and imitation 58
3.3 Finishing 60
3.4 Tool building 60
3.5 Logbooks 61
3.6 The personal library 63
3.7 Chapter end material 65
Bibliography 65
4 Beginning programming in C++ 66
4.1 Introduction 66
4.2 The programming environment 67
4.3 Program shape, output, and the basic types 69
4.4 Variables and their types 74
4.5 Conditionals and compound statements 77
4.6 Loops 80
4.7 Random numbers, timing and an arithmetic game 82
4.8 Functions 85
4.9 Arrays and C-strings 88
4.10 Program example: A dice-rolling simulation 93
4.11 Bitwise operators 97
4.12 Pointers 99
4.13 Arrays of pointers and program arguments 104
4.14 Static and global variables 107
4.15 File input and output 108
4.16 Structures 112
4.17 Pointers to structures 115
4.18 Making the program more general 117
4.19 Loading structured data 119
4.20 Memory allocation 120
4.21 typedef 123
4.22 enum 123
4.23 Mechanisms that underlie the program 124
4.24 More on the C/C++ standard library 126
4.25 Chapter end material 129
Bibliography 129
5 Object-oriented programming in C++ 130
5.1 The motivation for object-oriented programming 130
Objects localize information 130
In an object-oriented language, existing solutions can be extended powerfully 132
5.2 Glossary of terms in object-oriented programming 134
Data structure 134
Abstract Data Type (ADT) 135
Class 136
Object 136
Method 137
Member function 137
Message 137
Base types and derived types 137
Inheritance 137
Polymorphism 137
5.3 C++ type definition, instantiation and using objects 138
Stack ADT example 138
Location ADT example 141
Vector ADT example 144
5.4 Overloading 147
Operator overloading 149
5.5 Building a String class 153
5.6 Derived types, inheritance and polymorphism 160
Locations and mountains example 160
Student marks example 166
5.7 Exceptions 175
5.8 Templates 178
5.9 Streams 181
5.10 C++ and information localization 186
5.11 Chapter end material 186
Bibliography 186
6 Program style and structure 187
6.1 Write fewer bugs! 187
6.2 Ten programming errors and how to avoid them 188
The invalid memory access error 189
The off-by-1 error 190
Incorrect initialization 191
Variable type errors 193
Loop errors 193
Incorrect code blocking 194
Returning a pointer or a reference to a local variable 195
Other problems with new and delete 196
Inadequate checking of input data 196
Different modules interpret shared items differently 198
6.3 Style for program clarity 199
File structure: a commentary introduction is essential 200
Explanatory structure: comment to reveal 200
Visual structure: make the program pretty 200
Verbal structure: make it possible to read the code aloud 201
Logical structure: don't be too clever 201
Replicated structure: kill the doppelgänger 202
6.4 Multifile program structure 202
6.5 A program that automatically generates a multifile structure 203
6.6 Chapter end material 207
Bibliography 207
7 Data structures 209
7.1 Structuring data 209
7.2 Memory usage and pointers 209
7.3 Linked lists 211
7.4 Data structures for text editing 212
Arrays 212
Arrays of pointers 212
Linked lists 213
7.5 Array/Linked list hybrids 218
Hash tables 219
7.6 Trees 220
7.7 Elementary abstract data types 225
ADT Ordered List 225
ADT stack 225
ADT queue 226
ADT priority queue 228
7.8 The ADT table – definition 231
7.9 Implementing the ADT table with an unordered array 232
7.10 Alternative implementations 235
7.11 Chapter end material 236
Bibliography 236
8 Algorithms 237
8.1 Introduction 237
8.2 Searching algorithms 237
Unordered linked list – sequential search 237
Unordered array – sequential search 238
Ordered array – binary search 238
8.3 Expressing the efficiency of an algorithm 239
8.4 Search algorithm analysis 240
Unordered linked list – sequential search 240
Unordered array – sequential search 240
Ordered array – binary search 241
8.5 Sorting algorithms and their efficiency 241
Selection sort 242
Insertion sort 242
Mergesort 244
Quicksort 245
Heapsort 247
8.6 Exploiting existing solutions 248
9 Design methodology 250
9.1 Introduction 250
9.2 Generic design methodologies 250
9.3 Reliable steps to a solution? – a sceptical interlude 251
Brainstorming 252
Sceptical design for designers 254
9.4 Design methodology for software 254
9.5 Design team organization 255
9.6 Documentation 256
9.7 Chapter end material 257
Bibliography 257
10 Understanding the problem 259
10.1 Problems 259
10.2 The problem statement 260
Examples 261
Some solutions 263
10.3 Researching the problem domain 263
Library research 263
Getting information from the network 265
10.4 Understanding users 265
10.5 Documenting a specification 268
10.6 Chapter end material 269
Bibliography 269
Users and user interfaces 269
11 Researching possible solutions 270
11.1 Introduction 270
11.2 Basic analysis 270
11.3 Experiment 271
Example 271
11.4 Prototyping and simulation 272
11.5 Notations and languages for developing designs 272
11.6 Dataflow diagrams 273
11.7 Specifying event-driven systems 274
11.8 Table-driven finite state machines 274
Example 277
11.9 Statecharts 278
Basic statechart syntax 279
11.10 Using statecharts – a clock radio example 281
Problem statement 281
Understanding the problem domain 281
Developing and specifying a solution 282
11.11 State sketches – using state diagrams to understand algorithms 283
Example: binary search 286
11.12 Chapter end material 289
Bibliography 289
12 Modularization 291
12.1 Introduction 291
12.2 Top-down design 292
12.3 Information hiding 293
12.4 A modularization example 294
12.5 Modularizing from a statechart 295
12.6 Object-oriented modularization 297
Example 297
12.7 Documenting the modularization 299
12.8 Chapter end material 302
Bibliography 302
13 Detailed design and implementation 303
13.1 Introduction 303
13.2 Implementing from a higher-level representation 303
13.3 Implementing with data structures and algorithms: rules of representation selection 306
13.4 The ADT table (again) 306
A specific implementation 307
Other scenarios and their implications 311
14 Testing 313
14.1 Introduction 313
14.2 Finding faults 313
14.3 Static analysis 315
Code inspection 316
14.4 Dynamic testing: (deterministic) black box test 317
Example 1 318
Example 2 318
14.5 Statistical black box testing 319
14.6 White box testing 320
Example 321
Difficulties with white box testing 321
14.7 Final words on testing for finding faults 322
14.8 Assessing performance 322
14.9 Testing to discover 323
14.10 Release 324
14.11 Chapter end material 324
Bibliography 324
15 Case study: Median filtering 325
15.1 Introduction to the case studies 325
15.2 Introduction to this chapter 325
15.3 Background 326
15.4 Why use median filtering? 326
15.5 The application 327
15.6 Approaching the problem 327
15.7 Rapid prototyping 328
15.8 Exploit existing solutions 331
15.9 Finishing 338
16 Multidimensional minimization – a case study in numerical methods 344
16.1 Numerical methods 344
16.2 The problem 346
Finding minima in 1D 346
Finding minima in multidimensions 346
16.3 Researching possible solutions 347
16.4 Nelder–Mead Simplex Optimization 349
16.5 Understanding the method with state sketches 350
16.6 Experiment-driven development 352
Basic working 352
Learning from experiments 353
Minimizing noisy functions 353
16.7 Program code 355
17 stable – designing a string table class 368
17.1 A perennial problem in data analysis 368
Collating one type of table into another type 368
Sifting and computing 368
17.2 Design approach 369
17.3 Rapid prototyping a framework 370
17.4 A quick fix 374
17.5 Reading and writing 374
17.6 Finding things 377
17.7 Matching the requirements 379
17.8 Generalizing stable to do more 381
17.9 Size flexibility 382
17.10 Yet more generality: using templates to store other types in stable 382
17.11 A final program before refactoring 382
17.12 Refactoring 393
Appendix: Comparison of algorithms for standard median filtering 413
Index 420
A 420
B 421
C 421
D 422
E 422
F 423
G 424
H 424
I 424
J 424
K 424
L 424
M 425
N 425
O 426
P 426
Q 427
R 427
S 427
T 428
U 429
V 429
W 429
Y 429