Introduction To Computer Science PDF Fall 2024

INTRODUCTION TO COMPUTER SCIENCE 252-0032, 252-0047, 252-0058 Document authors: Manuela Fischer and Felix Friedrich Department of Computer Science, ETH Zurich Fall 2024 1 ...

INTRODUCTION TO COMPUTER SCIENCE 252-0032, 252-0047, 252-0058 Document authors: Manuela Fischer and Felix Friedrich Department of Computer Science, ETH Zurich Fall 2024 1  7 Preface These lecture notes are written for the service courses on Computer Science at ETH Zürich. Authors are, with equal contribution, Manuela Fischer and Felix Friedrich, both from the Computer Science Department of ETH Zürich. The lecture notes are based on the lecture slides that have been compiled and streamlined over many years by the service teaching team, with contributions by (in alphabetical order) Carlos Cotrini, Manuela Fischer, Felix Friedrich, Bernd Gärtner, Hermann Lehner, Ralf Sasse and Malte Schwerhoff. The lecture notes follow closely what is taught in lectures and occasionally contain explana- tions or background material that could not be covered in such detail in class. Sections or paragraphs marked with an asterisk indicate material that has not or only very superficially been covered in class and is thus not relevant for an exam. We write these lecture notes in the hope that they are useful for students and appreciate feedback and bug reports a lot. Alternative Literature We recommend the book [Str13] from the inventor of C++, Bjarne Stroustrup (that is also available in German) as secondary literature for this course. If you want to dig deeper, the more recent book [Str22] is an interesting resource. Introduction 8 Section 1 Introduction In this introductory chapter, we briefly cover the origin and scope of computer science. As far as it is informally possible, we illustrate the concept of a Turing machine as the base of todays computers. And lastly, we discuss (high level) programming languages and tools for programming computers. Subsection 1.1 Computer Science What is Computer Science? Originally, computer science was a formal part of math- ematics and it was practiced already before computers, as we know them today, were at all imaginable. Today, computer science covers a wide area of topics from theory to practical applications. It is one of the distinguishing features of computer science that it is on the one hand concerned with fundamental scientific questions and that on the other hand it also is a science of engineering. A good characterization of the scope of computer science is the following. Computer Science is concerned with the automation of intellectual activities. What computer science is not. Computer science is generally, and particularly also in this course, not considered the same as computer literacy. In this course we will learn how to write a computer program is written and to under- stand what happens when a computer program is executed. While this course is not a software engineering course, we still want to teach some best practices in developing good computer programs. We will learn about systematic problem solving with algorithms and the programming language C++. Hence this course is (not only but also) a programming course. Subsection 1.2 Algorithms At the very heart of computer science is the topic of algorithms. An algorithm is A series of instructions to solve a problem step by step. Introduction 9 Its execution does not require any intelligence, but precision (even computers can do it) The name Algorithm is according to the name of the astronomer and mathematician Muhammed al-Chwarizmi, the author of an arabic computation textbook (around 825 AD). A cookbook recipe is an everyday example of an algorithm. Without extremely much knowledge about the science of cooking most people can follow a cookbook recipe. A recipe is broken down into steps that are reasonably comprehenisble for humans with a little bit of experience. Algorithms in computer science are similar but the steps are even simpler because computers are relatively stupid. The oldest non-trivial algorithm that can be executed with knowlegde in basic arithmetics is the Euclidean algorithm. It is described in the elements from Eukild, steming from the 3. century B.C. In its primary form, it treated the geometric problem of partitioning two lines a and b into equally sized pieces with maximal length. The algorithm is reasonably simple: We start with the two lines with length a and b. If the two lines are of equal length, a = b, then the lengths a and b already provide the partitioning of a and b into equally sized pieces with maximal length and the algorithm terminates. If the two lenghts are not equal, then the shorter piece, say b, is subtracted from the longer piece a yielding two new lengths a − b and b. The algorithm is restarted with lengths a − b > 0 and b > 0 (or, if a was shorter in the first place, with a > 0 and b − a > 0). If a and b are both integer lengths, the procedure described must terminate because in each step either a or b become shorter. And why is this procedure correct? Assume without loss of generality that a > b. If c|b (c divides b without rest) and c|(a − b) then certainly also c|a (because a can be written as a = (a − b) + b. But also the reverse is true: if c|b and c|a then also c|(a − b). This implies that any number that divides a and b in the beginning of the algorithm also divides the values a and b at the end of the algorithm, and vice versa. Particularly, also the maximum of these divisors divides the final values of a and b and thus must coincide with the value of a = b at the end of the algorithm. Here, while showing correctness and also when executing the algorithm, we have done some- thing that you might not have seen before. We have changed values of variables over time, a concept that is very much inherent to programming. We have therefore deliberately re- frained from using indices (or new names) for the variables a and b when they changed Introduction 10 values in steps of the algorithm. Now you have already seen a number of steps that usually are executed (arguing about the objective, the rationale, the correctness and termination of an algorith) when an algorithm is designed, even before anything has been implemented on a computer. Figure 1.1 comprises an illustration of the algorithm. The algorithm that we have described with relatively verbose informal language, can be written down a bit more concisely using pseudo-code, see Figure 1.2. a b a b a b a b a b a b Figure 1.1: The steps of Euklid’s algorithm (from left to right). The shorter length is subtracted from the longer length until both lengths coincide. Input: Two strictly positive integers a and b Output: Greatest common divisor of a and b while a ̸= b do // do the following steps as long as a ̸= b if a > b then // if a is greater (longer) a ← a − b // replace a by a − b else // if b is greater (longer) b ← b − a // replace b by b − a end end Result: a. Figure 1.2: Euklid’s algorithm Three Levels of Abstraction When discussing Euclid’s algorithm above, we have seen the essence of the algorithm, its core idea that is usually described on a high level of abstraction. In order to describe the algorithm, we have used pseudo-code on a semi- detailed level. This description should contain enough information and detail in order to communicate the algorithm unambiguously to humans and to argue about correctness, efficiency etc. Introduction 11 1. Core idea (abstract): the essence of any algorithm (“Eureka moment”) 2. Pseudo code (semi-detailed): made for humans (education, correctness and efficiency discussions, proofs 3. Implementation (very detailed): made for humans & computers (read- & executable, specific programming lan- guage, various implementations possible) For Euclid we have seen the core ide and pseudo code. The implementation is yet missing and will be covered next. In order to discuss the implementation we need a model of computation. We postulate a box-computer that, to make things easy at first, we consider driven by a human. The box computer comprises a set of boxes labeled with ascending integer numbers. We call these labels addresses and the boxes we also refer to as memory locations. Boxes (memory locations) can contain instructions or data. Instructions are very simple statements comprising memory operations, i.e. reading / writ- ing something from/into a box (memory location), arithmetics, i.e. subtracting or adding register values and jump operations that can be conditionally executed depending on a comparison operation. Memory 0 1 2 3 4 5 6 7 8 9 R > L? L−R R−L L = R? jump jump →L →R stop jump → to 0 → to 0 b a to 6 instructions data state while a ̸= b do if a > b then Left Right a←a−b else b←b−a end end result: a. Register Figure 1.3: Components of the box-computer. Memory boxes for instruction and data and register representing internal state that can be accessed immediately without going through the memory boxes. This computer is filled with instructions to execute Euklid’s algorithm. The high-level code of the program is only displayed in order to be able to make the link between the high level code and the instructions in the boxes. Memory locations 8 and 9 are labeled a and b and thus carry the values of variables a and b of our algorithm. Introduction 12 Here is how the box-computer works. Instructions are executed starting with the instruction in memory location 0. When an instruction has finished execution, the instruction in the next memory location is executed unless the instruction contains a jump, in which case the next instruction is located at the jump target. Here, the instructions in the memory cells carry the following meanings: Location Meaning 0 Copy the content of memory location 8 to the L register 1 Copy the content of memory location 9 to the R register 2 Compare the content of the L register to that of R. If equal, stop (result is in R, for instance.) 3 Compare the content of R and L registers. If R > L then jump to location 6. 4 Store the difference of L and R to memory location 8 5 Jump to location 0 6 Store the difference of R and L to memory location 8 7 Jump to location 0 Now, try it out! Fill some reasonably small values, like 12 and 8 to memory locations 8 and 9 and execute the steps as described. You will see that the algorithm (with you as the computer) finds the largest common divisor of the two numbers.1 Subsection 1.3 Computers A bright idea: Alan Turing’s Machine (1936) Alan Turing, a British mathematician, was interested in theoretical statements about what can be computed and what cannot be computed. In order to be able to rigorously answer questions around computability, he invented an abstract machine in 1936 that was later named after his inventor, Turing Machine. Alan Turing, http://en.wikipedia.org/wiki/ Alan_Turing Fixed program computer were already known since the 17th century. One example of such fixed program computers was the mechanical calculator by Blaise Pascal (1642). Even first general-purpose computing devices like the computing machine by Charles Babbage in the mid 18th century were already known. New and absolutely revolutionary about Turing’s machine was its universality because it could be freely programmed and modify its own memory (even including the program stored in that memory). This made the machine extremely powerful and it is still today used as 1 If you repeat this experiment with a large and a small number, such as 100 and 12, you will find that the algorithm repeats subtracting the small number (too) often. This is why an improved (more efficient, i.e. practically faster) version of the algorithm replaces the subtraction by the remainder of a division. Introduction 13 reference when it comes to the computability of problems. Turing proved that his machine would be capable of performing any mathematical computation if it was represented in the form of an algorithm. We call, for example, a machine Turing complete when it has the same expressive computing power as the construct that we will describe below. Turing’s idea was ingeniously simple. He postulated a (conceptually infinitely long) tape that can store symbols. There is a read-/write (RW) head that can read and write symbols. The RW head can additionally be moved along the tape. Controlling the head is taken over by a fixed program computer that is pre-programmed (constructed) such that it can interprete symbols as instructions and such that it can execute very simple operations on its internal state. The idea is illustrated on Figure 1.4. Sequence of symbols on a (conceptually unlimited) tape Instructions x Input Output RW head Fixed Program Computer ”read symbol!” Control Unit ”write symbol!” Internal State ”move left!” ”move right!” Figure 1.4: Universal Turing Machine, Schematic When you think of what you did when interpreting the instructions of our box-computer in the preceding paragraph, you should understand that you took over the role of the fixed- program computer. All you needed to do was reading and writing from and to the boxes (memory locations = tape positions), interpreting instructions and moving the program counter (the RW head position) around. While Alan Turing was not primarily interested in the real implementation of his machine, he laid the foundations for the computers as we have them today. Computers built from the principle of the turing Machine included the Z1,Z2 and Z3 computers invented by the German civil engineer Konrad Zuse in the years 1940-1941. The Z3 was the first working electromechaincally programmable fully automatic digital computer. 2. While the com- puters by Zuse used different places to store data and instructions, the later developed von Neumann architecture was the first to store both, data and instructions in the same memory area. Von-Neumann Architecture* The Von-Neumann architecture that we use in most computers today provides the following ingredients, see also Figure 1.5. Memory (RAM – Random Access Memory) for programs and data, cf. Figure 1.6. – Every memory cell has an address. 2 https://en.wikipedia.org/wiki/History_of_computing_hardware Introduction 14 – Memory locations store data using a number of bits. This determines the gran- ularity at which memory can be accessed. – We assume that the time to access a memory location is independent of its address. This is why it is called Random Access Memory. A processor (CPU) to process programs and data – The processor features a set of very simple operations (instructions). It executes instructions that are stored in machine language in memory. – It can read from and write to main memory. – It has ists own very fast memory (registers). I/O components to communicate with the world Central Processing Unit Control Unit Arithmetic/Logic Unit Bus RAM I/O Figure 1.5: Schematics of the main ingredients of the von Neumann architecture adr=0 adr=2 adr=4 adr=6 adr=8 adr=10 01001101 1101101 00010010 00000000 11101001 Figure 1.6: Memory locations have addresses and can contain a certain number of bits, varying on the implementation. The memory displayed here stores 8 bits per memory location. Computing speed While the first implemented computers featured computing speeds in the order of instructions per second, today’s computers are unbelievably fast. For example, the number of instructions per second (IPS), coarsely rounded, are 5 × 109 for a 30 Dollar raspberry PI computer, about 200−800×109 for standard Intel/AMD notebook processors and can go up to 1012 for a bit more specialized systems.3. Subsection 1.4 Programming 3 https://en.wikipedia.org/wiki/Instructions_per_second Introduction 15 Programming languages are used in order to communicate our intentions to computers (and other humans). The language that the computer can understand (machine language) is very primitive. As we have seen above with the box computer, simple operations have to be subdivided into (extremely) many single steps, Additionally, this simple language, the machine language, varies between computers. Figure 1.7 depicts the different levels and languages that we use when programming a computer. If the two lines are of equal length, a = b, then the lengths a and b already provide the par- Core idea ”GCD” titioning of a and b into equally sized pieces with maximal length and the algorithm termi- nates.... while a ̸= b do if a > b then Pseudo 245 chars/ a←a−b Code 46 words... end int gcd(int a, int b){ Impl. while (a != b){ 282 chars/ if (a > b){ (C++) 55 words b = a-b;... > 8f 02 00 00 22 00 2e 00 00 00 00 00 00 1f 00 00 00 00 00 00 00 9c 02 00 00 22 00 00 00 00 00 00 00 00 0f 00 00 00 00 Machine 1536 bytes/ c0 02 00 00 22 00 30 00 00 00 00 00 00 code – 1f 00 00 00 00 00 00 00 cd 02 00 00 22 00 00 00 00 00 00 00 00 0f 00 00 00 00.... Figure 1.7: There are variety of languages we use when solving a problem with a computer. The core idea is usually formulated in reasonably informal text. Pseudo-code makes it pos- sible to argue about and communicate possible implementations. Programming languages are used in order to implement the pseudo-code, targeted towards a variety of machines. A compiler translates the program written in a programming language to machine code that can be executed on the targeted machine. Why C++? The language used for learning programming in this course is C++. Why did we choose with language and why not a different one, such as Python or JavaScript? Is C++ not a comparably difficult to learn language? Well, first of all: we do not believe it is really harder to learn C++ than to learn any other programming language. C++ makes makes many decisions explicit; or rather, forces Introduction 16 programmers to make explicit choices which, will make it easier to later on switch to a “simpler” language. It is like getting a driver’s license for manual transmission systems, but driving automatic transmission later on. Moreover, C++ is very well suted for systems programming and for high performance com- puting since it enables/requires careful resource management (memory,...). Syntax and Semantics Like spoken languages, programs have to be formed according to certain rules. For spoken languages we distinguish betweeen syntax, that provides connection rules for elementary symbols (characters) and semantics, interpretation rules for such connected characters. Corresponding rules for a computer program are simpler but also more strict because com- puters are relatively stupid. Let us have a look at a (German) sentence and a piece of C++ code. Example 1.1 (Deutsch) Alleen sind nicht gefährlich, Rasen ist gefährlich! (Wikipedia: Mehrdeutigkeit) This text comprises words (contatenated characters) and punctuation marks that structure the text. The exclamation mark, for example, tells us that a sentence ends. The text, moreover, contains a piece of text in parentheses, an annotation, that has no immediate reference to the text. The text can be read and understood without reading the annotation. In this case the annotation only denotes where the text comes from. Note that you would be able to understand the text without punctuation marks. This is because humans are intelligent. Most syntactial errors we can cope with. Computers, or at least most compilers (translation tools for programs), are not that intelli- gent. The following text contains structuring elements similar to that of written language: Example 1.2 (C++) // computation int b = a * a; // b = a2 b = b * b; // b = a4 The C++ piece of code contains an annotations (comments that are marked by two leading slashes //) that help us humans to understand what the code is supposed to do. Such comments are ignored entirely by the compiler. The remaining text comprises statements that are separated by semicolons. Leaving away the semicolons, for example, will lead to a clueless compiler that refuses to accept the text. The compiler will refuse the code because it finds an incorrect syntax. So, generally speaking, syntax tells us when a text can be considered a C++ program at all. Is it gramatically correct? This can be (and is) checked by a computer (compiler) easily. Introduction 17 On the other hand, semantics describe the meaming of a program. What kind of algorithm is implemented by a program? This usually requires human understanding (although com- puters have become suprisingly good at interpreting and synthesizing programs meanwhile. The Syntax and semantics of C++is defined by the ISO/IEC standard 14822 (1998,2011,2014,... ) and provide the “law” of C++. It defines the grammar and meaning of C++ programs and is subject to extensions. Behavior of a program During compilation, a program can either be accepted by the compiler (in which case it is at least syntactically correct) or it can imply compiler errors, in which case the compiler refuses to translate the program and reports error messages. A compiler always detects any syntactical error. Some semantical errors can also be detected by compilers. During running time, a program that had previously been successfully translated by a compiler, can provide a correct result, it can create incorrect results, it can crash or it might even not terminate at all. Because there are so many possibilities and because it can take a while before a program shows (correct or incorrect) results, it is good that the compiler identifies some of the problems early on (during compilation). A C++ Program and its Components 18 Section 2 A C++ Program and its Components What is required in order to program a computer? In the very early days of computing people created programs by punching holes into cards that were then fed the machine that executed the program that was encoded as a pattern of holes in cards. Fortunately, all that has become much more comfortable nowadays. We use the computer itself to program the computer. An editor can be used to create, modify, edit, and store C++ program texts. A compiler is a program that translates a program text into machine language. The computer itself is used to execute the machine language programs. And, finally, the operating system is a collection of programs to organize operations on a computer such as file handling, execution of programs like the editor and compiler and the compiled program. In the following, we discuss the C++ language constructs with an example. We first show the whole program (in Code 2.1) and its behavior and then try to understand it. // Program: power8.cpp // Raise a number to the eighth power. #include int main() { // input std::cout > a; // computation int b = a * a; // b = a^2 b = b * b; // b = a^4 // output b * b, i.e., a^8 std::cout