دانلود کتاب Computer Science: An Interdisciplinary Approach

فهرست مطالب :

Cover......Page 1
Title......Page 4
Copyright......Page 5
Contents......Page 7
Programs......Page 9
Circuits......Page 12
Preface......Page 14
Coverage......Page 15
Use in the Curriculum......Page 16
Prerequisites......Page 17
Goals......Page 18
Booksite......Page 19
Acknowledgments......Page 20
1—Elements of Programming......Page 22
Programming in Java......Page 23
Input and output......Page 28
Q&A......Page 30
Exercises......Page 33
1.2 Built-in Types of Data......Page 35
Terminology......Page 36
Characters and strings......Page 40
Integers......Page 43
Floating-point numbers......Page 45
Booleans......Page 47
Comparisons......Page 48
Library methods and APIs......Page 50
Type conversion......Page 53
Summary......Page 56
Q&A (Strings)......Page 58
Q&A (Integers)......Page 59
Q&A (Floating-Point Numbers)......Page 61
Q&A (Variables and Expressions)......Page 63
Exercises......Page 65
Creative Exercises......Page 68
If statements......Page 71
While loops......Page 74
For loops......Page 80
Nesting......Page 83
Applications......Page 85
Other conditional and loop constructs......Page 95
Infinite loops......Page 97
Summary......Page 98
Q&A......Page 99
Exercises......Page 102
Creative Exercises......Page 107
1.4 Arrays......Page 111
Arrays in Java......Page 112
Coupon collector......Page 122
Sieve of Eratosthenes......Page 124
Two-dimensional arrays......Page 127
Example: self-avoiding random walks......Page 133
Summary......Page 136
Q&A......Page 137
Exercises......Page 139
Creative Exercises......Page 142
1.5 Input and Output......Page 147
Bird’s-eye view......Page 148
Standard output......Page 150
Standard input......Page 153
Redirection and piping......Page 160
Standard drawing......Page 165
Standard audio......Page 176
Summary......Page 180
Q&A......Page 181
Exercises......Page 183
Creative Exercises......Page 188
1.6 Case Study: Random Web Surfer......Page 191
Input format......Page 192
Transition matrix......Page 193
Simulation......Page 195
Mixing a Markov chain......Page 200
Lessons......Page 205
Exercises......Page 207
Creative Exercises......Page 209
2—Functions and Modules......Page 212
2.1 Defining Functions......Page 213
Static methods......Page 214
Implementing mathematical functions......Page 223
Using static methods to organize code......Page 226
Passing arguments and returning values......Page 228
Example: superposition of sound waves......Page 232
Q&A......Page 237
Exercises......Page 239
Creative Exercises......Page 243
2.2 Libraries and Clients......Page 247
Using static methods in other programs......Page 248
Libraries......Page 251
Random numbers......Page 253
Input and output for arrays......Page 258
Iterated function systems......Page 260
Statistics......Page 265
Modular programming......Page 272
Q&A......Page 276
Exercises......Page 277
Creative Exercises......Page 280
2.3 Recursion......Page 283
Your first recursive program......Page 285
Mathematical induction......Page 287
Euclid’s algorithm......Page 288
Towers of Hanoi......Page 289
Function-call trees......Page 290
Exponential time......Page 293
Gray codes......Page 294
Recursive graphics......Page 297
Brownian bridge......Page 299
Pitfalls of recursion......Page 302
Dynamic programming......Page 305
Perspective......Page 310
Q&A......Page 311
Exercises......Page 312
Creative Exercises......Page 315
2.4 Case Study: Percolation......Page 321
Percolation......Page 322
Basic scaffolding......Page 323
Testing......Page 326
Estimating probabilities......Page 329
Recursive solution for percolation......Page 333
Adaptive plot......Page 335
Lessons......Page 339
Q&A......Page 342
Exercises......Page 343
Creative Exercises......Page 345
3—Object-Oriented Programming......Page 350
3.1 Using Data Types......Page 351
Basic definitions......Page 352
String-processing application: genomics......Page 357
Color.......Page 362
Digital image processing......Page 367
Input and output revisited......Page 374
Properties of reference types......Page 383
Q&A......Page 390
Exercises......Page 394
Creative Exercises......Page 398
3.2 Creating Data Types......Page 403
Basic elements of a data type......Page 404
Stopwatch......Page 411
Histogram......Page 413
Turtle graphics......Page 415
Complex numbers......Page 423
Mandelbrot set......Page 427
Commercial data processing......Page 431
Q&A......Page 436
Exercises......Page 439
Creative Exercises......Page 444
3.3 Designing Data Types......Page 449
Designing APIs......Page 450
Encapsulation......Page 453
Immutability......Page 460
Example: spatial vectors......Page 463
Interface inheritance (subtyping)......Page 467
Implementation inheritance (subclassing)......Page 473
Application: data mining......Page 479
Design by contract......Page 486
Q&A......Page 489
Exercises......Page 492
Data-Type Design Exercises......Page 495
Creative Exercises......Page 497
3.4 Case Study: N-Body Simulation......Page 499
N-body simulation......Page 500
Q&A......Page 510
Exercises......Page 511
Creative Exercises......Page 512
4—Algorithms and Data Structures......Page 514
4.1 Performance......Page 515
Observations......Page 516
Hypotheses......Page 517
Order-of-growth classifications......Page 524
Predictions......Page 528
Caveats......Page 530
Performance guarantees......Page 533
Memory......Page 534
Perspective......Page 539
Q&A......Page 540
Exercises......Page 543
Creative Exercises......Page 550
4.2 Sorting and Searching......Page 553
Binary search......Page 554
Insertion sort......Page 564
Mergesort......Page 571
Application: frequency counts......Page 576
Lessons......Page 579
Q&A......Page 580
Exercises......Page 581
Creative Exercises......Page 584
4.3 Stacks and Queues......Page 587
Pushdown stacks......Page 588
Array implementation......Page 589
Linked lists......Page 592
Resizing arrays......Page 599
Parameterized data types......Page 603
Stack applications......Page 607
FIFO queues......Page 613
Queue applications......Page 618
Iterable collections......Page 622
Resource allocation......Page 627
Q&A......Page 630
Exercises......Page 633
Linked-List Exercises......Page 637
Creative Exercises......Page 639
4.4 Symbol Tables......Page 645
API......Page 646
Symbol-table clients......Page 649
Elementary symbol-table implementations......Page 656
Hash tables......Page 657
Binary search trees......Page 661
Performance characteristics of BSTs......Page 668
Traversing a BST......Page 670
Ordered symbol table operations......Page 672
Set data type......Page 673
Perspective......Page 675
Q&A......Page 676
Exercises......Page 677
Binary Tree Exercises......Page 682
Creative Exercises......Page 684
4.5 Case Study: Small-World Phenomenon......Page 691
Graphs......Page 692
Graph data type......Page 696
Graph client example......Page 700
Shortest paths in graphs......Page 704
Small-world graphs......Page 714
Lessons......Page 721
Q&A......Page 724
Exercises......Page 726
Creative Exercises......Page 730
5—Theory of Computing......Page 736
Basic definitions......Page 739
Regular languages......Page 744
Generalized REs......Page 751
Applications......Page 753
Abstract machines......Page 758
Deterministic finite-state automata......Page 759
Java implementation of DFAs.......Page 762
Nondeterminism......Page 765
Kleene’s theorem......Page 769
Applications of Kleene’s theorem......Page 774
Summary......Page 777
Q&A......Page 778
Exercises......Page 780
Creative Exercises......Page 783
Turing machine model......Page 787
Universal virtual Turing machine......Page 795
Q&A......Page 801
Exercises......Page 802
Creative Exercises......Page 805
Algorithms......Page 807
Programs that process programs......Page 809
Church–Turing Thesis......Page 811
Variations on the TM model......Page 812
Universal models......Page 815
Q&A......Page 819
Creative Exercises......Page 820
Context: Hilbert’s program......Page 827
Warmup: liar’s paradox......Page 828
The halting problem......Page 829
Reduction......Page 832
More examples of unsolvable problems......Page 834
Implications......Page 837
Q&A......Page 839
Exercises......Page 840
Creative Exercises......Page 841
5.5 Intractability......Page 843
Overview......Page 844
Examples......Page 847
Satisfiability......Page 851
Search problems......Page 854
The main question......Page 861
Polynomial-time reductions......Page 862
Proving problems to be NP-complete......Page 865
Coping with NP-completeness......Page 871
Q&A......Page 879
Exercises......Page 882
Creative Exercises......Page 889
6—A Computing Machine......Page 894
6.1 Representing Information......Page 895
Binary and Hexadecimal......Page 896
Parsing and string representations......Page 901
Integer arithmetic......Page 905
Negative numbers......Page 907
Real numbers......Page 909
Java code for manipulating bits......Page 912
Characters......Page 915
Summary......Page 917
Q&A......Page 918
Exercises......Page 922
Creative Exercises......Page 926
6.2 TOY Machine......Page 927
Brief historical note......Page 928
TOY components......Page 929
Fetch–increment–execute cycle......Page 931
Instructions......Page 932
Your first TOY program......Page 935
Operating the machine......Page 937
Conditionals and loops......Page 939
Stored-program computing......Page 943
Von Neumann machines......Page 945
Q&A......Page 947
Exercises......Page 948
6.3 Machine-Language Programming......Page 951
Functions......Page 952
Standard output......Page 955
Standard input......Page 957
Arrays......Page 959
Linked structures......Page 963
Why learn machine-language programming?......Page 966
Q&A......Page 968
Exercises......Page 969
Creative Exercises......Page 976
6.4 TOY Virtual Machine......Page 979
Booting and dumping......Page 980
A note of caution......Page 982
Programs that process programs......Page 985
TOY in Java......Page 987
The TOY family of imaginary computers......Page 993
Q&A......Page 999
Exercises......Page 1000
Creative Exercises......Page 1001
7—Building a Computing Device......Page 1006
7.1 Boolean Logic......Page 1007
Boolean functions......Page 1008
An application......Page 1013
Boolean functions of three or more variables......Page 1015
Exercises......Page 1019
Creative Exercises......Page 1021
7.2 Basic Circuit Model......Page 1023
Wires......Page 1024
Controlled switches......Page 1026
Circuits......Page 1027
Logical design and the real world......Page 1029
Q&A......Page 1031
Exercises......Page 1032
7.3 Combinational Circuits......Page 1033
Gates......Page 1034
Building a circuit from gates......Page 1040
Decoders, demuxes, and muxes......Page 1042
Sum-of-products circuits......Page 1045
Adder......Page 1049
Arithmetic logic unit (ALU)......Page 1052
Modules and buses......Page 1055
Layers of abstraction......Page 1058
Q&A......Page 1062
Exercises......Page 1063
Creative Exercises......Page 1066
Elementary feedback circuits......Page 1069
Flip-flops......Page 1070
Registers......Page 1072
Memory......Page 1075
Clock......Page 1079
Summary......Page 1083
Q&A......Page 1085
Exercises......Page 1086
Creative Exercises......Page 1088
TOY-8......Page 1091
Warmup......Page 1094
TOY-8 CPU organization and connections......Page 1097
Control......Page 1101
Example: A TOY-8 program......Page 1103
Perspective......Page 1105
Q&A......Page 1109
Exercises......Page 1110
Creative Exercises......Page 1111
Context......Page 1114
B......Page 1118
C......Page 1119
G......Page 1120
I......Page 1121
M......Page 1122
O......Page 1123
P......Page 1124
T......Page 1125
W......Page 1126
A......Page 1128
B......Page 1130
C......Page 1131
D......Page 1134
E......Page 1136
F......Page 1137
H......Page 1139
I......Page 1140
L......Page 1142
M......Page 1143
N......Page 1145
O......Page 1146
P......Page 1147
R......Page 1149
S......Page 1151
T......Page 1154
V......Page 1156
Z......Page 1157
Math......Page 1159
System.out/StdOut/Out......Page 1160
StdIn/In......Page 1161
StdDraw......Page 1162
Picture......Page 1163
StdStats......Page 1164
SET......Page 1165
Graph......Page 1166