Table of Contents
Preface................................................................................................................. vii
1. Introduction to Computing................................................................................ 1
1.1. Introduction............................................................................................ 2
1.1.1 Early Computing Devices ........................................................ 3
1.1.2 Modern Computers.................................................................. 4
1.2 How do computers work?...................................................................... 4
1.2.1 Electronic circuits and hardware............................................. 4
1.2.2 Communicating with a Machine.............................................. 5
1.3 Algorithms............................................................................................... 7
1.4 Summary................................................................................................. 7
1.5 Exercises.................................................................................................. 8
1.6 Projects.................................................................................................... 8
2 Introduction to Computation.......................................................................... 11
2.1 Introduction............................................................................................ 12
2.2 Numbering Systems................................................................................ 12
2.2.1 Positional Numbering Systems................................................ 12
2.2.2 Converting from Binary to Decimal......................................... 14
2.2.3 Converting from Decimal to Binary......................................... 15
2.2.4 Hexadecimal Numbers............................................................. 16
2.2.5 Converting from Hexadecimal to Decimal.............................. 17
2.2.6 Converting from Decimal to Hexadecimal.............................. 18
2.2.7 Converting Between any Base and Base Ten.......................... 19
2.3 Introduction To C++............................................................................... 19
2.3.1 The program that does nothing.............................................. 19
2.3.2 Output and the endl................................................................ 21
2.3.3 Input and variable declaration................................................ 22
2.3.4 Code Tracing............................................................................. 26
2.3.5 Assignments and arithmetic expressions............................... 27
2.4 Algorithms............................................................................................... 29
2.5 Three Control Structures........................................................................ 32
2.5.1 Combining structures............................................................... 33
2.6 Summary................................................................................................. 38
2.7 Exercises.................................................................................................. 38
2.8 Projects.................................................................................................... 41
2.9 Solutions to Activities............................................................................ 42
3
3. The Art of Problem Solving................................................................................ 47
3.1. Introduction to Problem Solving................................................................ 47
3.1.1 Heuristic Solutions to problems.............................................. 48
3.1.2 Algorithmic Solutions to problems......................................... 48
3.2 The 5 steps to problem solving............................................................. 49
3.2.1 Prime Numbers......................................................................... 52
3.3 C++ Sequence, Selection, and Loop Structures..................................... 55
3.4 Problem Solving Strategies..................................................................... 60
3.4.1 Brute Force............................................................................... 60
3.4.2 Divide and Conquer................................................................. 61
3.5 C++ Logical Operators and Truth Tables............................................... 62
3.6 Solving Problems.................................................................................... 66
3.6.1 Sequential Search..................................................................... 67
3.6.2 Selection Sort............................................................................ 68
3.7 Exercises.................................................................................................. 71
3.8 Projects.................................................................................................... 73
3.9 Solutions to Activities............................................................................ 75
4 Data and Data storage .................................................................................... 79
4.1 Types of data.......................................................................................... 79
4.2 Data hierarchy........................................................................................ 80
4.3 Capacity – How much data do we store?.............................................. 81
4.4 Data in C++.............................................................................................. 82
4.4.1 C++ Arrays................................................................................. 83
4.4.2 C++ for-loops ........................................................................... 87
4.4.3 C++ Multidimensional Arrays.................................................. 88
4.4.4 C++ Sequential Search and Selection Sort Revisited.............. 92
4.5 Types of storage devices........................................................................ 93
4.5.1 Internal storage........................................................................ 95
4.5.2 External storage ....................................................................... 96
4.6 Representing Data ................................................................................. 98
4.6.1 Storing Characters in Computers............................................ 98
4.6.2 Integers .................................................................................... 98
4.6.3 Floating-Point Numbers........................................................... 106
4.7 Exercises.................................................................................................. 112
4.8 Projects.................................................................................................... 114
4.9 Solutions to Activities............................................................................ 116
5 Computer Architecture and Assembly Language Programming................... 123
5.1 Introduction to Computer Architecture................................................ 123
5.2 The Central Processing Unit................................................................... 124
5.2.1 The Machine Cycle................................................................... 126
5.2.2 Processor Design and Registers............................................... 126
5.3 Instruction Sets....................................................................................... 129
5.3.1 A Simple ISA.............................................................................. 130
5.3.2 Memory Access......................................................................... 131
5.3.3 Program Execution Example.................................................... 136
5.4 Assembly language................................................................................. 141
5.4.1 Assembly Language Programming........................................... 142
5.5 C++ Strings.............................................................................................. 144
5.6 Controllers and External Devices........................................................... 146
5.7 Exercises.................................................................................................. 148
5.8 Projects.................................................................................................... 151
5.9 Solutions to Activities ........................................................................... 153
6 The Notion of Computation............................................................................. 159
6.1 Introduction............................................................................................ 160
6.2 Sets and Relations.................................................................................. 160
6.3 C++ struct ............................................................................................... 163
6.4 Finite State Machines............................................................................. 166
6.5 Context Free Languages......................................................................... 180
6.6 C++ Libraries and External Files............................................................. 183
6.6.1 C++ Library Functions............................................................... 184
6.6.2 C++External Files...................................................................... 186
6.7 Exercises.................................................................................................. 191
6.8 Projects.................................................................................................... 195
6.9 Solutions to Activities............................................................................ 195
7 Languages: Talking with a Machine................................................................ 199
7.1 Types of Languages................................................................................. 200
7.2 Connecting Hardware to Software........................................................ 200
7.3 The Operating System............................................................................ 201
7.4 Programming Languages Syntax and Semantics................................... 202
7.4.1 Compilers.................................................................................. 203
7.5 C++ Functions......................................................................................... 204
7.5.1 Local data and scope................................................................ 206
7.5.2 static variables.......................................................................... 208
7.5.3 Arguments and parameters..................................................... 208
7.5.4 return statements.................................................................... 209
7.5.5 Reference parameters.............................................................. 210
7.6 Modules in a Compiler........................................................................... 212
7.6.1 The scanner.............................................................................. 213
7.6.2 The symbol table...................................................................... 215
7.6.3 The parser................................................................................. 218
7.6.4 The code generator.................................................................. 224
7.7 More about C++ Functions*.................................................................. 226
7.7.1 Mathematical functions........................................................... 227
7.7.2 Top-down design and function stubs..................................... 229
7.8 Summary................................................................................................. 232
7.9 Exercises.................................................................................................. 234
7.10 Projects.................................................................................................... 237
7.11 Solutions to Activities............................................................................ 239
8 Appendix A: ASCII Table.................................................................................. 243
9 Appendix B: Glossary.......................................................................................