Data Storage

We begin our study of computer science by considering how information is encoded and stored inside computers. Our first step is to discuss the basics of a computer’s data storage devices and then to consider how information is encoded for storage in these systems. We will explore the ramifications of today’s data storage systems and how such techniques as data compression and error handling are used to overcome their shortfalls.

Bits And Their Storage:

Inside today’s computers information is encoded as patterns of 0s and 1s. These digits are called bits (short for binary digits). Although you may be inclined to associate bits with numeric values, they are really only symbols whose meaning depends on the application at hand. Sometimes patterns of bits are used to represent numeric values; sometimes they represent characters in an alphabet and punctuation marks; sometimes they represent images; and sometimes they represent sounds.

Boolean Operation:

To understand how individual bits are stored and manipulated inside a computer, it is convenient to imagine that the bit 0 represents the value false and the bit 1 represents the value true because that allows us to think of manipulating bits as manipulating true/false values. Operations that manipulate

true/false values are called Boolean operations, in honor of the mathematician George Boole (1815–1864), who was a pioneer in the field of mathematics called logic. Three of the basic Boolean operations are AND, OR, and XOR (exclusive or) as summarized in Figure 1.1. These operations are similar to the arithmetic operations TIMES and PLUS because they combine a pair of values

(the operation’s input) to produce a third value (the output). In contrast to arithmetic operations, however, Boolean operations combine true/false values rather than numeric values.

The Boolean operation AND is designed to reflect the truth or falseness of a statement formed by combining two smaller, or simpler, statements with the conjunction and. Such statements have the generic form

P AND Q

where P represents one statement and Q represents another—for example, Kermit is a frog AND Miss Piggy is an actress. The inputs to the AND operation represent the truth or falseness of the compound statement’s components; the output represents the truth or falseness of the compound statement itself. Since a statement of the form P AND Q is true only when both of its components are true, we conclude that 1 AND 1 should be 1, whereas all other cases should produce an output of 0.

In a similar manner, the OR operation is based on compound statements of the form 

P OR Q

where, again, P represents one statement and Q represents another. Such statements are true when at least one of their components is true, which agrees with the OR operation depicted. There is not a single conjunction in the English language that captures the meaning of the XOR operation. XOR produces an output of 1 (true) when one of its inputs is 1 (true) and the other is 0 (false). For example, a statement of the form P XOR Q means “either P or Q but not both.” (In short, the XOR operation produces an output of 1 when its inputs are different.)

The operation NOT is another Boolean operation. It differs from AND, OR, and XOR because it has only one input. Its output is the opposite of that input; if the input of the operation NOT is true, then the output is false, and vice versa. Thus, if the input of the NOT operation is the truth or falseness of

the statement

Fozzie is a bear.

then the output would represent the truth or falseness of the statement

Fozzie is not a bear.

Main Memory:

For the purpose of storing data, a computer contains a large collection of circuits (such as flip-flops), each capable of storing a single bit. This bit reservoir is known as the machine’s main memory.

Memory Organization:

A computer’s main memory is organized in manageable units called cells, with a typical cell size being eight bits. (A string of eight bits is called a byte. Thus, a typical memory cell has a capacity of one byte.) Small computers used in such household devices as microwave ovens may have main memories consisting of only a few hundred cells, whereas large computers may have billions of cells in their main memories.

Although there is no left or right within a computer, we normally envision the bits within a memory cell as being arranged in a row. The left end of this row is called the high-order end, and the right end is called the low-order end. The leftmost bit is called either the high-order bit or the most significant bit in reference to the fact that if the contents of the cell were interpreted as representing a numeric

value, this bit would be the most significant digit in the number. Similarly, the rightmost bit is referred to as the low-order bit or the least significant bit. Thus we may represent the contents of a byte-size memory cell. To identify individual cells in a computer’s main memory, each cell is assigned a unique “name,” called its address. The system is analogous to the technique of identifying houses in a city by addresses. In the case of memory cells, however, the addresses used are entirely numeric. To be more precise, we envision all the cells being placed in a single row and numbered in this order starting with the value zero. Such an addressing system not only gives us a way of uniquely identifying each cell but also associates an order to the cells, giving us phrases such as “the next cell” or “the previous cell.” 

An important consequence of assigning an order to both the cells in main memory and the bits within each cell is that the entire collection of bits within a computer’s main memory is essentially ordered in one long row. Pieces of this long row can therefore be used to store bit patterns that may be longer than the length of a single cell. In particular, we can still store a string of 16 bits merely by

using two consecutive memory cells.

To complete the main memory of a computer, the circuitry that actually holds the bits is combined with the circuitry required to allow other circuits to store and retrieve data from the memory cells. In this way, other circuits can get data from the memory by electronically asking for the contents of a certain address (called a read operation), or they can record information in the memory by requesting that a certain bit pattern be placed in the cell at a particular address (called a write operation).

Outline of our Study

This text follows a bottom up approach to the study of computer science, beginning with such hands-on topics as computer hardware and leading to the more abstract topics such as algorithm complexity and computability. The result is that our study follows a pattern of building larger and larger abstract tools as our understanding of the subject expands. We begin by considering topics dealing with the design and construction of machines for executing algorithms. In Chapter 1 (Data Storage) we look at how information is encoded and stored within modern computers, and in Chapter 2 Data Manipulation) we investigate the basic internal operation of a simple computer. Although part of this study involves technology, the general theme is technology independent. That is, such topics as digital circuit design, data encoding and compression systems, and computer architecture are relevant over a wide range of technology and promise to remain relevant regardless of the direction of
future technology.
We study the software that controls the overall operation of a computer. This software is called an operating system. It is a computer’s operating system that controls the interface between the machine
and its outside world, protecting the machine and the data stored within from unauthorized access, allowing a computer user to request the execution of various programs, and coordinating the internal activities required to fulfill the user’s requests.
We study how computers are connected to each other to form computer networks and how networks are connected to form internets. This study leads to topics such as network protocols, the Internet’s structure and internal operation, the World Wide Web, and numerous issues of security.
Algorithms introduces the study of algorithms from a more formal perspective. We investigate how algorithms are discovered, identify several fundamental algorithmic structures, develop elementary techniques for representing algorithms, and introduce the subjects of algorithm efficiency
and correctness.
Programming Languages we consider the subject of algorithm representation and the program development process. Here we find that the search for better programming techniques has led to a variety of programming methodologies or paradigms, each with its own set of programming languages. We investigate these paradigms and languages as well as consider issues of grammar
and language translation.
Software Engineering introduces the branch of computer science known as software engineering, which deals with the problems encountered when developing large software systems. The underlying theme is that the design of large software systems is a complex task that embraces problems beyond those of traditional engineering. Thus, the subject of software engineering has become an important field of research within computer science, drawing from such diverse fields as engineering, project management, personnel management, programming language design, and even architecture.
In next two chapters we look at ways data can be organized within a computer system.
Data Abstractions we introduce techniques traditionally used for organizing data in a computer’s main memory and then trace the evolution of data abstraction from the concept of primitives to today’s objectorientedtechniques.
Database Systems we consider methods traditionally used for organizing data in a computer’s mass storage and investigate how extremely large and complex database systems are implemented.
Computer Graphics we explore the subject of graphics and animation, a field that deals with creating and photographing virtual worlds. Based on advancements in the more traditional areas of computer science such as machine architecture, algorithm design, data structures, and software engineering,
the discipline of graphics and animation has seen significant progress and has now blossomed into an exciting, dynamic subject. Moreover, the field exemplifies how various components of computer science combine with other disciplines such as physics, art, and photography to produce striking results.
Artificial Intelligence we learn that in order to develop more useful machines computer science has turned to the study of human intelligence for leadership. The hope is that by understanding how our own minds reason and perceive, researchers will be able to design algorithms that mimic these
processes and thus transfer these capabilities to machines. The result is the area of computer science known as artificial intelligence, which leans heavily on research in such areas as psychology, biology, and linguistics.
We close our study with Theory of Computation by investigating the theoretical foundations of computer science—a subject that allows us to understand the limitations of algorithms (and thus machines). Here we identify some problems that cannot be solved algorithmically (and therefore lie beyond the capabilities of machines) as well as learn that the solutions to many other problems require such enormous time or space that they are also unsolvable from a practical perspective. Thus, it is through this study that we are able to grasp the scope and limitations of algorithmic systems.
In each chapter our goal is to explore to a depth that leads to a true understanding of the subject. We want to develop a working knowledge of computer science—a knowledge that will allow you to understand the technical society in which you live and to provide a foundation from which you can learn on your own as science and technology advance.