2 Chapter 1 Analyzing Algorithms and Problems:Principles and Examples 1,1 Introduction To say that a problem is solvable algorithmically means,informally,that a computer program can be written that will produce the correct answer for any input if we let it run long enough and allow it as much storage space as it needs.In the 1930s,before the advent of computers,mathematicians worked very actively to formalize and study the notion of an algorithm,which was then interpreted informally to mean a clearly specified set of simple instructions to be followed to solve a problem or compute a function.Various formal modeis of computation were devised and investigated.Much of the emphasis in the early work in this field,cailed computability theory,was on describing or characterizing those problems that could be solved algorithmically and on exhibiting some problems that could not be.One of the important negative results,established by Alan Turing.was the proof of the unsolvability of the"halting problem."The halting problem is to determine whether an arbitrary given algorithm (or computer program)will eventually hait(rather than,say, get into an infinite loop)while working on a given input.There cannot exist a computer program that solves this problem. Although computability theory has obvious and fundaniental implications for com- puter science,the knowledge that a prohlem can theoretically be solved on a computer is not sufficient to tell us whether it is practical to do so.For example,a perfect chess-playing program could be written.This would not be a very difficult task;there are only a finite number of ways to arrange the chess pieces on the board,and under certain rules a game must terminate after a finite number of moves.The program could consider each of the computer's possible moves,each of its opponent's possible responses,each of its possi- ble responses to those moves,and so on until each sequence of possible moves reaches an end.Then since it knows the ultimate result of each move.the computer can choose the best one.The number of distinct arrangements of pieces on the board that it is reasonable to consider(much less the number of sequences of moves)is roughly 1050 hy some esti- mates.A program that examined them all would take several thousand years to run.Thus such a program has not been run. Numerous prohlems with practical applications can be solved--that is,programs can be written for them-but the time and storage requirements are much too great for these programs to be of practical use.Clearly the time and space requirements of a program are of practical importance.They have become,therefore,the subject of theoretical study in the area of computer science called computational complexiry.One branch of this study, which is not covered in this book,is concerned with setting up a formal and somewhat abstract theory of the complexity of computable functions.(Solving a problem is equivalent to computing a function from the set of inputs to the set of outputs.)Axioms for measures of complexity have been formulated;they are basic and general enough so that either the number of instructions executed or the number of storage bits used by a program can be taken as a complexity measure.Using these axioms,we can prove the existence of arbitrarily complex problems and of problems for which there is no best program. The branch of computational complexity studied in this book is concerned with an- alyzing specific problems and specific algorithms.This book is intended to help readers build a repertoire of classic algorithms to solve common problems.some general design
1.2 Java as an Algorithm Language 3 techniques,tools and principles for analyzing algorithms and problems,and methods of proving correctness.We will present,study,and analyze algorithms to solve a variety of problems for which computer programs are frequently used.We will analyze the amount of time the algorithms take to execute,and we will also often analyze the amount of space used by the algorithms.In the course of describing algorithms for a variety of problems, we will see that several algorithm design techniques often prove uscful.Thus we will pause now and then to talk about some general techniques.such as divide-and-conquer,greedy algorithms,depth-first search,and dynamic programming.We will also study the com- putational complexity of the problems themselves.that is,the time and space inherently required to solve the problem no matter what algorithm is used.We will study the class of NP-complete problems-problems for which no efficient algorithms are known-and consider some heuristics for getting useful results.We will also describe an approach for solving these problems using DNA instead of electronic computers.Finally,we will intro- duce the subject of algorithms for parallel computers. In the following sections we outline the algorithm language,review some hackground and tools that will be used throughout the book,and illustrate the main concepts involved in analyzing an algorithm. 1.2 Java as an Algorithm Language We chose Java as the algorithm language for this book by balancing several criteria.The algorithms should be easy to read.We want to focus on the strategy and techniques of an al- gorithm,not declarations and syntax details of concern to a compiler.The language should support data ahstraction and prohlem decomposition,to make it easy to express algorithmic ideas clearly.The language should provide a practical pathway to implementation.It should be widely available and provide support for program development.Actually implementing and running algorithms can enhance the student's understanding greatly,and should not turn into a frustrating battle with the compiler and debugger.Finally,because this book is teaching algorithms,not a programming language,it should be reasonably easy to trans- late an algorithm to a varicty of languages that readers might wish to use,and specialized language features should be minimized. Java showed up well by several of our criteria,although we would not claim it is ideal.It supports data abstraction naturally.It is type-safe,meaning that objects of one type cannot be used in operations intended for a different type;arbitrary type conversions(called "casts")are not permitted,either.There is an explicit boolean type,so if one types (the assignment operator)when"=="(the equality operator)was intended,the compiler catches it. Java does not permit pointer manipulations,which are a frequent source of obscure errors;in fact,pointers are hidden from the programmer and handled automatically behind the scenes.At run time,Java checks for out-of-range array subscripts,and other incon- sistencies that might be other sources of obscure errors.It performs "garbage collection," which means that it recycles the storage space of ohjects that are no longer referenced;this takes a hig burden of space management off the programmer
4 Chapter 1 Analyzing Algorithms and Problems:Principles and Examples On the downside,Java has many of the same terse,cryptic syntax features of C.The object structure may force inefficiencies in time and space.Many Java constructs require greater verbosity than other languages,such as C,for instance. Although Java has many specialized features,the algorithms presented in this book avoid most of them,in the interest of being language-independent.In fact,some steps within an algorithm may be stated in pseudocode for easier readability.This section de- scribes a small subset of Java that we use for the book,and the pseudocode conventions that we use to improve readability of the algorithms.The Java-specific Appendix A gives some additional implementation details for readers who want to get a Java program running,but these details are not pertinent to understanding the main text. 1.2.1 A Usable Subset of Java A thorough acquaintance with Java is not important to understand the algorithms in this text.This section gives a brief overview of the Java features that do appear,for those readers who wish to follow the implementation issues closely.In some cases we point out object- oriented features of Java that might be used,but which we avoid so that the text can be fairly language-independent;this is mainly for the benefit of readers who are familiar with some other object-oriented language,such as C++,but who are not completely familiar with Java.A sample Java "main program"appears in Appendix A.Many books are available for in-depth coverage of the Java language. Readers who are well acquainted with Java will undoubtedly notice many instances in which some nice Java feature could have been used.However,the concepis behind the algorithms do not require any special features,and we want these concepts to be easy to grasp and apply in a variety of languages,so we leave it to the readers,once they have grasped the concepts,to tailor the implementations to their favorite language. Readers familiar with C syntax will reoognize many similarities in Java syntax:Blocks are delimited by curly braces,and ")"square brackets,"[and"]",enclose array indexes.As in C and C++,a two-dimensional array is really a one-dimensional array whose elements are themselves one-dimensional arrays,so two pairs of square brackets are needed to access an element,.as in"matrixi]”.Operators“=".“l-",“<-”,and">=" are the keyboard versions of the mathematical relational operators“=',"≠"，“s",and respectively.In pseudocode the text usually prefers the mathematical versions.Text examples use the"++"and"--"operators to increment and decrement,but never use them embedded in other expressions.There are also the operators"+='.“-=”,“*=",and“/=” adopted from C.For example, p+=q:/÷Add g to p./ y-=x:/Subtract x from y As just illusirated,comments extend from"//"to end-of-line,or from"/*""to "*/"as in C++. Function headers normally look the same in Java as in C.The function header specifies the paramerer rype signature in parentheses after the function name;it specifies the return rype before the function name.The combination of return type and parameter type signature is called the function's full type signature,or profotype.Thus
1.2 Java as an Algorithm Language 5 int getMin(PriorityQ pq) tells us that getMin takes one parameter of type (or class)PriorityQ and returns type int. Java has a few primitive rypes and all remaining types are called classes.The primitive types are logical (boolean)and numerical (byte,char,short,int,long,float,and double) types.All classes (nonprimitive types)in Java are reference classes.Behind the scenes, variables declared in classes are"pointers";their values are addresses.Instances of classes are called objects.Declaring a variable does not create an object.Generally.objects are created with a"new"operator,which returns a reference to the new object. The data fields of an object are called instance fields in object-oriented terminology. The binary dot operator is used to access instance fields of an object. Example 1.1 Creating and accessing Java objects For this example,let's assume that date information has the following nested logical structure: 。year ·number ·isLeap month ·day That is,using informal terminology,year is a compound atribute that consists of the boolean attribute isLeap and the integer attribute number.while month and day are simple integer attributes.To reflect this nested structure,we have to define two classes in Java, one for the whole date and another for the year field.Assume we choose the names Date and Year,respectively,for these classes.Then we would declare number and isLeap as instance fields in the Year class and declare year,month,and day as instance fields in the Date class.Moreover,we would most likely define Year as an inner class of Date.The syntax is shown in Figure 1.1. class Date public Year year; public int month; public int day; public static class Year public int number; public boolean isLeap; Figure 1.1 Java syntax for the Date class with an inner Year class
Chapter 1 Analyzing Algorithms and Problems:Principles and Examples Without the public keyword,the instance fields would not be accessihle outside of the Date and Year classes;for simplicity,we make them public here.The reason for declaring the inner class,Year,to be static is so we can create an instance of Year that is not associated with any particular Date object.All inner classes will be static in this book. Suppose we have created a Date object that is referenced by variable dueDate.To access the instance field year in this obiect,the dot operator is used,as in"dueDate.year." If the instance field is in a class (as opposed to being in a primitive type),then further dot operators access its instance fields,as in "dueDate.year.isLeap." The assignment statcment copies only the reference,or address,of an object in a class;it does not make a copy of the instance fields.For example,"noticeDate dueDate" causes variable noticeDate to refer to the same object as variable dueDate.Therefore the following code fragment would probably be a logical error: noticeDate dueDate; noticeDate.day dueDate.day-7; See Scction 1.2.2 for additional discussion. Control statements if,else,while,for,and break have the same meanings in Java as in C (and C++)and arc used in this book.Severa)other control statements exist,but are not used.The syntax for while and for are while continuation condition )body for initializer;continuation condition;incrementer body whcre"initializer”and“"incrementer''are simple statements(without“t,").“body'is an arbitrary statement,and "continuation condition"is a boolean expression.The break statement causes an immediate exit froin the closest enclosing for or while loop. All classes form a tree (also called a hierarchy),with the Object class being the root. When declaring a new class,it is possible to say it extends a previously defined class,and the new class becoines a child of the previously defined class in the class tree.We will not create such structures in this text,to keep the code as language-independent as possible; however,a few examples are given in Appendix A.When the new class is not declared to extend any class,then it extends Object by default.Complex class structures are not needed for the algorithms studied in this text. Operations on objects are called methods in object-oriented terminology;however, we will restrict ourselves to the use of static methods,which are simply procedures and functions.In our terminology a procedure is a named sequence of computation steps that may be called (with parameters);a function is a procedure that also returns a value to the caller.In Java a procedure that returns no value is declared as having return type void;C and C++are similar in this respect.The term static is technical Java terminology, which means that the method can be applied to any object or objects of the appropriate types(an object's type is its class)according to the method's type signature (often called IIt also exits from swltch.but switch is not used in this hock