Object-Oriented Programming Languages: Interpretation

✍ Scribed by Craig, Iain D

• Publisher: Springer London
• Year: 2007
• Tongue: English
• Leaves: 266
• Series: Undergraduate topics in computer science
• Category: Library

✦ Synopsis

1.1 Introduction Object-oriented programming has opened a great many perspectives on the concept of software and has been hailed as part of the solution to the so-called software crisis . It has given the possibility that software components can be constructedandreusedwithconsiderablymorecredibility.Therearenowmany case studies in which the reuse of object-oriented components has been made and analysed. Object-oriented programming relates the programming activity to that of modelling or simulation; objects are identi?ed by a correspondence with the objects found in the application area of the program and are used to model those domain operations. Object-oriented programming also opens the prospect of more ?exible software that is able to respond dynamically to the needs of the application at runtime. It is very easy to think that object-oriented programming can be performed in only one way. The prevalence of C++ and Java suggests that they are the onlywaytoapproachtheproblemofwhatanobject-orientedprogrammingl- guage should look like. There are many approaches to this way of programming andC++andJavaexemplifyjustoneofthesedi?erentapproaches.Indeed, the wayinwhichtheconceptoftheobjectisinterpreteddi?ersbetweenapproaches and between languages. The two main approaches found in object-oriented programming languages are, respectively, class-based and prototype-based languages. Class-based l- guages are exempli?ed by Smalltalk [34], C++ [75, 74] and Java [47]. This 2 1. Introduction approach is based upon the identi?cation of common properties of objects and their description in terms of a de?nitional structure called a class. The objects manipulated by class-based programs are the result of instantiating classes."

✦ Table of Contents

Undergraduate Topics in Computer Science......Page 2
Preface......Page 7
Contents......Page 11
List of Figures......Page 17
List of Tables......Page 20
Listings......Page 21
Part I. Getting Started......Page 26
A minimalist program......Page 27
Hello World......Page 28
Expressions and programs as calculators......Page 29
Arithmetic operations and priority order......Page 30
Mathematical functions......Page 32
Commenting Java programs......Page 34
Variables, assignments and type checking......Page 35
Variables for storing intermediate values......Page 36
Type checking for assignments and casting......Page 39
General mechanism for incrementation......Page 41
Pre-incrementation and post-incrementation......Page 42
A calculator for solving quadratic equations......Page 43
Computing does not mean displaying......Page 44
Keyboard input......Page 45
File redirections......Page 47
Bugs and the art of debugging......Page 48
Integrated development environments (IDEs)......Page 50
Note to instructors......Page 51
First set of exercises......Page 52
Instruction workflow......Page 54
Branching conditions: if ... else .........Page 55
Ternary operator for branching instructions: Predicate ? A : B......Page 57
Nested conditionals......Page 58
Relational and logical operators for comparisons......Page 59
Multiple choices: switch case......Page 62
Blocks of instructions......Page 63
Looping structures......Page 64
Loop statement: while......Page 65
Loop statement: do-while......Page 66
Loop statement: for......Page 68
Boolean arithmetic expressions......Page 69
Never ending programs......Page 70
Loops and program termination......Page 71
Certifying programs: Syntax, compilation and numerical bugs......Page 72
Parsing program arguments from the command line......Page 74
Exercises......Page 76
Advantages of programming functions......Page 79
Prototyping functions......Page 80
Examples of basic functions......Page 81
A more elaborate example: The iterative factorial function......Page 82
Functions with conditional statements......Page 83
Static (class) variables......Page 84
Local memory and function call stack......Page 86
Side-effects of functions: Changing the calling environment......Page 89
Function signatures and function overloading......Page 90
Recursion......Page 92
Revisiting the factorial function: A recursive function......Page 93
Fibonacci sequences......Page 94
Logarithmic mean......Page 95
Terminal recursion for program efficiency ......Page 96
Recursion and graphics ......Page 98
Halting problem: An undecidable task......Page 99
Exercises......Page 101
Declaring arrays......Page 104
Creating and initializing arrays......Page 105
Retrieving the size of arrays: length......Page 106
Index range of arrays and out-of-range exceptions......Page 107
The fundamental concept of array references......Page 108
Arrays as function arguments......Page 111
Multi-dimensional regular arrays......Page 114
Multi-dimensional ragged arrays ......Page 116
Arrays of strings and main function......Page 118
A basic application of arrays: Searching ......Page 120
Exercises......Page 122
Part II. Data-Structures & Algorithms......Page 125
Why do programmers need objects?......Page 126
Declaring classes and creating objects......Page 127
Constructor and object creation......Page 128
The common null object......Page 129
Static (class) functions with objects as arguments......Page 130
Objects and references......Page 132
Testing for object equality......Page 133
Array of objects......Page 134
Declaring and assigning String variables......Page 136
Equality test for strings: equals(String str)......Page 137
Comparing strings: Lexicographic order......Page 138
Revisiting a basic program skeleton......Page 141
Exercises......Page 142
Overview......Page 146
Searching information......Page 147
Sequential search......Page 148
Dynamically adding objects......Page 150
Dichotomy/bisection search......Page 152
Sorting arrays......Page 153
Sorting by selection: SelectionSort......Page 154
Extending selection sort to objects......Page 155
Complexity of selection sorting......Page 157
QuickSort: Recursive sorting......Page 158
Searching by hashing......Page 159
Exercises......Page 161
Illustrating the concepts of cells and lists......Page 163
Programming linked lists in Java......Page 164
Traversing linked lists......Page 165
Linked lists storing +String+ elements......Page 166
Length of a linked list......Page 167
Dynamic insertion: Adding an element to the list......Page 168
Removing an element from a linked list......Page 169
Recursion on linked lists......Page 171
Copying linked lists......Page 173
Sorting linked lists......Page 174
Merging ordered lists......Page 175
Recursive sorting of lists......Page 176
Application of linked lists: Hashing......Page 178
Open address hashing......Page 180
Solving collisions with linked lists......Page 182
Exercises......Page 183
Queues as abstract data-structures: Interfaces......Page 186
Basic queue implementation: Static functions......Page 187
An application of queues: Set enumeration......Page 189
Priority queues and heaps......Page 190
Adding an element......Page 192
Removing the topmost element......Page 194
Object-oriented data-structures: Methods......Page 195
Object oriented priority queues......Page 199
Object-oriented lists......Page 200
Stacks: Last in first out (LIFO) abstract data-structures......Page 202
Stack interface and an array implementation......Page 203
Implementing generic stacks with linked lists......Page 204
Exercises......Page 206
Introduction......Page 208
Filling a knapsack......Page 209
Backtracking illustrated: The eight queens puzzle......Page 215
An approximate solution to the 0-1 knapsack problem......Page 218
A greedy algorithm for solving set cover problems......Page 222
Dynamic programming: Optimal solution for the 0-1 knapsack problem......Page 228
Optimization paradigms: Overview of complexity analysis......Page 231
Exercices......Page 233
The digital world......Page 236
Nature of computing?......Page 238
Birth of algorithms and computers......Page 239
Computer science in the 21st century......Page 240
Part III. Exam Review......Page 241
Exam & Solution......Page 242
Bibliography......Page 262
Index......Page 263