2 CHAPTER 1.COMPUTERS AND PROGRAMS 1.2 Program Power You have already learned an important lesson of computing:Soffware (programs)rules the hardware(the physical machine).It is the software that determines what any computer can do.Without programs,comput- ers would just be expensive paperweights.The process of creating software is called programming,and that is the main focus of this book. Computer programming is a challenging activity.Good programming requires an ability to see the big picture while paying attention to minute detail.Not everyone has the talent to become a first-class program- mer,just as not everyone has the skills to be a professional athlete.However,virtually anyone can learn how to program computers.With some patience and effort on your part,this book will help you to become a programmer. There are lots of good reasons to learn programming.Programming is a fundamental part of computer science and is,therefore,important to anyone interested in becoming a computer professional.But others can also benefit from the experience.Computers have become a commonplace tool in our society.Understanding the strengths and limitations of this tool requires an understanding of programming.Non-programmers often feel they are slaves of their computers.Programmers,however,are truly the masters.If you want to become a more intelligent user of computers,then this book is for you. Programming can also be loads of fun.It is an intellectually engaging activity that allows people to express themselves through useful and sometimes remarkably beautiful creations.Believe it or not,many people actually write computer programs as a hobby.Programming also develops valuable problem-solving skills,especially the ability to analyze complex systems by reducing them to interactions of understandable subsystems. As you probably know,programmers are in great demand.More than a few liberal arts majors have turned a couple computer programming classes into a lucrative career option.Computers are so commonplace in the business world today that the ability to understand and program computers might just give you the edge over your competition,regardless of your occupation. 1.3 What is Computer Science? You might be surprised to learn that computer science is not the study of computers.A famous computer scientist named Edsgar Dijkstra once quipped that computers are to computer science what telescopes are to astronomy.The computer is an important tool in computer science,but it is not itself the object of study. Since a computer can carry out any process that we can describe,the real question is What processes can we describe?Put another way,the fundamental question of computer science is simply What can be computed? Computer scientists use numerous techniques of investigation to answer this question.The three main ones are design,analysis,and experimentation. One way to demonstrate that a particular problem can be solved is to actually design a solution.That is. we develop a step-by-step process for achieving the desired result.Computer scientists call this an algorithm. That's a fancy word that basically means"recipe."The design of algorithms is one of the most important facets of computer science.In this book you will find techniques for designing and implementing algorithms. One weakness of design is that it can only answer the question What is computable?in the positive.IfI can devise an algorithm,then the problem is solvable.However,failing to find an algorithm does not mean that a problem is unsolvable.It may mean that I'm just not smart enough,or I haven't hit upon the right idea yet.This is where analysis comes in. Analysis is the process of examining algorithms and problems mathematically.Computer scientists have shown that some seemingly simple problems are not solvable by any algorithm.Other problems are in- tractable.The algorithms that solve these problems take too long or require too much memory to be of practical value.Analysis of algorithms is an important part of computer science;throughout this book we will touch on some of the fundamental principles.Chapter 13 has examples of unsolvable and intractable problems. Some problems are too complex or ill-defined to lend themselves to analysis.In such cases,computer scientists rely on experimentation;they actually implement systems and then study the resulting behavior. Even when theoretical analysis is done,experimentation is often needed in order to verify and refine the2 CHAPTER 1. COMPUTERS AND PROGRAMS 1.2 Program Power You have already learned an important lesson of computing: Software (programs) rules the hardware (the physical machine). It is the software that determines what any computer can do. Without programs, comput￾ers would just be expensive paperweights. The process of creating software is called programming, and that is the main focus of this book. Computer programming is a challenging activity. Good programming requires an ability to see the big picture while paying attention to minute detail. Not everyone has the talent to become a first-class program￾mer, just as not everyone has the skills to be a professional athlete. However, virtually anyone can learn how to program computers. With some patience and effort on your part, this book will help you to become a programmer. There are lots of good reasons to learn programming. Programming is a fundamental part of computer science and is, therefore, important to anyone interested in becoming a computer professional. But others can also benefit from the experience. Computers have become a commonplace tool in our society. Understanding the strengths and limitations of this tool requires an understanding of programming. Non-programmers often feel they are slaves of their computers. Programmers, however, are truly the masters. If you want to become a more intelligent user of computers, then this book is for you. Programming can also be loads of fun. It is an intellectually engaging activity that allows people to express themselves through useful and sometimes remarkably beautiful creations. Believe it or not, many people actually write computer programs as a hobby. Programming also develops valuable problem-solving skills, especially the ability to analyze complex systems by reducing them to interactions of understandable subsystems. As you probably know, programmers are in great demand. More than a few liberal arts majors have turned a couple computer programming classes into a lucrative career option. Computers are so commonplace in the business world today that the ability to understand and program computers might just give you the edge over your competition, regardless of your occupation. 1.3 What is Computer Science? You might be surprised to learn that computer science is not the study of computers. A famous computer scientist named Edsgar Dijkstra once quipped that computers are to computer science what telescopes are to astronomy. The computer is an important tool in computer science, but it is not itself the object of study. Since a computer can carry out any process that we can describe, the real question is What processes can we describe? Put another way, the fundamental question of computer science is simply What can be computed? Computer scientists use numerous techniques of investigation to answer this question. The three main ones are design, analysis, and experimentation. One way to demonstrate that a particular problem can be solved is to actually design a solution. That is, we develop a step-by-step process for achieving the desired result. Computer scientists call this an algorithm. That’s a fancy word that basically means “recipe.” The design of algorithms is one of the most important facets of computer science. In this book you will find techniques for designing and implementing algorithms. One weakness of design is that it can only answer the question What is computable? in the positive. If I can devise an algorithm, then the problem is solvable. However, failing to find an algorithm does not mean that a problem is unsolvable. It may mean that I’m just not smart enough, or I haven’t hit upon the right idea yet. This is where analysis comes in. Analysis is the process of examining algorithms and problems mathematically. Computer scientists have shown that some seemingly simple problems are not solvable by any algorithm. Other problems are in￾tractable. The algorithms that solve these problems take too long or require too much memory to be of practical value. Analysis of algorithms is an important part of computer science; throughout this book we will touch on some of the fundamental principles. Chapter 13 has examples of unsolvable and intractable problems. Some problems are too complex or ill-defined to lend themselves to analysis. In such cases, computer scientists rely on experimentation; they actually implement systems and then study the resulting behavior. Even when theoretical analysis is done, experimentation is often needed in order to verify and refine the