Foundations of Computer Science

Cover......Page 1
Contents......Page 7
Preface......Page 13
Chapter 1: Introduction......Page 21
1.1 Turing Model......Page 22
1.2 Von Neumann Model......Page 24
1.3 Computer Components......Page 26
1.4 History......Page 29
1.5 Computer Science as a Discipline......Page 31
1.6 Outline of the Course......Page 32
1.7 End-Chapter Materials......Page 33
1.8 Practice Set......Page 34
Chapter 2: Number Systems......Page 35
2.2 Positional Number Systems......Page 36
2.3 Nonpositional Number Systems......Page 51
2.4 End-Chapter Materials......Page 52
2.5 Practice Set......Page 54
Chapter 3: Data Storage......Page 59
3.1 Data Types......Page 60
3.2 Storing Numbers......Page 62
3.3 Storing Text......Page 80
3.4 Storing Audio......Page 81
3.5 Storing Images......Page 83
3.6 Storing Video......Page 85
3.7 Chapter Materials......Page 86
3.8 Practice Set......Page 88
Chapter 4: Operations on Data......Page 93
4.1 Logic Operations......Page 94
4.2 Shift Operations......Page 99
4.3 Arithmetic Operations......Page 102
4.4 End-Chapter Materials......Page 106
4.5 Practice Set......Page 107
Chapter 5: Computer Organization......Page 111
5.2 Central Processing Unit......Page 112
5.3 Main Memory......Page 114
5.4 Input/Output Subsystem......Page 117
5.5 Subsystem Interconnection......Page 124
5.6 Program Execution......Page 129
5.7 Different Architectures......Page 133
5.8 A Simple Computer......Page 137
5.9 End-Chapter Materials......Page 146
5.10 Practice Set......Page 150
Chapter 6: Computer Networks and Internet......Page 153
6.1 Overview......Page 154
6.2 Application Layer......Page 163
6.3 Transport Layer......Page 176
6.4 Network Layer......Page 179
6.5 Data-Link Layer......Page 186
6.6 Physical Layer......Page 194
6.7 Transmission Media......Page 197
6.8 End-Chapter Materials......Page 200
6.9 Practice Set......Page 203
Chapter 7: Operating Systems......Page 207
7.1 Introduction......Page 208
7.2 Evolution......Page 209
7.3 Components......Page 211
7.4 A Survey of Operating Systems......Page 223
7.5 End-Chapter Materials......Page 227
7.6 Practice Set......Page 229
Chapter 8: Algorithms......Page 233
8.1 Concept......Page 234
8.2 Three Constructs......Page 238
8.3 Algorithm Representation......Page 239
8.4 A More Formal Definition......Page 243
8.5 Basic Algorithms......Page 244
8.6 Subalgorithms......Page 253
8.7 Recursion......Page 254
8.8 End-Chapter Materials......Page 256
8.9 Practice Set......Page 258
Chapter 9: Programming Languages......Page 263
9.1 Evolution......Page 264
9.2 Translation......Page 266
9.3 Programming Paradigms......Page 268
9.4 Common Concepts......Page 277
9.5 End-Chapter Materials......Page 287
9.6 Practice Set......Page 289
Chapter 10: Software Engineering......Page 293
10.1 The Software Lifecycle......Page 294
10.2 Analysis Phase......Page 296
10.3 Design Phase......Page 299
10.4 Implementation Phase......Page 300
10.5 Testing Phase......Page 303
10.6 Documentation......Page 305
10.7 End-Chapter Materials......Page 306
10.8 Practice Set......Page 308
Chapter 11: Data Structure......Page 311
11.1 Arrays......Page 312
11.2 Records......Page 318
11.3 Linked Lists......Page 321
11.4 End-Chapter Materials......Page 334
11.5 Practice Set......Page 335
Chapter 12: Abstract Data Types......Page 337
12.1 Background......Page 338
12.2 Stacks......Page 340
12.3 Queues......Page 346
12.4 General Linear Lists......Page 351
12.5 Trees......Page 357
12.6 Graphs......Page 363
12.7 End-Chapter Materials......Page 364
12.8 Practice Set......Page 366
Chapter 13: File Structure......Page 369
13.2 Sequential Files......Page 370
13.3 Indexed Files......Page 374
13.4 Hashed Files......Page 375
13.5 Directories......Page 380
13.6 Text versus Binary......Page 382
13.7 End-Chapter Materials......Page 383
13.8 Practice Set......Page 384
Chapter 14: Databases......Page 389
14.1 Introduction......Page 390
14.2 Database Architecture......Page 392
14.3 Database Models......Page 393
14.4 The Relational Database Model......Page 394
14.5 Database Design......Page 401
14.6 Other Database Models......Page 405
14.7 End-Chapter Materials......Page 406
14.8 Practice Set......Page 408
Chapter 15: Data Compression......Page 411
15.2 Lossless Compression Methods......Page 412
15.3 Lossy Compression Methods......Page 420
15.4 End-Chapter Materials......Page 426
15.5 Practice Set......Page 427
Chapter 16: Security......Page 431
16.1 Introduction......Page 432
16.2 Confidentiality......Page 435
16.3 Other Aspects of Security......Page 448
16.4 Firewalls......Page 462
16.5 End-Chapter Materials......Page 465
16.6 Practice Set......Page 467
Chapter 17: Theory of Computation......Page 471
17.1 Simple Language......Page 472
17.2 The Turing Machine......Page 476
17.3 Godel Numbers......Page 483
17.4 The Halting Problem......Page 484
17.5 The Complexity of Problems......Page 487
17.6 End-Chapter Materials......Page 489
17.7 Practice Set......Page 490
Chapter 18: Artificial Intelligence......Page 493
18.1 Introduction......Page 494
18.2 Knowledge Representation......Page 495
18.3 Expert Systems......Page 505
18.4 Perception......Page 507
18.5 Searching......Page 514
18.6 Neural Networks......Page 518
18.7 End-Chapter Materials......Page 521
18.8 Practice Set......Page 523
Chapter 19: Introduction to Social Media......Page 527
19.2 Facebook......Page 528
19.3 Twitter......Page 534
19.4 End-Chapter Materials......Page 541
19.5 Practice Set......Page 542
Chapter 20: Social and Ethical Issues......Page 545
20.1 Ethical Principles......Page 546
20.2 Intellectual Property......Page 547
20.4 Computer Crimes......Page 548
20.6 End-Chapter Materials......Page 550
20.7 Practice Set......Page 551
Appendix A: Unicode......Page 553
Appendix B: Unified Modeling Language (UML)......Page 559
Appendix C: Pseudocode......Page 573
Appendix D: Structure Chart......Page 577
Appendix E: Boolean Algebra and Logic Circuits......Page 583
Appendix F: Examples of Programs in C, C++, and Java......Page 601
Appendix G: Mathematical Review......Page 611
Appendix H: Error Detection and Correction......Page 621
Appendix I: Addition and Subtraction for Sign-and-Magnitude Integers......Page 637
Appendix J: Addition and Subtraction for Reals......Page 641
Acronyms......Page 645
Glossary......Page 649
Index......Page 689