CS101 Final Term Highlighted Handouts PDF

INTRODUCION TO COMPUTING CS101 FINAL TERM HIGHLIGHTED HANDOUTS For video lectures visit our YouTube Channel VU Supreme Taleem Join VU Group: https://chat.whatsapp.com/K8O1b4yN8XiLTwEPUdXwVq ...

INTRODUCION TO COMPUTING CS101 FINAL TERM HIGHLIGHTED HANDOUTS For video lectures visit our YouTube Channel VU Supreme Taleem Join VU Group: https://chat.whatsapp.com/K8O1b4yN8XiLTwEPUdXwVq  Machine Language Assembly Language High level languages Programs for modern computers consist of sequences of instructions that are encoded as numeric digits. Such an encoding system is known as a machine language. Unfortunately, writing programs in a machine language is a tedious task that often leads to errors that must be located and corrected (a process known as debugging) before the job is finished.  Using Mnemonics and descriptive names In the 1940s, researchers simplified the programming process by developing notational systems by which instructions could be represented in mnemonic rather than numeric form. For example, the instruction Move the contents of register 5 to register 6 Machine codes 4056 using the machine language introduced, 1 Load 3 Store Whereas in a mnemonic system it might appear as MOV R5, R6 4 Move 5 Add As a more extensive example, the machine language routine Machine Language Assembly Language 156C LD R5, Price 166D LD R6, ShippingCharge 5056 ADDI R0, R5 R6 306E ST R0, TotalCost C000 HLT Which adds the contents of memory cells 6C and 6D and stores the result at location 6E Note: 156C loads register 5 with bit pattern found in memory cell at address 6C using mnemonics. (Here we have used LD, ADDI, ST, and HLT to represent load, add, store, and halt. Moreover, we have used the descriptive names Price, ShippingCharge, and TotalCost to refer to the memory cells at locations 6C, 6D, and 6E, respectively. Such descriptive names are often called program variables or identifiers.) Note that the mnemonic form, although still lacking, does a better job of representing the meaning of the routine than does the numeric form. Join VU Group: https://chat.whatsapp.com/K8O1b4yN8XiLTwEPUdXwVq   Assemblers Once such a mnemonic system was established, programs called assemblers were developed to convert mnemonic expressions into machine language instructions. Thus, rather than being forced to develop a program directly in machine language, a human could develop a program in mnemonic form and then have it converted into machine language by means of an assembler. MOV R5, R6 to 4056  Assembly language A mnemonic system for representing programs is collectively called an assembly language. At the time assembly languages were first developed, they represented a giant step forward in the search for better programming techniques. In fact, assembly languages were so revolutionary that they became known as second-generation languages, the first generation being the machine languages themselves.  Assembly language disadvantages Although assembly languages have many advantages over their machine language counterparts, they still fall short of providing the ultimate programming environment. After all, the primitives used in an assembly language are essentially the same as those found in the corresponding machine language. The difference is simply in the syntax used to represent them. Thus, a program written in an assembly language is inherently machine dependent – that is, the instructions within the program are expressed in terms of a particular machine’s attributes. In turn, a program written in assembly language cannot be easily transported to another computer design because it must be rewritten to conform to the new computer’s register configuration and instruction set. Another disadvantage of an assembly language is that a programmer, although not required to code instructions in numeric form, is still forced to think in terms of the small, incremental steps of the machine’s language. (Low level primitives) The situation is analogous to designing a house in terms of boards, nails, bricks, and so on. It is true that the actual construction of the house ultimately requires a description based on these elementary pieces, but the design process is easier if we think in terms of larger units such as rooms, windows, doors, and so on. In short, the elementary primitives in which a product must ultimately be constructed are not necessarily the primitives that should be used during the product’s design. The design process is better suited to the use of high-level primitives, each representing a concept associated with a major feature of the product. Once the design is complete, these primitives can be translated to lower-level concepts relating to the details of implementation.  Machine Independent Following this philosophy, computer scientists began developing programming languages that were more conducive to software development than were the low-level assembly languages. The result was the emergence of a third generation of programming languages that differed from previous generations in that their primitives were both higher level (in that they expressed instructions in larger increments) and machine independent (in that they did not rely on the characteristics of a particular machine). The best known early examples are FORTRAN (FORmula TRANslator), which was developed for scientific and engineering applications, and COBOL (COmmon Business-Oriented Language), which was developed by the U.S. Navy for business applications. In general, the approach to third-generation programming languages was to identify a collection of high level primitives in which software could be developed. Each of these primitives was designed so that it could be implemented as a sequence of the low-level primitives available in machine languages. For example, the statement TotalCost = Price + ShippingCharge expresses a high-level activity without reference to how a particular machine should perform the task, yet it can be implemented by the sequence of machine instructions discussed earlier. Thus, our pseudocode structure identifier = expression is a potential high-level primitive. Join VU Group: https://chat.whatsapp.com/K8O1b4yN8XiLTwEPUdXwVq   Translators Once this collection of high-level primitives had been identified, a program, called a translator, was written that translated programs expressed in these high-level primitives into machine-language programs. Such a translator was similar to the second-generation assemblers, except that it often had to compile several machine instructions into short sequences to simulate the activity requested by a single high-level primitive.  Compilers Translators, which compile several machine instructions into short sequences to simulate the activity requested by a single high-level primitive. Such Translation programs were often called compilers.  Interpreters An alternative to translators, called interpreters, emerged as another means of implementing third generation languages. These programs were similar to translators except that they executed the instructions as they were translated instead of recording the translated version for future use. That is, rather than producing a machine-language copy of a program that would be executed later, an interpreter actually executed a program from its high-level form. As a side issue, we should note that the task of promoting third-generation programming languages was not as easy as might be imagined. The thought of writing programs in a form similar to a natural language was so revolutionary that many in managerial positions fought the notion at first. Grace Hopper, who is recognized as the developer of the first compiler, often told the story of demonstrating a translator for a third-generation language in which German terms, rather than English, were used. The point was that the programming language was constructed around a small set of primitives that could be expressed in a variety of natural languages with only simple modifications to the translator. But she was surprised to find that many in the audience were shocked that, in the years surrounding World War II, she would be teaching a computer to “understand” German.  Natural languages and formal languages Today we know that understanding a natural language involves much more than responding to a few rigorously defined primitives. Indeed, natural languages (such as English, German, and Latin) evolved over time without formal grammatical analysis. Formal languages (such as programming languages) are precisely defined by grammars.  Goal of machine independence With the development of third-generation languages, the goal of machine independence was largely achieved. Since the statements in a third-generation language did not refer to the attributes of any particular machine, they could be compiled as easily for one machine as for another.  A program written in a third generation language could theoretically be used on any machine simply by applying the appropriate compiler. When a compiler is designed, particular characteristics of the underlying machine are sometimes reflected as conditions on the language being translated.  The different ways in which machines handle I/O operations have historically caused the “same” language to have different characteristics, or dialects, on different machines.  Consequently, it is often necessary to make at least minor modifications to a program to move it from one machine to another. Compounding this problem of portability is the lack of agreement in some cases as to what constitutes the correct definition of a particular language.  Standardization  To aid in this regard, the American National Standards Institute and the International Organization for Standardization have adopted and published standards for many of the popular languages. Join VU Group: https://chat.whatsapp.com/K8O1b4yN8XiLTwEPUdXwVq   In other cases, informal standards have evolved because of the popularity of a certain dialect of a language and the desire of other compiler writers to produce compatible products.  Language Extensions  Compiler designers often provide features, sometimes called language extensions that are not part of the standard version of the language.  If a programmer takes advantage of these features, the program produced will not be compatible with environments using a compiler from a different vendor, makes the code machine dependent In the overall history of programming languages, the fact that third generation languages fell short of true machine independence is actually of little significance for two reasons. First, they were close enough to being machine independent that software could be transported from one machine to another with relative ease. Second, the goal of machine independence turned out to be only a seed for more demanding goals. Indeed, the realization that machines could respond to such high level statements as The generation approach to classifying programming languages is based on a linear scale on which a language’s position is determined by the degree to which the user of the language is freed from the world of computer gibberish and allowed to think in terms associated with the problem being solved.  What are programming paradigms? It is Fundamental style of computer programming. It serves as a pattern or model of a programming language. In reality, the development of programming languages has not progressed in this manner but has developed along different paths as alternative approaches to the programming process (called programming paradigms) have surfaced and been pursued. Generations of programming languages Consequently, the historical development of programming languages is better represented by a multiple- track diagram, in which different paths resulting from different paradigms are shown to emerge and progress independently. In particular, the figure presents four paths representing the functional, object- oriented, imperative, and declarative paradigms, with various languages associated with each paradigm positioned in a manner that indicates their births relative to other languages. (It does not imply that one language necessarily evolved from a previous one.) Join VU Group: https://chat.whatsapp.com/K8O1b4yN8XiLTwEPUdXwVq We should note that although the paradigms identified called programming paradigms, these alternatives have ramifications beyond the programming process. They represent fundamentally different approaches to building solutions to problems and therefore affect the entire software development process. In this sense, the term programming paradigm is a misnomer. A more realistic term would be software development paradigm.  Imperative paradigm The imperative paradigm, also known as the procedural paradigm, represents the traditional approach to the programming process. It is the paradigm on which Python and our pseudocode are based as well as the machine language. As the name suggests, the imperative paradigm defines the programming process to be the development of a sequence of commands that, when followed, manipulate data to produce the desired result. Thus, the imperative paradigm tells us to approach the programming process by finding an algorithm to solve the problem at hand and then expressing that algorithm as a sequence of commands.  Develops a sequence of commands that when followed, manipulate data to produce the desired result  Approaches a problem by trying to find an algorithm for solving it  Declarative paradigm In contrast to the imperative paradigm is the declarative paradigm, which asks a programmer to describe the problem to be solved (what) rather than an algorithm to be followed (How). More precisely, a declarative programming system applies a pre-established general-purpose problem-solving algorithm to solve problems presented to it. In such an environment the task of a programmer becomes that of developing a precise statement of the problem rather than of describing an algorithm for solving the problem.  Emphasizes “What is the problem?” Rather than “What algorithm is required to solve the problem?  Implemented a general problem-solving algorithm  Obstacles A major obstacle in developing programming systems based on the declarative paradigm is the need for an underlying problem-solving algorithm. Knowing the generic algorithm and then implementing it. For this reason, early declarative programming languages tended to be special-purpose in nature, designed for use in particular applications or softwares. For example, the declarative approach has been used for many years to simulate a system (political, economic, environmental, and so on) in order to test hypotheses or to obtain predictions. In these settings, the underlying algorithm is essentially the process of simulating the passage of time by repeatedly re-computing values of parameters (gross domestic product, trade deficit, and so on) based on the previously computed values.  Weather forecasteing Join VU Group: https://chat.whatsapp.com/K8O1b4yN8XiLTwEPUdXwVq Thus, implementing a declarative language for such simulations requires that one first implement an algorithm that performs this repetitive function. Then the only task required of a programmer using the system is to describe the situation to be simulated. In this manner, a weather forecaster does not need to develop an algorithm for forecasting the weather but merely describes the current weather status, allowing the underlying simulation algorithm to produce weather predictions for the near future.  Logic programming A tremendous boost was given to the declarative paradigm with the discovery that the subject of formal logic within mathematics provides a simple problem- solving algorithm suitable for use in a general purpose declarative programming system. The result has been increased attention to the declarative paradigm and the emergence of logic programming. Another programming paradigm is the functional paradigm. Under this paradigm a program is viewed as an entity that accepts inputs and produces outputs. Mathematicians refer to such entities as functions, which is the reason this approach is called the functional paradigm. Under this paradigm a is program constructed by connecting smaller predefined program units (predefined functions) so that each unit’s outputs are used as another unit’s inputs in such a way that the desired overall input-to-output relationship is obtained. In short, the programming process under the functional paradigm is that of building functions as nested complexes of simpler functions. As an example, shows how a function for balancing your checkbook can be constructed from two simpler functions. One of these, called Find_sum, accepts values as its input and produces the sum of those values as its output. The other, called Find_diff, accepts two input values and computes their difference. The structure displayed in Figure 6.3 can be represented in the LISP programming language (a prominent functional programming language) by the expression (Find_diff (Find_sum Old_balance Credits) (Find_sum Debits)) The nested structure of this expression (as indicated by parentheses) reflects the fact that the inputs to the function Find_diff are produced by two applications of Find_sum. The first application of Find_sum produces the result of adding all the Credits to the Old_balance. The second application of Find_sum computes the total of all Debits. Then, the function Find_diff uses these results to obtain the new checkbook balance. To more fully understand the distinction between the functional and imperative paradigms, let us compare the functional program for balancing a checkbook to the following pseudocode program obtained by following the imperative paradigm: Imperative program Functional program Total_credits = sum of all Credits Temp_balance = Old_balance + Total_credits Total_debits = sum of all Debits Balance = Temp_balance - Total_debits A function for checkbook balancing constructed from simpler functions Note that this imperative program consists of multiple statements, each of which requests that a computation be performed and that the result be stored for later use. Join VU Group: https://chat.whatsapp.com/K8O1b4yN8XiLTwEPUdXwVq In contrast, the functional program consists of a single statement in which the result of each computation is immediately channeled into the next. In a sense, the imperative program is analogous to a collection of factories, each converting its raw materials into products that are stored in warehouses. From these warehouses, the products are later shipped to other factories as they are needed. But the functional program is analogous to a collection of factories that are coordinated so that each produces only those products that are ordered by other factories and then immediately ships those products to their destinations without intermediate storage. This efficiency is one of the benefits proclaimed by proponents of the functional paradigm. Object oriented paradigm Another programming paradigm (and the most prominent one in today’s software development) is the object-oriented paradigm, which is associated with the programming process called object-oriented programming (OOP). Following this paradigm, a software system is viewed as a collection of units, called objects, each of which is capable of performing the actions that are immediately related to itself as well as requesting actions of other objects. Together, these objects interact to solve the problem at hand.  Developing a GUI As an example of the object-oriented approach at work, consider the task of developing a graphical user interface. In an object-oriented environment, the icons that appear on the screen would be implemented as objects. Each of these objects would encompass a collection of functions (called methods in the object- oriented vernacular) describing how that object is to respond to the occurrence of various events, such as being selected by a click of the mouse button or being dragged across the screen by the mouse. Thus, the entire system would be constructed as a collection of objects, each of which knows how to respond to the events related to it.  Difference of List in imperative and OO-Paradigm To contrast the object-oriented paradigm with the imperative paradigm, consider a program involving a list of names. In the traditional imperative paradigm, this list would merely be a collection of data. Any program unit accessing the list would have to contain the algorithms for performing the required manipulations. In the object-oriented approach, however, the list would be constructed as an object that consisted of the list together with a collection of methods for manipulating the list. You need your algorithm for searching, sorting etc in imperative, however, in OO-paradigm; all functionality will be available along with the list in terms of object Its significance in today’s software development arena dictates that we include the concept of a class in this introduction. To this end, recall that an object can consist of data (such as a list of names) together with a collection of methods for per- forming activities (such as inserting new names in the list). These features must be described by statements in the written program. This description of the object’s properties is called a class. Once a class has been constructed, it can be applied anytime an object with those characteristics is needed. Thus, several objects can be based on (that is, built from) the same class. Just like identical twins, these objects would be distinct entities but would have the same characteristics because they are constructed from the same template (the same class). (An object that is based on a particular class is said to be an instance of that class.) High-level programming languages allow locations in main memory to be referenced by descriptive names rather than by numeric addresses. Such a name is known as a variable, in recognition of the fact that by changing the value stored at the location, the value associated with the name changes as the program Join VU Group: https://chat.whatsapp.com/K8O1b4yN8XiLTwEPUdXwVq executes. These declarative statements also require that the programmer describe the type of data that will be stored at the memory location associated with the variable. Such a type is known as a data type.  Data Types 1. Integer refers to numeric data consisting of whole numbers, probably stored using two’s complement notation. 2. Float (sometimes called real) refers to numeric data that might contain values other than whole numbers, probably stored in floating-point notation. Operations performed on data of type float are similar to those performed on data of type integer. int Height, Width; int WeightLimit = 100; 3. Character refers to data consisting of symbols, probably stored using ASCII or Unicode. Operations performed on such data include comparisons such as determining whether one symbol occurs before another in alphabetical order, testing to see whether one string of symbols appears inside another, and concatenating one string of symbols at the end of another to form one long string. The statement char Letter, Digit; 4. Boolean refers to data items that can take on only the values true or false. Operations on data of type Boolean include inquiries as to whether the current value is true or false. For example, if the variable LimitExceeded was declared to be of type Boolean, then a statement of the form if (LimitExceeded) then (...) else (...) would be reasonable. The data types that are included as primitives in a programming language, such as int for integer and char for character, are called primitive data types. Data types such as: integer, float, character, and boolean are common primitives. Other data types that have not yet become widespread primitives include images, audio, video, and hypertext. However, types such as GIF, JPEG, and HTML might soon become as common as integer and float. In addition to data type, variables in a program are often associated with data structure, which is the conceptual shape or arrangement of data. For example: ✓ Name is a sequence of characters, ✓ Student marks in 5 subjects One common data structure is the array, which is a block of elements of the same type such as a one dimensional list, a two-dimensional table with rows and columns, or tables with higher dimensions. To establish such an array in a program, many programming languages require that the declaration statement declaring the name of the array also specify the length of each dimension of the array. For example, displays the conceptual structure declared by the statement int Scores; in the language C, which means “The variable Scores will be used in the following program unit to refer to a two-dimensional array of integers having two rows and nine columns.” The same statement in FORTRAN would be written as INTEGER Scores (2, 9) Once an array has been declared, it can be referenced elsewhere in the program by its name, or an individual element can be identified by means of integer values called indices that specify the row, column, and so on, desired. However, the range of these indices varies from language to language. For example, in C (and its derivatives C++, Java, and C#) indices start at 0, meaning that the entry in the second row and Join VU Group: https://chat.whatsapp.com/K8O1b4yN8XiLTwEPUdXwVq fourth column of the array called Scores (as declared above) would be referenced by Scores, and the entry in the first row and first column would be Scores. In contrast, indices start at 1 in a FORTRAN program so the entry in the second row and fourth column would be referenced by Scores(2,4). In contrast to an array in which all data items are the same type, an aggregate type (also called a structure, a record, or sometimes a heterogeneous array) is a block of data in which different elements can have different types. For instance, a block of data referring to an employee might consist of an entry called Name of type character, an entry called Age of type integer, and an entry called SkillRating of type float. Such an aggregate type would be declared in C by the statement struct {char Name; int Age; float SkillRating; } Employee; which says that the variable Employee is to refer to a structure (abbreviated struct) consisting of three components called Name (a string of 25 characters), Age, and SkillRating (Figure 95). Once such an aggregate has been declared, a programmer can use the structure name (Employee) to refer to the entire aggregate or can reference individual fields within the aggregate by means of the structure name followed by a period and the field name (such as Employee.Age). Once the special terminology to be used in a program (such as the variables and constants) has been declared, a programmer can begin to describe the algorithms involved. This is done by means of imperative statements. The most basic imperative statement is the assignment statement, which requests that a value be assigned to a variable (or more precisely, stored in the memory area identified by the variable). Such a statement normally takes the syntactic form of a variable, followed by a symbol representing the assignment operation, and then by an expression indicating the value to be assigned. The semantics of such a statement is that the expression is to be evaluated and the result stored as the value of the variable. For example, the statement: Z = X + Y; in C, C++, C#, and Java requests that the sum of X and Y be assigned to the variable Z. The semicolon at the end of the line, which is used to separate statements in many imperative languages, is the only syntactic difference from an equivalent Python assignment statement. In some other languages (such as Ada) the equivalent statement would appear as: Join VU Group: https://chat.whatsapp.com/K8O1b4yN8XiLTwEPUdXwVq Z := X + Y; A control statement alters the execution sequence of the program. it determines whether other statements will be executed or not. if (condition) Statement A else Statement B For example, if a student’s gets more than or equal to 50 marks, the student passes the examination. To denote this using the if-statement, we will proceed as follow: if (marks>=50) You have passed the examination Else You have failed the examination The result is the practice known as structured programming, which encompasses an organized design methodology combined with the appropriate use of the language’s control statements. In this module, we will learn another example. Suppose a university wants to give a scholarship, if a student gets more than 3.0 CGPA in a given semester. We can write the program in the following way and you have also seen its implementation in the videos in the online compiler. float CGPA=3.5; If (CGPA>=3.0) cout