CS101 Introduction to Computing - Handouts.pdf

Introduction to Computing – CS101 VU Module 82 82. Networking and the Internet: Protection and Cures Another preventative tool that has filtering connotations is the proxy server. A proxy server is a software unit that a...

Introduction to Computing – CS101 VU Module 82 82. Networking and the Internet: Protection and Cures Another preventative tool that has filtering connotations is the proxy server. A proxy server is a software unit that acts as an intermediary between a client and a server with the goal of shielding the client from adverse actions of the server. Without a proxy server, a client communicates directly with a server, meaning that the server has an opportunity to learn a certain amount about the client. Over time, as many clients within an organization’s intranet deal with a distant server, that server can collect a multitude of information about the intranet’s internal structure—information that can later be used for malicious activity. To counter this, an organization can establish a proxy server for a particular kind of service (FTP, HTTP, telnet, etc.). Then, each time a client within the intranet tries to contact a server of that type, the client is actually placed in contact with the proxy server. In turn, the proxy server, playing the role of a client, contacts the actual server. From then on the proxy server plays the role of an intermediary between the actual client and the actual server by relaying messages back and forth. The first advantage of this arrangement is that the actual server has no way of knowing that the proxy server is not the true client, and in fact, it is never aware of the actual client’s existence. In turn, the actual server has no way of learning about the intranet’s internal features. The second advantage is that the proxy server is in position to filter all the messages sent from the server to the client. For example, an FTP proxy server could check all incoming files for the presence of known viruses and block all infected files. Another tool for preventing problems in a network environment is auditing software. Using network auditing software, a system administrator can detect a sudden increase in message traffic at various Page 152 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU locations within the administrator’s realm, monitor the activities of the system’s firewalls, and analyze the pattern of requests being made by the individual computers in order to detect irregularities. In effect, auditing software is an administrator’s primary tool for identifying problems before they grow out of control. Another means of defense against invasions via network connections is software called antivirus software, which is used to detect and remove the presence of known viruses and other infections. (Actually, antivirus software represents a broad class of software products, each designed to detect and remove a specific type of infection. For example, whereas many products specialize in virus control, others specialize in spyware protection.) It is important for users of these packages to understand that, just as in the case of biological systems, new computer infections are constantly coming on the scene that require updated vaccines. Thus, antivirus software must be routinely maintained by downloading updates from the software’s vendor. Even this, however, does not guarantee the safety of a computer. After all, a new virus must first infect some computers before it is discovered, and a vaccine is produced. Thus, a wise computer user never opens email attachments from unfamiliar sources, does not download software without first confirming its reliability, does not respond to pop-up adds, and does not leave a PC connected to the Internet when such connection is not necessary. Page 153 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 83 83. Networking and the Internet: Encryption Page 154 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Figure 77: Public key encryption Many commercial certificate authorities are now available on the Internet, although it is also common for organizations to maintain their own certificate authorities in order to maintain tighter control over the security of the organization’s communication. Finally, we should comment on the role public-key encryption systems play in solving problems of authentication—making sure that the author of a message is, in fact, the party it claims to be. The critical point here is that, in some public-key encryption systems, the roles of the encryption and decryption keys can be reversed. That is, text can be encrypted with the private key, and because only one party has access to that key, any text that is so encrypted must have originated from that party. In this manner, the holder of the private key can produce a bit pattern, called a digital signature, that only that party knows how to produce. By attaching that signature to a message, the sender can mark the message as being authentic. A digital signature can be as simple as the encrypted version of the message itself. All the sender must do is encrypt the message being transmitted using his or her private key (the key typically used for decrypting). When the message is received, the receiver uses the sender’s public key to decrypt the signature. The message that is revealed is guaranteed to be authentic because only the holder of the private key could have produced the encrypted version. Page 155 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 84 84. Networking and the Internet: Legal Approaches to Network Security Two Issues US – Computer Fraud and Abuse Act Page 156 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Page 157 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 85 85. Algorithm: an Informal Review 1. Take input of KM’s 2. Multiply the input with 1000. 3. Display the result As long as the halt instruction has not been executed continue to execute the following steps: a. Fetch an instruction. b. Decode the instruction. c. Execute the instruction. Many researchers believe that every activity of the human mind, including imagination, creativity, and decision making, is actually the result of algorithm execution. Page 158 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 86 86. Algorithm: Formal Definition of Algorithm Formal Definition An algorithm is an ordered set of unambiguous, executable steps that defines a terminating process. Order vs sequence  Have a well-established structure in terms of the order of their execution  Does not mean a sequence – like we do not have in parallel processing.  Flip-flops producing their output individually and then together they have a meaning. Executable  Make a list of all the positive integers.  Computer scientists use the term effective to capture the concept of being executable. Unambiguous The information in the state of the process must be sufficient to determine uniquely and completely the actions required by each step. Make a pretty cartoon! Terminating Process The execution of an algorithm must lead to an end. But!  Monitoring the vital signs of a hospital patient  Maintaining an aircraft’s altitude in flight. Page 159 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 87 87. Algorithm: Abstract Nature of Algorithms It is important to emphasize the distinction between an algorithm and its representation—a distinction that is analogous to that between a story and a book. A story is abstract, or conceptual, in nature; a book is a physical representation of a story. If a book is translated into another language or republished in a different format, it is merely the representation of the story that changes—the story itself remains the same. In the same manner, an algorithm is abstract and distinct from its representation. A single algorithm can be represented in many ways. As an example, the algorithm for converting temperature readings from Celsius to Fahrenheit is traditionally represented as the algebraic formula F = (9/5)C + 32 But it could be represented by the instruction Multiply the temperature reading in Celsius by 9⁄5 and then add 32 to the product or even in the form of an electronic circuit. In each case the underlying algorithm is the same; only the representations differ. The distinction between an algorithm and its representation presents a problem when we try to communicate algorithms. A common example involves the level of detail at which an algorithm must be described. Among meteorologists, the instruction “Convert the Celsius reading to its Fahrenheit equivalent” suffices, but a layperson, requiring a more detailed description, might argue that the instruction is ambiguous. The problem, however, is not with the underlying algorithm but that the algorithm is not represented in enough detail for the layperson. In the next section we will see how the concept of primitives can be used to eliminate such ambiguity problems in an algorithm’s representation. Finally, while on the subject of algorithms and their representations, we should clarify the distinction between two other related concepts—programs and processes. A program is a representation of an algorithm. (Here we are using the term algorithm in its less formal sense in that many programs are representations of nonterminating “algorithms.”) In fact, within the computing community the term program usually refers to a formal representation of an algorithm designed for computer application. We defined a process already to be the activity of executing a program. Note, however, that to execute a program is to execute the algorithm represented by the program, so a process could equivalently be defined as the activity of executing an algorithm. We conclude that programs, algorithms, and processes are distinct, yet related, entities. A program is the representation of an algorithm, whereas a process is the activity of executing an algorithm. Page 160 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 88 88. Algorithm: Representation (Primitives) The representation of an algorithm requires some form of language. In the case of humans, this might be a traditional natural language (English, Spanish, Russian, Japanese) or perhaps the language of pictures, as demonstrated in Figure 78, which describes an algorithm for folding a bird from a square piece of paper. Often, however, such natural channels of communication lead to misunderstandings, sometimes because the terminology used has more than one meaning. (The sentence, “Visiting grandchildren can be nerve- racking,” could mean either that the grandchildren cause problems when they come to visit or that going to see them is problematic.) Problems also arise over misunderstandings regarding the level of detail required. Few readers could successfully fold a bird from the directions given in Figure 78, yet a student of origami would probably have little difficulty. In short, communication problems arise when the language used for an algorithm’s representation is not precisely defined or when information is not given in adequate detail. Figure 78: Folding a bird from a square piece of paper Computer science approaches these problems by establishing a well-defined set of building blocks from which algorithm representations can be constructed. Such a building block is called a primitive. Assigning precise definitions to these primitives removes many problems of ambiguity and requiring algorithms to be described in terms of these primitives establishes a uniform level of detail. A collection of primitives along with a collection of rules stating how the primitives can be combined to represent more complex ideas constitutes a programming language. Each primitive has its own syntax and semantics. Syntax refers to the primitive’s symbolic representation; semantics refers to the meaning of the primitive. The syntax of air consists of three symbols, whereas the semantics is a gaseous substance that surrounds the world. As an example, Figure 79 presents some of the primitives used in origami. Page 161 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Figure 79: Origami primitives To obtain a collection of primitives to use in representing algorithms for computer execution, we could turn to the individual instructions that the machine is designed to execute. If an algorithm is expressed at this level of detail, we will certainly have a program suitable for machine execution. However, expressing algorithms at this level is tedious, and so one normally uses a collection of “higher-level” primitives, each being an abstract tool constructed from the lower-level primitives provided in the machine’s language. The result is a formal programming language in which algorithms can be expressed at a conceptually higher level than in machine language. We will discuss such programming languages in the next chapter Page 162 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 89 89. Algorithm: Representation (Pseudocode) For now, we forgo the introduction of a formal programming language in favor of a less formal, more intuitive notational system known as pseudocode. In general, a pseudocode is a notational system in which ideas can be expressed informally during the algorithm development process. One way to obtain a pseudocode is simply to loosen the rules of a formal programming language, borrowing the syntax-semantic structures of the language, intermixed with less formal constructs. There are many such pseudocode variants, because there are many programming languages in existence. Two particularly popular choices are loose versions of the languages Algol and Pascal, largely because these were widely used in textbooks and academic papers for decades. More recently, pseudocode reminiscent of the Java and C languages has proliferated, again because most programmers will have at least a reading knowledge of these languages. Regardless of where a pseudocode borrows its syntax from, one essential property is required for it to serve its purpose in expressing algorithms: A pseudocode must have a consistent, concise notation for representing recurring semantic structures. One semantic structure is the saving of a computed value. For example, if we have computed the sum of our checking and savings account balances, we may want to save the result so we can refer to it later. In such cases we will use the form name = expression where name is the name by which we will refer to the result and expression describes the computation whose result is to be saved. This pseudocode structure directly follows the equivalent Python assignment statement, which we introduced in Chapter 1 for storing a value into a Python variable. For example, the statement RemainingFunds = CheckingBalance + SavingsBalance is an assignment statement that assigns the sum of CheckingBalance and SavingsBalance to the name RemainingFunds? Thus, the term RemainingFunds can be used in future statements to refer to that sum. Another recurring semantic structure is the selection of one of two possible activities depending on the truth or falseness of some condition. Examples include: If the gross domestic product has increased, buy common stock otherwise sell common stock. Buy common stock if the gross domestic product has increased and sell it otherwise. Buy or sell common stock depending on whether the gross domestic product has increased or decreased, respectively. Each of these statements could be rewritten to conform to the structure if (condition): activity else: activity where we have used the keywords if and else to announce the different sub- structures within the main structure and have used colons and indentation to delineate the boundaries of these substructures. The condition and the else will always be followed immediately by a colon. The corresponding activity will be indented. If an activity consists of multiple steps, they will all be similarly indented. By adopting this Page 163 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU syntactic structure for our pseudocode, we acquire a uniform way in which to express this common semantic structure. Thus, whereas the statement Depending on whether the year is a leap year, divide the total by 366 or 365, respectively might possess a more creative literary style, we will consistently opt for the straightforward condition: if (year is leap year): daily total = total / 366 else: daily total = total / 365 Page 164 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 90 90. Algorithm: Representation (Pseudocode) While-Structure Another common semantic structure is the repeated execution of a statement or sequence of statements as long as some condition remains true. Informal examples include: For such cases, we adopt the uniform pattern For our pseudocode. In short, such a statement means to check the condition and, if it is true, perform the activity and return to check the condition again. If, however, the condition is found to be false, move on to the next instruction following the while structure. Thus, both of the preceding statements are reduced to: Page 165 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 91 91. Algorithm: Representation (Pseudocode) Function-Structure We want to use our pseudocode to describe activities that can be used as abstract tools in other applications. Computer science has a variety of terms for such program units, including subprogram, subroutine, procedure, method, and function, each with its own variation of meaning. We will follow Python convention, using the term function for our pseudocode and using the Python keyword def to announce the title by which the pseudocode unit will be known. More precisely, we will begin a pseudocode unit with a statement of the form def name(): where name is the particular name of the unit. We will then follow this introductory statement with the statements that define the unit’s action. For example, Figure 80 is a pseudocode representation of a function called Greetings that prints the message “Hello” three times. Figure 80: The function Greetings in pseudocode When the task performed by a function is required elsewhere in our pseudo code, we will merely request it by name. For example, if two functions were named ProcessLoan and RejectApplication, then we could request their services within an if-else structure by writing if (... ): ProcessLoan() else: RejectApplication() which would result in the execution of the function ProcessLoan if the tested condition were true or in the execution of RejectApplication if the condition were false. Page 166 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 92 92. Algorithm: Discovery (The Art of Problem Solving) The techniques of problem solving and the need to learn more about them are not unique to computer science but rather are topics pertinent to almost any field. The close association between the process of algorithm discovery and that of general problem solving has caused computer scientists to join with those of other disciplines in the search for better problem-solving techniques. Ultimately, one would like to reduce the process of problem solving to an algorithm in itself, but this has been shown to be impossible. Thus the ability to solve problems remains more of an artistic skill to be developed than a precise science to be learned. As evidence of the elusive, artistic nature of problem solving, the following loosely defined problem- solving phases presented by the mathematician G. Polya in 1945 remain the basic principles on which many attempts to teach problem-solving skills are based today. Phase 1. Understand the problem. Phase 2. Devise a plan for solving the problem. Phase 3. Carry out the plan. Phase 4. Evaluate the solution for accuracy and for its potential as a tool for solving other problems. Translated into the context of program development, these phases become Phase 1. Understand the problem. Phase 2. Get an idea of how an algorithmic function might solve the problem. Phase 3. Formulate the algorithm and represent it as a program. Phase 4. Evaluate the program for accuracy and for its potential as a tool for solving other problems. As an example, consider the following problem: Person A is charged with the task of determining the ages of person B’s three children. B tells A that the product of the children’s ages is 36. After considering this clue, A replies that another clue is required, so B tells A the sum of the children’s ages. Again, A replies that another clue is needed, so B tells A that the oldest child plays the piano. After hearing this clue, A tells B the ages of the three children. How old are the three children? At first glance the last clue seems to be totally unrelated to the problem, yet it is apparently this clue that allows A to finally determine the ages of the children. How can this be? Let us proceed by formulating a plan of attack and following this plan, even though we still have many questions about the problem. Our plan will be to trace the steps described by the problem statement while keeping track of the information available to person A as the story progresses. The first clue given A is that the product of the children’s ages is 36. This means that the triple representing the three ages is one of those listed in Figure 81(a). The next clue is the sum of the desired triple. We are not told what this sum is but we are told that this information is not enough for A to isolate the correct triple; therefore the desired triple must be one whose sum appears at least twice in the table of Figure 81(b). But the only triples appearing in Figure 81(b) with identical sums are (1,6,6) and (2,2,9), both of which produce the sum 13. This is the information available to A at the time the last clue is given. It is at this point that we finally understand the significance of the last clue. It has nothing to do with playing the piano; rather Page 167 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU it is the fact that there is an oldest child. This rules out the triple (1,6,6) and thus allows us to conclude that the children’s ages are 2, 2, and 9. In this case, then, it is not until we attempt to implement our plan for solving the problem (Phase 3) that we gain a complete understanding of the problem (Phase 1). Had we insisted on completing Phase 1 before proceeding, we would probably never have found the children’s ages. Such irregularities in the problem- solving process are fundamental to the difficulties in developing systematic approaches to problem solving. Figure 81: Analyzing the possibilities Page 168 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 93 93. Algorithm: Getting your Foot in the Door We have been discussing problem solving from a somewhat philosophical point of view while avoiding a direct confrontation with the question of how we should go about trying to solve a problem. There are, of course, numerous problem-solving approaches, each of which can be successful in certain settings. We will identify some of them shortly. For now, we note that there seems to be a common thread running through these techniques, which simply stated is “get your foot in the door.” As an example, let us consider the following simple problem: Page 169 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 94 94. Algorithm: Algorithm Discovery Strategies (I) Of course, being told to get our foot in the door is not the same as being told how to do it. Obtaining this toehold, as well as realizing how to expand this initial thrust into a complete solution to the problem, requires creative input from the problem solver. There are, however, several general approaches that have been proposed by Polya and others for how one might go about getting a foot in the door. One is to try working the problem backward. For instance, if the problem is to find a way of producing a particular output from a given input, one might start with that output and attempt to back up to the given input. This approach is typical of people trying to discover the bird-folding algorithm in the previous section. They tend to unfold a completed bird in an attempt to see how it is constructed. Another general problem-solving approach is to look for a related problem that is either easier to solve or has been solved before and then try to apply its solution to the current problem. This technique is of particular value in the context of program development. Generally, program development is not the process of solving a particular instance of a problem but rather of finding a general algorithm that can be used to solve all instances of the problem. More precisely, if we were faced with the task of developing a program for alphabetizing lists of names, our task would not be to sort a particular list but to find a general algorithm that could be used to sort any list of names. Thus, although the instructions 1. Interchange the names David and Alice. 2. Move the name Carol to the position between Alice and David. 3. Move the name Bob to the position between Alice and Carol. correctly sort the list David, Alice, Carol, and Bob, they do not constitute the general-purpose algorithm we desire. What we need is an algorithm that can sort this list as well as other lists we might encounter. This is not to say that our solution for sorting a particular list is totally worthless in our search for a general- purpose algorithm. We might, for instance, get our foot in the door by considering such special cases in an attempt to find general principles that can in turn be used to develop the desired general-purpose algorithm. In this case, then, our solution is obtained by the technique of solving a collection of related problems. Page 170 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 95 95. Algorithm: Algorithm Discovery Strategies (II) Another approach to getting a foot in the door is to apply stepwise refinement, which is essentially the technique of not trying to conquer an entire task (in all its detail) at once. Rather, stepwise refinement proposes that one first view the problem at hand in terms of several subproblems. The idea is that by breaking the original problem into subproblems, one is able to approach the overall solution in terms of steps, each of which is easier to solve than the entire original problem. In turn, stepwise refinement proposes that these steps be decomposed into smaller steps and these smaller steps be broken into still smaller ones until the entire problem has been reduced to a collection of easily solved subproblems. In this light, stepwise refinement is a top-down methodology in that it progresses from the general to the specific. In contrast, a bottom-up methodology progresses from the specific to the general. Although contrasting in theory, the two approaches often complement each other in creative problem solving. The decomposition of a problem proposed by the top-down methodology of stepwise refinement is often guided by the problem solver’s intuition, which might be working in a bottom-up mode. Page 171 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 96 96. Algorithm: Iterative Structures (Sequential Search Algorithm) Consider the problem of searching within a list for the occurrence of a particular target value. We want to develop an algorithm that determines whether that value is in the list. If the value is in the list, we consider the search a success; otherwise we consider it a failure. We assume that the list is sorted according to some rule for ordering its entries. For example, if the list is a list of names, we assume the names appear in alphabetical order, or if the list consists of numeric values, we assume its entries appear in order of increasing magnitude. To get our foot in the door, we imagine how we might search a guest list of perhaps 20 entries for a particular name. In this setting we might scan the list from its beginning, comparing each entry with the target name. If we find the target name, the search terminates as a success. However, if we reach the end of the list without finding the target value, our search terminates as a failure. In fact, if we reach a name greater than (alphabetically) the target name without finding the target, our search terminates as a failure. (Remember, the list is arranged in alphabetical order, so reaching a name greater than the target name indicates that the target does not appear in the list.) In summary, our rough idea is to continue searching down the list as long as there are more names to be investigated and the target name is greater than the name currently being considered. In our pseudocode, this process can be represented as Select the first entry in the list as TestEntry. while (TargetValue > TestEntry and entries remain): Select the next entry in the list as TestEntry Upon terminating this while structure, one of two conditions will be true; Either the target value has been found or the target value is not in the list. In either case we can detect a successful search by comparing the test entry to the target value. If they are equal, the search has been successful. Thus, we add the statement if (TargetValue == TestEntry): Declare the search a success. else: Declare the search a failure. to the end of our pseudocode routine. Finally, we observe that the first statement in our routine, which selects the first entry in the list as the test entry, is based on the assumption that the list in question contains at least one entry. We might reason that this is a safe guess, but just to be sure, we can position our routine as the else option of the statement if (List is empty): Declare search a failure. else:... This produces the function shown in Figure 82. Note that this function can be used from within other functions by using statements such as Search() the passenger list using Darrel Baker as the target value. to find out if Darrel Baker is a passenger and Page 172 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Search() the list of ingredients using nutmeg as the target value. to find out if nutmeg appears in the list of ingredients. Figure 82: The sequential search algorithm in pseudocode Page 173 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 97 97. Algorithm: Iterative Structures (Loop Control) The repetitive use of an instruction or sequence of instructions is an important algorithmic concept. One method of implementing such repetition is the iterative structure known as the loop, in which a collection of instructions, called the body of the loop, is executed in a repetitive fashion under the direction of some control process. A typical example is found in the sequential search algorithm represented in Figure 82. Here we use a while statement to control the repetition of the single statement Select the next entry in List as the TestEntry. Indeed, the while statement. while (condition): Body exemplifies the concept of a loop structure in that its execution traces the cyclic pattern check the condition. execute the body. check the condition. execute the body.... check the condition. until the condition fails. As a general rule, the use of a loop structure produces a higher degree of flexibility that would be obtained merely by explicitly writing the body several times. For example, to execute the statement Add a drop of sulfuric acid, three times, we could write: Add a drop of sulfuric acid. Add a drop of sulfuric acid. Add a drop of sulfuric acid. But we cannot produce a similar sequence that is equivalent to the loop structure. while (the pH level is greater than 4): add a drop of sulfuric acid because we do not know in advance how many drops of acid will be required. Let us now take a closer look at the composition of loop control. You might be tempted to view this part of a loop structure as having minor importance. After all, it is typically the body of the loop that actually performs the task at hand (for example, adding drops of acid)—the control activities appear merely as the overhead involved because we chose to execute the body in a repetitive fashion. However, experience has shown that the control of a loop is the more error-prone part of the structure and therefore deserves our attention. Page 174 of 381 Copyright Virtual University of Pakistan Introduction to Computing – CS101 VU Module 98 98. Algorithm: Iterative Structures (Components of Repetitive Control) The control of a loop consists of the three activities initialize, test, and modify (Figure 83), with the presence of each being required for successful loop control. The test activity has the obligation of causing the termination of the looping process by watching for a condition that indicates termination should take place. This condition is known as the termination condition. It is for the purpose of this test activity that we provide a condition within each while statement of our pseudocode. In the case of the while statement, however, the condition stated is the condition under which the body of the loop should be executed—the termination condition is the negation of the condition appearing in the while structure. Thus, in the statement while (the pH level is greater than 4): add a drop of sulfuric acid the termination condition is “the pH level is not greater than 4,” and in the while statement of Figure 82, the termination condition could be stated as (TargetValue