Unit 02: Computational Thinking and Algorithms PDF

## Unit 02: Computational Thinking and Algorithms **After completing this lesson, you will be able to:** - Plan, develop, systematically test, and refine computational artifacts for problem solving. - Apply common search and sort algorithms. ### Computational Thinking Steps * **Abstraction:** Sim...

## Unit 02: Computational Thinking and Algorithms **After completing this lesson, you will be able to:** - Plan, develop, systematically test, and refine computational artifacts for problem solving. - Apply common search and sort algorithms. ### Computational Thinking Steps * **Abstraction:** Simplifying a problem or system by focusing on the most relevant aspects while ignoring unnecessary details. It's about looking at the big picture without getting lost in the tiny details. * **Decomposition:** Breaking down a complex problem into smaller, more manageable sub-problems or tasks. * **Pattern Recognition:** Identifying patterns or trends within data, problems, or solutions. * **Algorithm Design:** Developing a step-by-step solution to solve a problem. ### Computational Artifacts Computational artifacts refer to human-made objects and systems using computational thinking. An artifact is a byproduct of software. Particularly in computer science, the computational artifacts could include programs, websites, videos, simulations, databases, digital animations, software systems, e-commerce platforms, and mobile applications. #### Computational Artifacts in Software Development In software development, the artifact could be an object that helps to describe the architecture, design, and function of software. There are a range of different artifacts generated during the lifecycle of software development as shown in the figure below. The artifacts are considered important because they make the process of developing software easy. - **Meeting notes / Images:** - **Diagrams:** - **Source code:** - **Software documentation:** - **Prototypes:** #### Design Methods * **Algorithms:** A step-by-step set of instructions that defines how a specific problem should be solved. * **Flowcharts:** A visual representation of flow and logic using defined symbols. * **Pseudocode:** An intermediate step between the algorithm and actual programming code. It's a more structured and semi-formal way of representing the algorithm using a combination of natural language and simplified programming constructs. #### Algorithm Design The primary goal of pseudocode is to convey the algorithm's logic in a clear and understandable way, irrespective of specific programming language conventions. **Font, Size, Style:** * **Font:** It is typically written in a plain, easy-to-read font. * **Size:** Use a standard font size that is easy to read, often around 10-12 points. * **Style:** Italicizing or bolding keywords is sometimes done for emphasis, but it's not a strict rule. **Indentation:** Use consistent indentation to visually represent the structure of your code. Commonly, 2-4 spaces or a tab character is used for each level of indentation. **Case:** While pseudocode is not case-sensitive, using uppercase for keywords and lowercase for variables can enhance readability. For example, FOR i FROM 1 TO n or if condition then. **Line Numbers:** Including line numbers is optional and depends on the requirements of a specific project. Line numbers can aid in discussions about the algorithm. **Comments:** Comments are essential for explaining the logic. They are often denoted by symbols like // for single-line comments or /**/ for multiline comments. **Data Type Keywords:** Some pseudocode styles use data type keywords like INTEGER, STRING, etc., to indicate the type of a variable. However, this is optional. **Variables:** Variables/Assignments & Declarations: Variables can be declared using DECLARE or simply by mentioning them. Assignments are often denoted using := or =. **Common Operators:** Use standard operators such as +, -, *, /, %, <, >, <=, >=, == to represent common operations. **Key Commands:** Key commands like INPUT, OUTPUT, FOR, IF, WHILE can be used to represent specific actions on control structures. #### Planning and Developing a Computational Artifact The following steps are used for planning and development of an artifact: 1. **Define the problem:** State the problem you are trying to solve in clear and concise terms. 2. **List the inputs (information needed to solve the problem) and the expected outputs (what the algorithm will produce as a result):** 3. **Plan:** - **Outline the logic**: For this purpose, breakdown the problem into smaller problems and consider how to solve each one. - **Choose Data Structures**: A data structure is a storage to save and organize the data. We have different types of data structures such as array, stack, queue, etc. The choice of data structures is determined by considering the merits and drawbacks associated with each specific data structure. - **Choose Control Structures**: Enables to determine the order of program execution. - **Development**: Describe the steps needed to convert or manipulate the inputs to produce the outputs. Start at a high level first and keep refining the steps until they are effectively computable operations. Keep the process simplified and remember that the number of steps should be finite. - **Test the algorithm**: Choose data sets and verify that your algorithm. #### Testing Computational Artifacts The computational artifacts should be tested by considering potential logical errors. For example, you should think what would happen if a user enters invalid or a certain out of range input. Testing and accordingly refinement of the solution is the iterative process of a computational artifact. **Tracing an Algorithm:** Tracing of the algorithm is also known as a "desk check or dry-run”. The programmers convert the algorithms to code that is ultimately handed over to computer for compilation and execution. But before going to write code for an algorithm, we manually verify that the algorithm works correctly. For this purpose, trace method is used that hand simulates the execution of your algorithm, keep change track of variable values and flow of logic control. **Tracing of Algorithm involves the following:** 1. **Understand the Algorithm:** Before tracing is started, thoroughly understand the algorithm's logic flow. 2. **Choose Test Input:** To trace the algorithm it requires input; a complete set of input is therefore chosen at this point. 3. **Initialization:** Initialize the variables and data structures. This helps in setting up the algorithm in its initial state, where the algorithm has never run before. 4. **Trace Each Step:** Hand execute the algorithm step-by-step, tracking the flow of control. For each step of algorithm, do the following: * Track record Inputs: write the input values and variable values relevant to that step. * Perform processing: Do computation / perform the operation specified in that step of algorithm. * Update Variables: keep an eye on the changes in the variable values and data structures in response to performing operation. * Go by Control Flow: Normally, the steps of algorithms are followed sequentially but sometimes this sequence is broken by loops, conditional statements, and function calls. Therefore, we need to track how an algorithm decides which step to execute next. 5. **Repeat Until Completion:** Tracing the algorithm continues step by step until we reach the end of algorithm. 6. **Verify Output:** At the end, evaluate the final output and ensure that it matches our expectations based on the given set of inputs. #### Trace Tables Trace tables show the variables change at each stage in the algorithm. The trace tables generate the output on a given set of input data to test if the algorithm is giving expected output. It also helps to check that our logic is correct and find logical errors, if any. #### Algorithms Evaluation Parameters Algorithms are evaluated using a variety of criteria and methods to assess their performance, efficiency, and correctness for specific tasks. The evaluation process determines whether an algorithm meets its intended objectives. The following are some common ways to evaluate algorithms: - **Correctness** - **Efficiency** - **Clarity** - **Reliability** #### Common Computing Algorithms Different problems require different types of algorithmic techniques to solve the problems. Similarly, different programmers prefer to use different algorithms to solve the same problem. There are many algorithms that have been pre-developed because they are considered fundamental and commonly used in solving daily life problems. ##### Sorting Algorithms The sorting algorithms are used to arrange data in a useful manner (Such as ascending or descending order). Various methods of sorting are used for example Insertion sort algorithms, Bubble sort algorithms, etc. ###### Insertion Sort Algorithm In Insertion sort, we compare adjacent elements and sort them if they are not in correct order. While comparison, the smallest element is selected and swapped with the element that is placed at first location. This is the first iteration, and we will continue until all elements are sorted. At the end, we have an array of sorted elements. **Working of Insertion Sort Algorithm** Consider the following array of unsorted elements which need to be sorted in ascending order. For ease let's use four colors to represent four different things in the given array: * **Yellow color for unsorted array.** * **Blue color for elements to be compared in the unsorted array.** * **Green color for sorted array.** * **Red color for elements that are not correct in the sorted part of array.** At the start, all elements are colored yellow: **12 31 25 8 32 17** Assuming first element (12) is already sorted. **12 31 25 8 32 17** ##### Bubble Sort Algorithm In Bubble Sort algorithm, we repeatedly compare and swap the adjacent elements if they are not in correct order. If we need to sort the array in ascending order, then bubble sort algorithm starts by taking first element of the array and compare it with the second element first iteration. Suppose if the first element is greater than the second then it will swap these elements, and then move forward to compare the second element with the third element, and it continues until the largest element reaches the last place in the array. We need to repeat this process (iteration) until the complete list is sorted. **Working of Bubble Sort Algorithm** Consider the following array of elements: **First Iteration:** **13 32 26 35 10** Take the first element and compare it with its adjacent element: **13 32 26 35 10** Here, the first element (31) is small than the second element (32), so it is already sorted. Now, the second element and compare it with next adjacent element (e.g. 32 with 26). **13 32 26 35 10** Here, 32 is greater than 26. So, we need to swap them both. After the swapping, array will look like this: **13 26 32 35 10** ##### Searching Algorithms The searching algorithms are used to search desired element that is available in some group of elements. Like sorting, various searching methods are available for example Binary Search algorithms and Linear Search algorithms. ###### Binary Search Algorithm This search method works on sorted lists. It follows the divide and conquer approach in which the sorted list is divided into two parts. The item to be searched is then compared with the middle element of the list. If it matches then, the location of the middle element is returned. Otherwise, we search into one of the divided parts depending upon the result produced in the last comparison. **Working of Binary Search** Consider the following sorted array of nine elements and we need to find a number 36. **0 1 2 3 4 0 6 7 8 10 12 24 29 39 40 51 56 69** **Divide the array in to two parts, the middle element is 39.** **0 1 2 3 4 0 6 7 8 10 12 24 29 39 40 51 56 69** The item to be searched (56) is compared with the middle value (e.g. 39). We came to know that 56 is greater than 39, therefore the item is surely in the right side of the array (because the array is sorted). **Here we get right part of the array.** It will again be divided into two parts. **40 51 56 69 56 69** **Considering 51 the middle element, we will compare the item (with this, because 56 is greater than 51 therefore, we will again take right side of the array.** Divide the array again into two parts. **56 69** **Considering 56 as the middle element, we will compare it with the item to be searched (e.g. 56). Now, the required item is found. So we will provide output of the algorithm that is location 7. If the required item is not found the algorithm returns NULL.** ###### Linear Search Algorithm This is a simple search algorithm; we go through the complete list and match the elements one-by-one until the required item is found. If the item is found, then the location of that element is returned, otherwise a NULL is returned. This search is also called as sequential search algorithm. However, there is no compulsion that the array should be sorted. Working of Linear Search Consider the given unsorted array and we need to find location of item 41. **0 1 2 3 4 0 6 7 8 70 40 30 11 57 41 25 14 56** We will start from first element. **0 1 2 3 4 0 6 7 8 70 40 30 11 57 41 25 14 56** The required item (41) is compared with the first element. Both don't match, we will go to next element. **0 1 2 3 4 0 6 7 8 70 40 30 11 57 41 25 14 56** We will again compare the send element (e.g. 40) with required item (e.g. 41), both don't match. So will continue the process. **0 1 2 3 4 0 6 7 8 70 40 30 11 57 41 25 14 56** We found the element at location 5 so output of this algorithm would be 5. In these type of algorithms, if the required item is found we provide the output or if item is not found and we reach at the end of array then a NULL is given in output. ### Summary * **Abstraction:** Identifying essential information and removal of the unnecessary details to solution. * **Algorithm:** A step-by-step set of instructions that define how a specific problem should be solved. * **Algorithm Design:** This is actual designing of solution. This involves creating step-by-step plan of the problem solution. * **Algorithm Evaluation:** Assess the algorithm performance, efficiency, and correctness for specific tasks. * **Algorithm Tracing:** Used to hand simulate the execution of your algorithm, keep change track of variable values and flow of logic control. * **Binary Search:** Sorted list is divided into two parts. The item to be searched is then compared with the middle element of the list. If it matches then, the location of the middle element is returned. Otherwise, we search into one of the divided parts depending upon the result produced in the last comparison. * **Bubble Sort:** We repeatedly compare and swap the adjacent elements if they are not in correct order. Bubble sort algorithm starts by taking first element of the array and compare it with the second element. Suppose if the first element is greater than the second then it will swap these elements, and then move forward to compare the second element with the third element, and it continues until the largest element reaches the last place in the array. * **Computational Artifacts:** Refer to human-made objects and systems using computational thinking. * **Computational Thinking:** A thought process that helps us to understand the problem and solve it in a way that computers do. * **Decomposition:** Breaking down the larger problems into smaller/ manageable ones and working on them one by one. These smaller problems are referred to as sub-problems. This way we simplify the problem and solve it easily. * **Development:** Describes the steps needed to convert or manipulate the inputs to produce the outputs. * **Flowchart:** Provides a visual representation of flow and logic using defined symbols. * **Insertion Sort:** We compare adjacent elements and sort them if they are not in correct order. While comparison, the smallest element is selected and swapped with the element that is placed at first location. * **Linear Search:** We go through the complete list and match the elements one-by-one until the required item is found. If the item is found, then the location of that element is returned, otherwise a NULL is returned. This search is also called as sequential search algorithm. However, there is no compulsion that the array should be sorted. * **Pattern Recognition:** Examine the problem for a pattern or similarities between previously solved problems. * **Pseudocode:** An intermediate step between the algorithm and actual programming code. * **Searching Algorithms:** Used to search desired element that is available in some group of elements. * **Sorting Algorithms:** Used to arrange data in a useful manner (Such as ascending or descending order). * **Trace Tables:** The dry run of an algorithm can be done with a technique known as Trace Tables. ### Exercise **Select the best answer for the following Multiple-Choice Questions (MCQs).** 1. A complexity of algorithm depends upon a) Time Only b) Space Only c) Both Time and Space d) None of above 2. An algorithm: can be represented through a) Flow charts b) Pseudo-codes c) Instructions in common language d) All of the mentioned above 3. There are two algorithms suppose A takes 1.41 milliseconds while B takes 0.9 milliseconds, which one of them is better considering all other things the same? a) A is better than B b) B is better than A c) Both are equally good d) None of the mentioned 4. Considering an array has 10 elements and the searching element is at array index 6. A starting element is present at index zero. How many comparisons are required to search and element using linear search? a) 5 b) 6 c) 7 d) 8 5. In computer science, the computational artifacts could include. a) Programs b) Simulations c) Videos d) Programs, Simulations and videos 6. In the planning phase of computational artifact development following is included in a) Logic b) Data Structures c) Control Structures d) Logic, Data and Control Structures 7. Trace method is used to a) Take input b) Hand simulate the execution algorithm. c) Take a print d) Align margins 8. Trace Tables are used to a) dry run algorithm b) test if algorithm is giving expected output c) show the variables change d) a, b and c 9. Algorithms are evaluated using ______ a) Correctness b) Efficiency c) a and b d) None of above **Give short answers to the following Short Response Questions (SRQs).** 1. Differentiate between: i) Clarity vs. Efficiency ii) Abstraction vs. Pattern Recognition iii) Pseudocode vs. Flowcharts iv) Data Structures vs. Control Structures v) Algorithm vs. Pseudocode 2. Write a note on working of Bubble Sort. 3. Write names of commonly used computational artifacts made during computational thinking. 4. Where we prefer to use binary search algorithm rather than linear search algorithm? 5. What are the advantages of using flowcharts? **Give long answers to the following Extended Response Questions (ERQs).** 1. Determine the properties involved in computational thinking. 2. Sketch an algorithm that inputs length in inches and prints it in centimetres. 3. Implement an algorithm to print multiplication table of a number in reverse order. 4. Examine the uses of Flowcharts. 5. Anewly developed Algorithm needs to be tested. Argue about the reasons. **Activity 1: Complete the given trace table using the following algorithm snippet.** 1. Start 2. x = 2 3. total = 0 4. REPEAT Step 5 Three TIMES 5. total = total + x 6. Print (total) End | Line No. | x | total | output | |---|---|---|---| |---|---|---|---| | **...** | **...** | **...** | **...** | | **...** | **...** | **...** | **...** |