Computer Programming 1 Past Paper PDF

**COMPUTER PROGRAMMING 1 \[CIT 202\]** **PROBLEM SOLVING PROCESS** Problem solving is a process whereby a "best" outcome is determined for some situation, subject to certain constraints. Many models for problem solving exist, differing in their emphasis and in the sequence of steps employed. The s...

**COMPUTER PROGRAMMING 1 \[CIT 202\]** **PROBLEM SOLVING PROCESS** Problem solving is a process whereby a "best" outcome is determined for some situation, subject to certain constraints. Many models for problem solving exist, differing in their emphasis and in the sequence of steps employed. The steps in some of the models are more difficult to employ than others, making them less accessible to less experienced practitioners. There are two distinct types of problem solving: analytical and open-ended. Analytical problem solving yields one correct answer and therefore tends to be more discipline-specific, whereas Open-ended or creative problem solving can lead to multiple solutions and therefore draws on a wide variety of cognitive, affective, and social skills. The problem-solving process includes several steps which are considered together as an important life skill (Anderson, 2009). They are; i. Problem identification, ii. Information gathering, iii. Problem resolution to identify the root problem, iv. Identification of possible solutions, v. Determination of the best solution, and vi. Problem solution (Mayer, 1998) **What Constitutes a Problem?** What we call a problem is a real challenge; it is a situation where we really have to struggle to define it, figure out what it means, and resolve it". Problems will always occur no matter what situation you are in, so it's important to know how to conquer them before they get out of hand. **Problem Solving** It can be said that whatever activity a human being or machine do for achieving a specified objective comes under problem solving. Example (a) If someone asks to you, what is time now? So seeing time in your watch and telling him is also a kind of problem solving. (b) Some students in a class plan to go on picnic and decide to share the expenses among them. So calculating total expenses and the amount an individual have to give for picnic is also a kind of problem solving. A problem is a kind of barrier to achieve something and problem solving is a process to get that barrier removed by performing some sequence of activities. Here it is necessary to mention that all the problems in the world cannot be solved. There are some problems which have no solution and these problems are called Open Problems. If you can solve a given problem then you can also write an algorithm for it. Five Steps to Better Problem-Solving Step 1: Identify the Problem:- The first step in the problem-solving process is to identify the root of the issue. Unfortunately, the problem isn't always easily identifiable and requires extra analysis to get the source. One method used in this step is Toyota's "Five Whys" technique. In the event of a problem, ask yourself the five whys: Who, What, When, Why, and Where. By asking yourself these questions in associations with the problem, you will discover exactly where the problem is coming from. If that isn't enough, there are three steps you can take to better identify a problem. i. Explore the situation: Expand on the problem to try to get to the bottom of it. If the source of the problem is coming from an individual, try putting yourself in their shoes ii. Draft a problem statement: Reduce the problem into the simplest of terms and put it on paper iii. Try to answer the question: "why is this current situation a problem?"- Once you've boiled it down to one source, you will then be able to better assess the situation better Step 2: Generate potential solutions:- The next step is to create a list of possible solutions to the problem you've discovered. There are many ways to generate solutions. i. **Brainstorming:-** is the first way to think of a potential answer. This can be done individually or in a group setting. The latter is recommended, because the more input, the better, simply because different perspectives can lead to different solutions. ii. **Means-End Analysis:-** An artificial intelligence analysis that looks at the ultimate goal and finds the best possible way of attaining that goal iii. **PDSA Model\[Plan Do Study Act Model\]:-** This is the shorthand version of the problem-solving method, where you start with planning, test the theory, study the results, and act based upon observations. This process is done several times iv. **Root Cause Analysis:-**  This method is used to get to the root of the problem. There are four steps to find the root cause. Identify the problem, establish a timeline, distinguish between root causes and other factors, and create a cause graph v. **Lean Prioritization Method:-** This method is created within a two by two matrix with the X and Y-axis ranging from low to high. The X-axis is labeled as effort, while the Y-axis is labeled value. Inside the two by two matrix label the four squares with quick wins, big bets, maybes, and time sinks. Evaluate all of the problems and situations and put them in the appropriate categories to figure out where to focus your attention Step 3: Choose one solution:- Once a list of possible solutions has been made, it's time to put your decision-making skills to the test. In order to find the best solution for the problem, analyze every possible resolution and decide which is best for the situation you are in. One might want to consider many elements before choosing one solution. These elements include efficacy, practicality, timeliness, resources, cost and also, who is involved before making any final decisions. The process of elimination is another good way to narrow your choices down. This is also where risk management will be used to help make a decision. Step 4: Implement the solution you have chosen:- Now that a solution has been chosen, it's time to implement it throughout the necessary departments, areas, or people. On average, it takes about 66 days for a new habit to become automatic, according to a recent study that was published in the European Journal of Social Psychology. In other words, change doesn't happen overnight. To make a new change to any business, planning, patience, and persistence are all required. Step 5: Evaluate results:- The final part of the problem-solving process is to analyze the results. This can be done after a couple of weeks, months, or years, depending on what you are trying to change or achieve. It's important to remember why this problem started in the first place and how it was affecting the company. To make the problem-solving process easier, it's best to simplify the solution as much as possible. Try to focus on the solution rather than the problem. Finally, be in the correct mentality to want to change. This includes having the right mindset language, both are positive and open-minded. With enough practice, any problem can be solved. **PROBLEM IDENTIFICATION** Duncker (1945) states that a problem arises, when a person has a specific aim but he/she does not know how to achieve it. However, this statement is only one of the possible cases since a problematic relation does not have to be primarily based on the aim of the person, but also on the difficulties and inner uncertainty. The individual is aware of the problem that has already arisen and then he/she establishes the aims to remove the difficulties and uncertainty causing the burdensome feeling. The problem is defined by a relation between the subject and objective situation in the environment. A problematic relation has a nature of: a)either a conflict between two contradictory tendencies which the subject sees as two incompatible alternatives, or as a difference or conflict between the current situation and the aim; the subject needs to achieve the aim but he/she does not know the means to achieve it -- the result is \"a perceived inconsistency\" of the situation; the problem solving consists of the removal of the conflict and the finding of the desired object. b\) a disorder in the objective situation or in the structure of an activity and subjective uncertainty that causes activating tension and motivating focus. J. Linhart (1976, p 385), defines the problematic situation as a totality of conditions that determine the formation and specifics of the problem while I. J. Lerner (1986, p. 91) defines it as a barrier that subject is clearly or indefinitely aware of and to its overcoming he/she needs a creative search of the new knowledge, new ways and activities. However, the barrier is not the only element of the problematic situation - this role is played by the other factors as well. Analysing the different problematic situations, we draw a conclusion that they are characterized by diversity and it is possible to divide them in the groups based on the similar signs. **FORMAL REPRESENTATION OF THE PROBLEM** Problems can be represented by writing a Problem Statement. A problem statement is usually one or two sentences to explain the problem your process improvement project will address. In general, a problem statement will outline the negative points of the current situation and explain why this matters. It also serves as a great communication tool, helping to get buy­ing and support from others. One of the most important goals of any problem statement is to define the problem being addressed in a way that\'s clear and precise. Its aim is focus the process improvement team's activities and steer the scope of the project. Creation of a problem statement is an activity that is best completed in a small group (4­6 people). It is helpful to have a couple of people who are involved in the process and a process owner involved in the activity. 1\. Get each person to write his or her own problem statement without conferring. Compare each of the sentences/ looking for common themes and wording. 2\. Start to write an improved statement using the common themes. 3\. Ensure that the problems include the customer's perspective 4\. Ensure that the statement focuses on existing problems. 5\. Try to include the time frame over which the problem has been occurring. 6\. Try to quantify the problem. If you do not have the data to hand, defer writing the final problem statement until you have been able to quantify the problem. You should be able to apply the 5 \'W\'s (Who, What, Where, When and Why) to the problem statement. A problem statement can be refined as you start to further investigate root cause. Finally, review your new problem statement against the following criteria: i. It should focus on only one problem. ii. It should be one or two sentences long. iii. It should not suggest a solution. **CONCEPT AND PROPERTIES OF ALGORITHMS** The term algorithm originally referred to any computation performed via a set of rules applied to numbers written in decimal form. The word is derived from the phonetic pronunciation of the last name of Abu Ja\'far Mohammed ibn Musa al-Khowarizmi, who was an Arabic mathematician who invented a set of rules for performing the four basic arithmetic operations (addition, subtraction, multiplication and division) on decimal numbers. **Procedure:** A procedure is a finite sequence of well-defined instructions, each of which can be mechanically carried out in a finite amount of time. **Algorithm:** An algorithm is procedure consisting of a finite set of unambiguous rules (instructions) which specify a finite sequence of operations that provides the solution to a problem, or to a specific class of problems for any allowable set of input quantities (if there are inputs). In other word, an algorithm is a step-by-step procedure to solve a given problem. Alternatively, we can define an algorithm as a set or list of instructions for carrying out some process step by step. A recipe in a cookbook is an excellent example of an algorithm. The recipe includes the requirements for the cooking or ingredients and the method of cooking them until you end up with a nice cooked dish. It is a well-known fact of programming life that if the algorithm construction is not done well, a programmer will probably spend excessive amounts of time debugging, i.e. finding and fixing errors in the program. Algorithms are written during the programming process, which involves the steps below: i. Problem analysis ii. Algorithm construction iii. Translation of algorithm into programming language iv. Testing and debugging of the program **Properties of Algorithm** Donald Ervin Knuth has given a list of five properties for algorithm, these properties are: 1\) **Finiteness:** An algorithm must always terminate after a finite number of steps. 2\) **Definiteness:** Each step of an algorithm must be precisely defined. It is done by well thought actions to be performed at each step of the algorithm. Also the actions are defined unambiguously for each activity in the algorithm. 3\) **Input:** Any operation you perform need some beginning value/quantities associated with different activities in the operation. So the value/quantities are given to the algorithm before it begins. 4\) **Output:** The output is expected value/quantities always have a specified relation to the inputs 5\) **Effectiveness:** Algorithms to be developed/written using basic operations. Actually operations should be basic, so that even they can in principle be done exactly and in a finite amount of time by a person, by using paper and pencil only. Three reasons for using algorithms are efficiency, abstraction and reusability. **Efficiency:** Certain types of problems, like sorting, occur often in computing. Efficient algorithms must be used to solve such problems considering the time and cost factor involved in each algorithm. **Abstraction:** Algorithms provide a level of abstraction in solving problems because many seemingly complicated problems can be distilled into simpler ones for which well-known algorithms exist. Once we see a more complicated problem in a simpler light, we can think of the simpler problem as just an abstraction of the more complicated one. For example, imagine trying to find the shortest way to route a packet between two gateways in an internet. Once we realize that this problem is just a variation of the more general shortest path problem, we can solve it using the generalized approach. **Reusability:** Algorithms are often reusable in many different situations. Since many well-known algorithms are the generalizations of more complicated ones, and since many complicated problems can be distilled into simpler ones, an efficient means of solving certain simpler problems potentially lets us solve many complicated problems. **Constructing Algorithms** **1) Understand the problem:-** A common mistake is to start writing an algorithm before the problem to be solved is fully understood. Among other things, understanding the problem involves knowing the answers to the following questions. a. What is the input list, i.e. what information will be required by the algorithm? b. What is the desired output or result? c. What are the initial conditions? **2) Devise a Plan:-** The first step in devising a plan is to solve the problem yourself. Arm yourself with paper and pencil and try to determine precisely what steps are used when you solve the problem \"by hand\". Force yourself to perform the task slowly and methodically. Do not use your own memory, introduce variables when you need to remember information used by the algorithm. Using the information gleaned from solving the problem by hand, devise an explicit step-by-step method of solving the problem. These steps can be written down in an informal outline form \-- it is not necessary at this point to use pseudocode. **3) Refine the Plan and Translate into Pseudocode:-** The plan devised in step 2) needs to be translated into pseudocode. This refinement may be trivial or it may take several \"passes\". **4) Test the Design Using appropriate test data:-** test the algorithm by going through it step by step. Think about ordinary sets of input data as well as those which are \"degenerate\". If you find errors correct them. If serious errors are found, it may be necessary to scrap your pseudo-code and go back to step 2). **ALGORITHM DEVELOPMENT USING PSEUDOCODES AND FLOWCHARTS** **FLOWCHART** Flowcharting is a tool developed in the computer industry, for showing the steps involved in a process. A flowchart is a diagram made up of boxes, diamonds and other shapes, connected by arrows - each shape represents a step in the process, and the arrows show the order in which they occur. Flowcharting combines symbols and flowlines, to show figuratively the operation of an algorithm. The first design of flowchart goes back to 1945 which was designed by John Von Neumann. Unlike an algorithm, Flowchart uses different symbols to design a solution to a problem. It is another commonly used programming tool. By looking at a Flowchart one can understand the operations and sequence of operations performed in a system. Flowchart is often considered as a blueprint of a design used for solving a specific problem. Flowchart is drawn according to defined rules. **Flowchart Symbols** There are 6 basic symbols commonly used in flowcharting: Terminal, Process, input/output, Decision, Connector and Predefined Process. Process Indicates any type of internal operation inside the Processor or Memory Decision - Used to ask a question that can be answered in a binary format (Yes/No, True/False) Connector - Allows the flowchart to be drawn without intersecting lines or without a reverse flow. Flow Lines - Shows direction of flow **General Rules for Flowcharting** 1\. All boxes of the flowchart are connected with Arrows. (Not lines) 2\. Flowchart symbols have an entry point on the top of the symbol with no other entry points. The exit point for all flowchart symbols is on the bottom except for the Decision symbol. 3\. The Decision symbol has two exit points; these can be on the sides or the bottom and one side. 4\. Generally a flowchart will flow from top to bottom. However, an upward flow can be shown as long as it does not exceed 3 symbols. 5\. Connectors are used to connect breaks in the flowchart. Examples are: From one page to another page. From the bottom of the page to the top of the same page. An upward flow of more than 3 symbols 6\. Subroutines and Interrupt programs have their own and independent flowcharts. 7\. All flow charts start with a Terminal or Predefined Process (for interrupt programs or subroutines) symbol. 8\. All flowcharts end with a terminal or a contentious loop. Flowcharting uses symbols that have been in use for a number of years to represent the type of operations and/or processes being performed. The standardized format provides a common method for people to visualize problems together in the same manner. The use of standardized symbols makes the flow charts easier to interpret, however, standardizing symbols is not as important as the sequence of activities that make up the process. **Advantages of Using Flowcharts** These advantages are as follows: **1) Communication:** A Flowchart can be used as a better way of communication of the logic of a system and steps involve in the solution, to all concerned particularly to the client of system. **2) Effective analysis:** A flowchart of a problem can be used for effective analysis of the problem. **3) Documentation of Program/System:** Program flowcharts are a vital part of a good program documentation. Program document is used for various purposes like knowing the components in the program, complexity of the program etc. **4) Efficient Program Maintenance:** Once a program is developed and becomes operational it needs time to time maintenance. With help of flowchart, maintenance becomes easier. **5) Coding of the Program:** Any design of solution of a problem is finally converted into computer program. Writing code referring the flowchart of the solution become easy. **Limitations of Using Flowcharts** Although a flowchart is a very useful tool, there are a few limitations in using flowcharts which are listed below: **Complex logic:** Sometimes, the program logic is quite complicated. In that case, flowchart becomes complex and clumsy. **Alterations and Modifications:** If alterations are required the flowchart may require re-drawing completely. **When to Use a Flowchart:** - To communicate to others how a process is done. - A flowchart is generally used when a new project begins in order to plan for the project. - A flowchart helps to clarify how things are currently working and how they could be improved. - It also assists in finding the key elements of a process, while drawing clear lines between where one process ends and the next one starts. - Developing a flowchart stimulates communication among participants and establishes a common understanding about the process. - Flowcharts also uncover steps that are redundant or misplaced. - Flowcharts are used to help team members, to identify who provides inputs or resources to whom, to establish important areas for monitoring or data collection, to identify areas for improvement or increased efficiency, and to generate hypotheses about causes. - It is recommended that flowcharts be created through group discussion, as individuals rarely know the entire process and the communication contributes to improvement. - Flowcharts are very useful for documenting a process (simple or complex) as it eases the understanding of the process. - Flowcharts are also very useful to communicate to others how a process is performed and enables understanding of the logic of a process. **PSEUDOCODE** Pseudocode is a generic way of describing an algorithm without use of any specific programming language syntax. It is, as the name suggests, pseudo code ---it cannot be executed on a real computer, but it models and resembles real programming code, and is written at roughly the same level of detail. Pseudocode, by nature, exists in various forms, although most borrow syntax from popular programming languages (like C, Lisp, or FORTRAN). **Pseudocode Statements** At first, our language will have 6 types of statements. These are described below. 1\) Assignment statements are used to give a values to a variables. Various notation are used for assigning a value to a variable X, such as: assign X the value 0, set X to 0, X := 0, X = 0, N = 0, N = N + 1 2\) Input statements are used to get information from some external source, such as the users' keyboard. E.g. input X, input Number, read Number 3\) Output statements are used to display information determined by an algorithm. Two sorts of items may be displayed: the value of a variable or expression and a string of characters. Examples: **Examples of Algorithm** Problem 1: Find the area of a Circle of radius r. Inputs to the algorithm: Radius r of the Circle. Expected output: Area of the Circle Algorithm: Step1: Read\\input the Radius r of the Circle Step2: Area = PI\*r\*r // calculation of area Step3: Print Area Problem 2: Write an algorithm to read two numbers and find their sum. Inputs to the algorithm: First num1. Second num2. Expected output: Sum of the two numbers. Algorithm: Step1: Start Step2: Read\\input the first num1. Step3: Read\\input the second num2. Step4: Sum= num1+num2 // calculation of sum Step5: Print Sum Step6: End Problem 3: Convert temperature Fahrenheit to Celsius Inputs to the algorithm: Temperature in Fahrenheit Expected output: Temperature in Celsius Algorithm: Step1: Start Step 2: Read Temperature in Fahrenheit F Step 3: C= 5/9\*(F-32) Step 4: Print Temperature in Celsius: C Step5: End **CONTROL STRUCTURES** There are three main types of control structures used in algorithms: pseudocodes and flowcharts. They are: 1\. Sequence 2. Branching (Selection) 3. Loop (Repetition) These three control structures are sufficient for all purposes. 1\. **Sequence Structure:-** In the sequence structure, statements are placed one after the other and the execution takes place starting from up to down. In flowcharts, sequence of statements is usually contained in the rectangular process box. Example 1: This is the pseudocode required to input three numbers from the keyboard and output the result. Example 2: The following pseudocode describes an algorithm which will accept two numbers from the keyboard and calculate the sum and product displaying the answer on the monitor screen. **2. Selection Structure:** This constitutes a branch and it involves a binary decision based on some condition. If the condition is true, one of the two branches is explored; if the condition is false, the other alternative is taken. This is usually represented by the 'If-Then' construct in pseudo-codes and programs. In flowcharts, this is represented by the diamond-shaped decision box. Example 1: Write algorithm to find the greater number between two numbers Example 2: Write algorithm to find the result of equation: ( ) { Example 3: An algorithm to find the largest value of any three numbers. Example 4: The program is to input an examination mark and test it for the award of a grade. The mark is a whole number between 1 and 100. Grades are awarded according to the following criteria: The pseudo-code is: **3. Iteration/Loop/Repetition Structure:** The loop allows a statement or a sequence of statements to be repeatedly executed based on some loop condition. It is represented by the 'while' and 'for' constructs in most programming languages, for unbounded loops and bounded loops respectively. (**Unbounded loops** refer to those whose number of iterations depends on the eventuality that the termination condition is satisfied while **Bounded loops** refer to those whose number of iterations is known before-hand.) In the flowcharts, a back arrow hints the presence of a loop. A trip around the loop is known as iteration. Any program instruction that repeats some statement or sequence of statements a number of times is called an iteration or a loop. The commands used to create iterations or loops are all based on logical tests. You must ensure that the condition for the termination of the looping must be satisfied after some finite number of iterations, otherwise it ends up as an infinite loop, a common mistake made by inexperienced programmers. The Iteration/Loop/Repetition structure can be implemented using: i\) Repeat Until Loop ii) The While Loop and iii) The For Loop i\) **The Repeat Until loop:-** The syntax is REPEAT A statement or block of statements UNTIL a true condition Example 1: A program segment repeatedly asks for entry of a number in the range 1 to 100 until a number outside the range is entered. Example 2: Algorithm to read integers entered by user and find the sum. Input ends when a non-positive number is entered. ii\) **The WHILE loop:-** This type of conditional loop tests for terminating condition at the beginning of the loop. In this case no action is performed at all if the first test causes the terminating condition to evaluate as false. The syntax is: ENDWHILE Example 1: A program segment to print out each character typed at a keyboard until the character 'q' is entered. Example 2: Write a program that will output the square root of any number input until the number input is zero. Use variable: number of type real DISPLAY "Type in a number or zero to stop" ACCEPT number WHILE number \ 0 ENDWHILE Example 3: Algorithm to add numbers entered by user. iii\) **The FOR Loop:-** This type of iteration is used when the number of iterations is known in advance. This, in its simplest form, uses an initialization of the variable as a starting point, a stop condition depending on the value of the variable. The variable is incremented on each iteration until it reaches the required value. The pseudocode syntax will be: Example 1: DISPLAY "loop", n The fragment of code will produce the output In the example, n is usually referred as the loop variable, or counting variable, or index of the loop. The loop variable can be used in any statement of the loop. The variable should not be assigned a new value within the loop, which may change the behaviour of the loop. Example 2: Write a program to calculate the sum and average of a series of numbers. The pseudocode solution is: Example 3: Algorithm to read 10 integers entered by user and find their sum. Input ends after the 10th number is entered. **More Statements used in Algorithms (Pseudocodes and Flowcharts)** 1\. The **If-Then statement** allows other statements to be executed conditionally, i.e. if a certain condition is met. The If-Then statement is of the form If Then End If. The \"End If\" serves a delimiter, to mark the end of the statements to be executed if the condition is true. Example 1: Example 2: 2\) **The If-Then-Else** statement is a more powerful version of the If-Then statement. It is of the form: If Then Else End If Example: **Note:** The REPEAT LOOP is usually best if you are constructing a loop that will execute indefinite number of times, but at least once. (Repeat 1 or more times). The WHILE LOOP is usually best if you are constructing a loop that will execute indefinite number of times, and possibly not at all. (Repeats 0 or more times). The FOR LOOP is usually best if you are constructing a loop, and you know exactly how many times the loop has to execute. **More Algorithm Examples** Example 1: An algorithm that asks for a number, then prints its square. Example 2: An algorithm that asks for a number, then tells whether it is odd or even. Example 3: An algorithm which finds the sum of a list of 10 numbers. Example 4: Design an algorithm and the corresponding flowchart for finding the sum of n numbers. **Advantages of Algorithm** i. It is a step-wise representation of a solution to a given problem, which makes it easy to understand. ii. An algorithm uses a definite procedure. iii. It is not dependent on any programming language, so it is easy to understand for anyone even without programming knowledge. iv. Every step in an algorithm has its own logical sequence so it is easy to debug. **ALGORITHM IMPLEMENTATION** **General Approaches in Algorithm Design** In a broad sense, many algorithms approach problems in the same way. Thus, it is often convenient to classify them based on the approach they employ. One reason to classify algorithms is to gain an insight about an algorithm and understand its general approach. This can also give us ideas about how to look at similar problems for which we do not know algorithms. Of course, some algorithms defy classification, whereas others are based on a combination of approaches. This section presents some common approaches. **1. Randomized Algorithms:** Randomized algorithms rely on the statistical properties of random numbers. One example of a randomized algorithm is quicksort. Imagine an unsorted pile of cancelled checks by hand. In order to sort this pile we place the checks numbered less than or equal to what we may think is the median value in one pile, and in the other pile we place the checks numbered greater than this. Once we have the two piles, we divide each of them in the same manner and repeat the process until we end up with one check in every pile. At this point the checks are sorted. **2. Divide-and-conquer Algorithms:** Divide-and-conquer algorithms revolve around 3 steps: divide, conquer and combine. In the divide step, we divide the data into smaller, more manageable pieces. In the conquer step, we process each division by performing some operations on it. In the combine step, we recombine the processed divisions. An example of the divide-and-conquer algorithm is merge sort. As before, imagine an unsorted pile of cancelled checks by hand. We begin by dividing the pile in half. Next, we divide each of the resulting two piles in half and continue this process until we end up with one check in every pile. Once all piles contain a single check, we merge the piles two by two so that each pile is a sorted combination of the two that were merged. Merging continues until we end up with one big pile again, at which point the checks are sorted. **3. Dynamic-programming solutions:** Dynamic-programming solutions are similar to divide-and-conquer methods in that both solve problems by breaking larger problems into sub-problems whose results are later recombined. However, the approaches differ in how sub-problems are related. In divide-and-conquer algorithms, each sub-problem is independent of the others. Therefore we solve each sub-problem using recursion and combine its results with the results of other sub-problems. In dynamic programming solutions, sub-problems are not independent of one another. A dynamic-programming solution is better than a divide-and-conquer approach because the latter approach will do more work than necessary, as shared sub-problems are solved more than once. However, if the sub-problems are independent and there is no repetition, using divide-and-conquer algorithms is much better than using dynamic-programming. An example of dynamic-programming is finding the shortest path to reach a point from a vertex in a weighted graph. **4. Greedy Algorithms:** Greedy algorithms make decisions that look best at the moment. In other words, they make decisions that are locally optimal in the hope that they will lead to globally optimal solutions. The greedy method extends the solution with the best possible decision at an algorithmic stage based on the current local optimum and the best decision made in a previous stage. It is not exhaustive, and does not give accurate answer to many problems. But when it works, it will be the fastest method. One example of a greedy algorithm is Huffman coding, which is an algorithm for data compression. **5. Approximation Algorithms:** Approximation algorithms are algorithms that do not compute optimal solutions; instead, they compute solutions that are "good enough". Often we use approximation algorithms to solve problems that are computationally expensive but are too significant to give up altogether. The travelling salesman problem is one example of a problem usually solved using an approximation algorithm. **Analysis of Algorithms** Whether we are designing an algorithm or applying one that is widely accepted, it is important to understand how the algorithm will perform. There are a number of ways we can look at an algorithm's performance, but usually the aspect of most interest is how fast the algorithm will run. In some cases, if an algorithm uses significant storage, we may be interested in its space requirement as well. Analysis of algorithms is the theoretical study of computer program performance and resource usage, and is often practiced abstractly without the use of specific programming language or implementation. The practical goal of algorithm analysis is to predict the performance of different algorithms in order to guide program design decisions. There are many reasons to understand the performance of an algorithm. For example, we often have a choice of several algorithms when solving problems (like sorting). Understanding how each performs helps us differentiate between them. Understanding the burden an algorithm places on an application also helps us plan how to use the algorithm more effectively. For instance, garbage collection algorithms, algorithms that collect dynamically allocated storage to return to the heap, require considerable time to run. Knowing this we can be careful to run them only at opportune moments, just as Java does, for example. Algorithm analysis is important in practice because the accidental or unintentional use of an inefficient algorithm can significantly impact system performance. In time-sensitive applications, an algorithm taking too long to run can render its results outdated or useless. An inefficient algorithm can also end up requiring an uneconomical amount of computing power or storage in order to run, again rendering it practically useless. **Worst-Case Analysis:** Most algorithms do not perform the same in all cases; normally an algorithm's performance varies with the data passed to it. Typically, three cases are recognized: the best case, average case and worst case. For any algorithm, understanding what constitutes each of these cases is an important part of analysis because performance can vary significantly between them. Consider a simple algorithm such as linear search. Linear search is a natural but inefficient search technique in which we look for an element simply by traversing a set from one end to the other. In the **best case**, the element we are looking for is the first element we inspect, so we end up traversing only a single element. In the **worst case**, however, the desired element is the last element that we inspect, in which we end up traversing all the elements. On **average**, we can expect to find the element somewhere in the middle. A basic understanding of how an algorithm performs in all cases is important, but usually we are most interested in how an algorithm performs in the worst case. There are four reasons why algorithms are generally analyzed by their worst case: Many algorithms perform to their worst case a large part of the time. For example, the worst case in searching occurs when we do not find what we are looking for at all. This frequently happens in database applications. The best case is not very informative because many algorithms perform exactly the same in the best case. For example, nearly all searching algorithms can locate an element in one inspection at best, so analyzing this case does not tell us much. Determining average-case performance is not always easy. Often it is difficult to determine exactly what the "average case" even is; since we can seldom guarantee precisely how an algorithm will be exercised. The worst case gives us an upper bound on performance. Analyzing an algorithm's worst case guarantees that it will never perform worse than what we determine. Therefore, we know that the other cases must perform at least better than the worst case. Worst case analysis of algorithms is considered to be crucial to applications such as games, finance and robotics. Although worst case analysis is the metric for many algorithms, it is worth noting that there are exceptions. Sometimes special circumstances let us base performance on the average case (for example quick-sort algorithm). **O-notation** O-notation, also known as Big O-notation, is the most common notation used to express an algorithm's performance in a formal manner. Formally, O-notation expresses the upper bound is a function within a constant factor. Specifically, if g(n) is an upper bound of f(n), then for some constant c it is possible to find the value of n, call it n~0~, for which any value of n≥n~0~ will result in f(n)≤cg(n). Normally we express an algorithm's performance as a function of the size of the data it processes. That is, for some data of size n, we describe its performance with some function f(n). Primarily we are interested only in the growth rate of f, which describes how quickly the algorithm's performance will degrade as the size of data it processes becomes arbitrarily large. An algorithm's growth rate, or order of growth, is significant because ultimately it describes how efficient the algorithm is for arbitrary inputs. O-notation reflects an algorithm's order of growth. **Simple Rules for O-notation** O-notation lets us focus on the big picture. When faced with a complicated function like 3n^2^ + 4n + 5, we just replace it with O(f(n)), where f(n) is as simple as possible. In this particular example we\'d use O(n^2^), because the quadratic portion of the sum dominates the rest of the function. Here are some rules that help simplify functions by omitting dominated terms: 1\. We can ignore constant terms because as the value of n becomes larger and larger, eventually constant terms will become insignificant. For example, if T(n) = n+50 describes the running time of an algorithm, and n, the size of data it processes, is only 1024, the constant term in this expression constitutes less than 5% of the running time. 2\. We can ignore multiplicative constants because they too will become insignificant as the value of n increases. For example, 14n^2^ becomes n^2^. 3\. We need to consider the highest-order term because as n increases higher-order terms quickly outweigh the lower-order terms. That is, n^a^ dominates n^b^ if a \> b. For instance, n^2^ dominates n. 4\. We also must note that an exponential term dominates any polynomial term in the expression. For example, 3^n^ dominates n^5^ (it even dominates 2^n^). 5\. Similarly, a polynomial term dominates any logarithmic term used in the expression. For example, n dominates (log n)^3^. This also means, for example, that n^2^ dominates n log n. **O-Notation Example:** We look at how these rules help us in predicting an algorithm's performance. Let's look at a specific example demonstrating why they work so well in describing a function's growth rate. Suppose we have an algorithm whose running time is described by the function T(n) = 3n^2^ + 10n + 10. Using the rules of O-notation, this function can be simplified to: O(T(n)) = O(3n^2^ + 10n + 10) = O(3n^2^ ) = O(n^2^ ) This indicates that the term n^2^ will be the one that accounts for the most of the running time as n grows arbitrarily large. We can verify this quantitatively by computing the percentage of the overall running time that each term accounts for as n increases. For example, when n = 10, we have the following: Running time for 3n^2^ : 3(10)^2^ / (3(10)^2^ + 10(10) + 10) = 73.2% Running time for 10n: 10(10) / (3(10)^2^ + 10(10) + 10) = 24.4% Running time for 10: 10 / (3(10)^2^ + 10(10) + 10) = 2.4% Already we see that the n^2^ term accounts for the majority of the overall running time. Now consider when n = 100: Running time for 3n^2^: 3(100)^2^ / (3(100)^2^ + 10(100) + 10) = 96.7% Running time for 10n: 10(100) / (3(100)^2^ + 10(100) + 10) = 3.2% Running time for 10: 10 / (3(100)^2^ + 10(100) + 10) = 0.1% Here we see that this term accounts for almost all of the running time, while the significance of the other terms diminishes further. Imagine how much of the running time this term would account for if n was 106!