CHAPTER 1

Introduction to Computer Science

1.1 Computer Science

1.2 Computer Systems

1.3 Python Programming Language

1.4 Computational Thinking

Chapter Summary

IN THIS INTRODUCTORY CHAPTER, we provide the context for the book and introduce the key concepts and terminology that we will be using throughout. The starting point for our discussion are several questions. What is computer science? What do computer scientists and computer application developers do? And what tools do they use?

Computers, or more generally computer systems, form one set of tools. We discuss the different components of a computer system including the hardware, the operating system, the network and the Internet, and the programming language used to write programs. We specifically provide some background on the Python programming language, the language used in this book.

The other set of tools are the reasoning skills, grounded in logic and mathematics, required to develop a computer application. We introduce the idea of computational thinking and illustrate how it is used in the process of developing a small web search application.

The foundational concepts and terminology introduce in this chapter are independent of the Python programming language. They are relevant to any type of application development regardless of the hardware or software platform or programming language used.

1.1 Computer Science

This textbook is an introduction to programming. It is also an introduction to Python, the programming language. But most of all, it is an introduction to computing and how to look at the world from a computer science perspective. To understand this perspective and define what computer science is, let's start by looking at what computing professionals do.

What Do Computing Professionals Do?

One answer is to say: they write programs. It is true that many computing professionals do write programs. But saying that they write programs is like saying that screenwriters (i.e., writers of screenplays for movies or television series) write text. From our experience watching movies, we know better: screenwriters invent a world and plots in it to create stories that answer the movie watcher's need to understand the nature of the human condition. Well, maybe not all screenwriters.

So let's try again to define what computing professionals do. Many actually do not write programs. Even among those who do, what they are really doing is developing computer applications that address a need in some activity we humans do. Such computing professionals are often called computer application developers or simply developers. Some developers even work on applications, like computer games, that are not that different from the imaginary worlds, intricate plots, and stories that screenwriters create.

Not all developers develop computer games. Some create financial tools for investment bankers, and others create visualization tools for doctors (see Table 1.1 for other examples.)

What about the computing professionals who are not developers? What do they do? Some talk to clients and elicit requirements for computer applications that clients need. Others are managers who oversee an application development team. Some computing professionals support their clients with newly installed software and others keep the software up to date. Many computing professionals administer networks, web servers, or database servers. Artistic computing professionals design the interfaces that clients use to interact with an application. Some, such as the author of this textbook, like to teach computing, and others offer information technology (IT) consulting services. Finally, more than a few computing professionals have become entrepreneurs and started new software businesses, many of which have become household names.

Table 1.1 The range of computers science. Listed are examples of human activities and, for each activity, a software product built by computer application developers that supports performing the activity.

Regardless of the ultimate role they play in the world of computing, all computing professionals understand the basic principles of computing and how computer applications are developed and how they work. Therefore, the training of a computing professional always starts with the mastery of a programming language and the software development process. In order to describe this process in general terms, we need to use slightly more abstract terminology.

Models, Algorithms, and Programs

To create a computer application that addresses a need in some area of human activity, developers invent a model that represents the “real-world” environment in which the activity occurs. The model is an abstract (imaginary) representation of the environment and is described using the language of logic and mathematics. The model can represent the objects in a computer game, stock market indexes, an organ in the human body, or the seats on an airplane.

Developers also invent algorithms that operate in the model and that create, transform, and/or present information. An algorithm is a sequence of instructions, not unlike a cooking recipe. Each instruction manipulates information in a very specific and well-defined way, and the execution of the algorithm instructions achieves a desired goal. For example, an algorithm could compute collisions between objects in a computer game or the available economy seats on an airplane.

The full benefit of developing an algorithm is achieved with the automation of the execution of the algorithm. After inventing a model and an algorithm, developers implement the algorithm as a computer program that can be executed on a computer system. While an algorithm and a program are both descriptions of step-by-step instructions of how to achieve a result, an algorithm is described using a language that we understand but that cannot be executed by a computer system, and a program is described using a language that we understand and that can be executed on a computer system.

At the end of this chapter, in Section 1.4, we will take up a sample task and go through the steps of developing a model and an algorithm implementing the task.

Tools of the Trade

We already hinted at a few of the tools that developers use when working on computer applications. At a fundamental level, developers use logic and mathematics to develop models and algorithms. Over the past half century or so, computer scientists have developed a vast body of knowledge—grounded in logic and mathematics—on the theoretical foundations of information and computation. Developers apply this knowledge in their work. Much of the training in computer science consists of mastering this knowledge, and this textbook is the first step in that training.

The other set of tools developers use are computers, of course, or more generally computer systems. They include the hardware, the network, the operating systems, and also the programming languages and programming language tools. We describe all these systems in more detail in Section 1.2. While the theoretical foundations often transcend changes in technology, computer system tools are constantly evolving. Faster hardware, improved operating systems, and new programming languages are being created almost daily to handle the applications of tomorrow.

What Is Computer Science?

We have described what application developers do and also the tools that they use. What then is computer science? How does it relate to computer application development?

While most computing professionals develop applications for users outside the field of computing, some are studying and creating the theoretical and systems tools that developers use. The field of computer science encompasses this type of work. Computer science can be defined as the study of the theoretical foundations of information and computation and their practical implementation on computer systems.

While application development is certainly a core driver of the field of computer science, its scope is broader. The computational techniques developed by computer scientists are used to study questions on the nature of information, computation, and intelligence. They are also used in other disciplines to understand the natural and artificial phenomena around us, such as phase transitions in physics or social networks in sociology. In fact, some computer scientists are now working on some of the most challenging problems in science, mathematics, economics, and other fields.

We should emphasize that the boundary between application development and computer science (and, similarly, between application developers and computer scientists) is usually not clearly delineated. Much of the theoretical foundations of computer science have come out of application development, and theoretical computer science investigations have often led to innovative applications of computing. Thus many computing professionals wear two hats: the developer's and the computer scientist's.

1.2 Computer Systems

A computer system is a combination of hardware and software that work together to execute application programs. The hardware consists of physical components—that is, components that you can touch, such as a memory chip, a keyboard, a networking cable, or a smartphone. The software includes all the nonphysical components of the computer, including the operating system, the network protocols, the programming language tools, and the associated application programming interface (API).

Computer Hardware

The computer hardware refers to the physical components of a computer system. It may refer to a desktop computer and include the monitor, the keyboard, the mouse, and other external devices of a computer desktop and, most important, the physical “box” itself with all its internal components.

The core hardware component inside the box is the central processing unit (CPU). The CPU is where the computation occurs. The CPU performs computation by fetching program instructions and data and executing the instructions on the data. Another key internal component is main memory, often referred to as random access memory (RAM). That is where program instructions and data are stored when the program executes. The CPU fetches instructions and data from main memory and stores the results in main memory.

The set of wirings that carry instructions and data between the CPU and main memory is commonly called a bus. The bus also connects the CPU and main memory to other internal components such as the hard drive and the various adapters to which external devices (such as the monitor, the mouse, or the network cables) are connected.

The hard drive is the third core component inside the box. The hard drive is where files are stored. Main memory loses all data when the computer is shut down; the hard drive, however, is able to store a file whether the computer is powered on or off. The hard drive also has a much, much higher capacity than main memory.

The term computer system may refer to a single computer (desktop, laptop, smartphone, or pad). It may also refer to a collection of computers connected to a network (and thus to each other). In this case, the hardware also includes any network wiring and specialized network hardware such as routers.

It is important to understand that most developers do not work with computer hardware directly. It would be extremely difficult to write programs if the programmer had to write instructions directly to the hardware components. It would also be very dangerous because a programming mistake could incapacitate the hardware. For this reason, there exists an interface between application programs written by a developer and the hardware.

Operating Systems

An application program does not directly access the keyboard, the computer hard drive, the network (and the Internet), or the display. Instead it requests the operating system (OS) to do so on its behalf. The operating system is the software component of a computer system that lies between the hardware and the application programs written by the developer. The operating system has two complementary functions:

1. The OS protects the hardware from misuse by the program or the programmer and
2. The OS provides application programs an interface through which programs can request services from hardware devices.

In essence, the OS manages access to the hardware by the application programs executing on the machine.

Networks and Network Protocols

Many of the computer applications we use daily require the computer to be connected to the Internet. Without an Internet connection, you cannot send an email, browse the web, listen to Internet radio, or update your software. In order to be connected to the Internet, though, you must first connect to a network that is part of the Internet.

A computer network is a system of computers that can communicate with each other. There are several different network communication technologies in use today, some of which are wireless (e.g., Wi-Fi) and others that use network cables (e.g., Ethernet).

An internetwork is the connection of several networks. The Internet is an example of an internetwork. The Internet carries a vast amount of data and is the platform upon which the World Wide Web (WWW) and email are built.

Programming Languages

What distinguishes computers from other machines is that computers can be programmed. What this means is that instructions can be stored in a file on the hard drive, and then loaded into main memory and executed on demand. Because machines cannot process ambiguity the way we (humans) can, the instructions must be precise. Computers do exactly what they are told and cannot understand what the programmer “intended” to write.

The instructions that are actually executed are machine language instructions. They are represented using binary notation (i.e., a sequence of 0s and 1s). Because machine language instructions are extremely hard to work with, computer scientists have developed programming languages and language translators that enable developers to write instructions in a human readable language and then translate them into machine language. Such language translators are referred to as assemblers, compilers, or interpreters, depending on the programming language.

There are many programming languages out there. Some of them are specialized languages meant for particular applications such as 3D modeling or databases. Other languages are general-purpose and include C, C++, C#, Java, and Python.

While it is possible to write programs using a basic text editor, developers use Integrated Development Environments (IDEs) that provide a wide array of services that support software development. They include an editor to write and edit code, a language translator, automated tools for creating binary executables, and a debugger.

Software Libraries

A general-purpose programming language such as Python consists of a small set of general-purpose instructions. This core set does not include instructions to download web pages, draw images, play music, find patterns in text documents, or access a database. The reason why is essentially because a “sparser” language is more manageable for the developer.

Of course, there are application programs that need to access web pages or databases. Instructions for doing so are defined in software libraries that are separate from the core language, and they must be explicitly imported into a program in order to be used. The description of how to use the instructions defined in a library is often referred to as the application programming interface (API).

1.3 Python Programming Language

In this textbook, we introduce the Python programming language and use it to illustrate core computer science concepts, learn programming, and learn application development in general. In this section, we give some background on Python and how to set up a Python IDE on your computer.

Short History of Python

The Python programming language was developed in the late 1980s by Dutch programmer Guido van Rossum while working at CWI (the Centrum voor Wiskunde en Informatica in Amsterdam, Netherlands). The language was not named after the large snake species but rather after the BBC comedy series Monty Python's Flying Circus. Guido van Rossum happens to be a fan. Just like the Linux OS, Python eventually became an open source software development project. However, Guido van Rossum still has a central role in deciding how the language is going to evolve. To cement that role, he has been given the title of “Benevolent Dictator For Life” by the Python community.

Python is a general-purpose language that was specifically designed to make programs very readable. Python also has a rich library making it possible to build sophisticated applications using relatively simple-looking code. For these reasons, Python has become a popular application development language and also the preferred “first” programming language.

http://wiki.python.org/moin/Python2orPython3

Setting Up the Python Development Environment

If you do not have Python development tools installed on your computer already, you will need to download a Python IDE. The official list of Python IDEs is at

http://wiki.python.org/moin/IntegratedDevelopmentEnvironments

We illustrate the IDE installation using the standard Python development kit that includes the IDLE IDE. You may download the kit (for free) from:

http://python.org/download/

Listed there are installers for all mainstream operating systems. Choose the appropriate one for your system and complete the installation.

To get started with Python, you need to open a Python interactive shell window. The IDLE interactive shell included with the Python IDE is shown in Figure 1.1.

Figure 1.1 The IDLE IDE. The IDLE Integrated Development Environment is included in the standard implementation of Python. Shown is the IDLE interactive shell. At the >>> prompt, you can type single Python instructions. The instruction is executed by the Python interpreter when the Enter/Return key is pressed.

The interactive shell expects the user to type a Python instruction. When the user types the instruction print(‘Hello world’) and then presses the key on the keyboard, a greeting is printed:

Python 3.2.1 (v3.2.1:ac1f7e5c0510, Jul 9 2011, 01:03:53)
[GCC 4.2.1 (Apple Inc. build 5666) (dot 3)] on darwin
Type “copyright”, “credits” or “license()” for more information.
>>> print(‘Hello world’)
Hello world

The interactive shell is used to execute single Python instructions like print(‘Hello world’). A program typically consists of multiple instructions that must be stored in a file before being executed.

1.4 Computational Thinking

In order to illustrate the software development process and introduce the software development terminology, we consider the problem of automating a web search task. To model the relevant aspects of the task and describe the task as an algorithm, we must understand the task from a “computational” perspective. Computational thinking is a term used to describe the intellectual approach through which natural or artificial processes or tasks are understood and described as computational processes. This skill is probably the most important one you will develop in your training as a computer scientist.

A Sample Problem

We are interested in purchasing about a dozen prize-winning novels from our favorite online shopping web site. The thing is, we do not want to pay full price for the books. We would rather wait and buy the books on sale. More precisely, we have a target price for each book and will buy a book only when its sale price is below the target. So, every couple of days, we visit the product web page of every book on our list and, for each book, check whether the price has been reduced to below our target.

As computer scientists, we should not be satisfied with manually visiting web page after web page. We would rather automate the search process. In other words, we are interested in developing an application that visits the web pages of the books on our list and finds the books whose price is below the target. To do this, we need to describe the search process in computational terms.

Abstraction and Modeling

We start by simplifying the problem statement. The “real world” that is the context for the problem contains information that is not really relevant. For example, it is not necessarily important that the products are books, let alone prize-winning novels. Automating the search process would be the same if the products were climbing gear or fashion shoes.

It also is not important that there are 12 products on our list. More important is that there is a list (of products); our application should be able to handle a list of 12, 13, 11, or any number of products. The additional benefit of ignoring the “dozen novels” detail is that the application we end up with will be reusable on an arbitrarily long list of arbitrary products.

What are the relevant aspects of the problem? One is that each product has an associated web page that lists its price. Another is that we have a target price for each product. Finally, the web itself is a relevant aspect as well. We can summarize the relevant information as consisting of:

1. the web
2. a list that contains addresses of product web pages
3. a list that contains target prices

Let's call the first list Addresses and the second Targets.

We need to be a bit more precise with the descriptions of our lists, because it is not clear how addresses in list Addresses correspond to target prices in list Targets. We clarify this by numbering the products 0, 1, 2, 3,… (computer scientists start counting from 0) and then ordering the addresses and targets so the web page address and target price of a product are in the same position in their respective list, as shown in Figure 1.2.

Figure 1.2 Lists of web page addresses and target prices. The web page address and target price for product 0 are first in their respective lists. For product 1, they are both second, for product 2, they are third, etc.

The process of distilling the relevant aspects of a problem is called abstraction. It is a necessary step so the problem is described precisely, using the language of logic and mathematics. The result of abstraction is a model that represents all the relevant aspects of the problem.

Algorithm

The search application we want to develop should “visit” product web pages “one after another” and, for each product, “check” whether the price has been reduced to below the target price. While this description of how the application should work may be clear to us, it is not quite precise enough. For example, what do we mean by “visit,” “one after another,” and “check”?

When we “visit” a web page, we are really downloading it and displaying it in our browser (or reading it). When we say that we are going to visit pages “one after another,” we need to be clear that each page will be visited exactly once; we also should be explicit about the order in which the pages will be visited. Finally, in order to “check” whether the price has been reduced enough, we need to first find the price in the web page.

To facilitate the eventual implementation of the search process as a computer program, we need to describe the search using more precise step-by-step instructions or, in other words, an algorithm. The algorithm should consist of an unambiguous description of the steps that, when executed on a specified input, produce the desired output.

We start the development of the algorithm by clearly specifying the input data (i.e., the information we start with) and the output data (i.e., the information we desire to obtain):

Input: An ordered list of web page addresses called Addresses and an ordered list of target prices called Targets of the same size

Output: (Printed on the screen.) Web page addresses for products whose price is less than the target price

Now we can describe the algorithm:

1 Let N be the number of products in list Addresses.
2
3 For every product I = 0, 1,…, N-1, execute these statements:
4
5     Let ADDR be the address in list Addresses for product I
6
7     Download the web page whose address is ADDR and
8         let PAGE be the content of this web page
9
10    Find in PAGE the current price of product I and
11        let CURR be this value
12
13    Let TARG be the product I target price from list Targets
14
15    If CURR < TARG:
16        Print ADDR

This description of the algorithm is not real code that can be executed on a computer. It is simply a precise description of what we need to do to acomplish a task and is often refered to as pseudocode. An algorithm can also be described using actual executable code. In the rest of this book, we will describe our algorithms using Python programs.

Data Types

The description of the search algorithm includes references to various data:

1. N, the number of products
2. ADDR, the address of a web page
3. PAGE, the content of a web page
4. CURR and TARG, the current and target prices
5. The lists Addresses and Targets

The names N, I, ADDR, PAGE, CURR, and TARG are called variables, just as in algebra. The names Addresses and Targets are also variables. The purpose of variables is to store values so that they can be retrieved later. For example, the value of ADDR, set in line 5 of the algorithm, is retrieved to be printed in line 16.

Let's take a closer look at the type of values these data can have. The number of products N will be a nonnegative integer value. The current price CURR and the target price TARG will be positive numbers likely using decimal point notation; we describe them as positive non-integer numbers. What about the “value” of the web page address ADDR and the “value” of the web page content? Both are best described as sequences of characters (we ignore non-text content). Finally, we have the two lists. The list of addresses Addresses is an ordered sequence of addresses (which are character sequences), whereas the list of target prices Targets is an ordered sequence of prices (which are numbers).

The data type refers to the range of values data can have (e.g., integer, non-integer number, sequence of characters, or list of other values) and also to the operations that can be performed on the data. In the algorithm, we perform the following operations, among others, on the data:

1. We compare numbers CURR and TARG
2. We find the address of product I in list Addresses
3. We search the web page content for a price
4. We create a sequence 0, 1, 2,…, N-1 from integer N

In case a., we make the assumption that number types can be compared. In case b., we assume that we can retrieve product I from list Addresses. In case c., we assume that we can search a sequence of characters and look for something that looks like a price. In case d., we assume that we can create a sequence from 0 up to and not including an integer.

The point we are making is this: An algorithm consists of instructions that manipulate data and how the data is allowed to be manipulated depends on the data type. Consider case d., for example. While this operation makes sense for integer data type N, it does not make sense at all for, say, the web page address data ADDR. So the integer data type supports the operation of creating a sequence, whereas the “character sequence” data type does not.

So, in order to be able to think “computationally,” we really need to know what types of data we can use and what operations can be performed on that data. Because we will think “computationally” in the context of Python programming, we will need to know the data types and the operations that Python supports. Our first order of business is thus to learn Python's core data types and, in particular, the different operations that these data types support. This will be the topic of Chapter 2.

Assignments and Execution Control Structures

In addition to different types of data, the product search algorithm we developed uses different kinds of instructions. Several instructions in the algorithm assign a value to a variable:

1. In line 1, we assign a value to variable N.
2. In line 5, we assign a value to variable ADDR.
3. In line 8, we assign a value to variable PAGE.
4. In line 11, we assign a value to variable CURR.
5. In line 13, we assign a value to variable TARG.

While the values assigned to the variables are of different types, the same kind of instruction is used to do the assignment. This kind of instruction is called an assignment statement.

A different kind of instruction is used in line 15. This instruction compares the current price CURR with the target price TARG; if the value of CURR is less than the value of TARG—and only then—the statement in line 16 is executed (and the value of ADDR is printed). The If instruction in line 15 is a kind of instruction referred to as a conditional control structure.

Line 3 illustrates yet another kind of instruction. This instruction will repeatedly execute the statements in lines 5 to 16, once for every value of I. So, the statements 5 to 16 will be executed for I equal to 0, and then again for I equal to 1, and then again for I equal to 2, and so on. After the statements 5 to 16 have been executed for I equal to N-1, the execution of the instruction in line 3 is complete. This instruction is referred to as an iteration control structure. The word iteration means “the action of repeating a process.” The process that is repeated in our algorithm is the execution of statements in lines 5 to 16.

Conditional and iteration control structures are together referred to as execution control structures. Execution control structures are used to control the flow of execution of the statements in a program. In other words, they determine the order in which the statements are executed, under what conditions, and how many times. Together with assignment statements, execution control structures are the fundamental building blocks for describing computational solutions to problems and developing algorithms. We introduce Python's execution control structures in Chapter 3, after having reviewed Python's core data types in Chapter 2.

Chapter Summary

This chapter introduces the field of computer science, the work computer scientists and developers do, and the tools that computer scientists and developers use.

Computer science studies, on one hand, the theoretical foundations of information and computation and, on the other, the hands-on techniques to implement applications on computer systems. Computer application developers use the concepts and techniques of computer science in the context of application development. They formulate abstract representations that model a particular real or imaginary environment, create algorithms that manipulate data in the model, and then implement the algorithm as a program that can be executed on a computer system.

The computer science tools include the abstract tools of math and logic and the concrete computer system tools. Computer system tools include the hardware and the software. In particular, they include the programming language and the programming language tools through which the developer ultimately controls the different system components.

The abstract tools that computer scientists use are the computational thinking skills, based on logic and mathematics, that are necessary to describe problems, tasks, and processes through the lens of abstraction and computation. In order to be able to do this, we need to master a language of abstraction and computation. The best way to do this, of course, is to master a programming language. In effect, the programming language is the glue that connects the system and the abstract tools of a developer. That is why mastery of a programming language is the core skill of a computer scientist.