Computational Thinking & Problem Solving (SE1101) Lecture 1

Computational Thinking & Problem Solving (SE1101) Lecture 1: Introduction to computational thinking Dr. …… Logic Logic is a system used for distinguishing between correct and incorrect arguments allows using known knowledge to arrive at some further concl...

Computational Thinking & Problem Solving (SE1101) Lecture 1: Introduction to computational thinking Dr. …… Logic Logic is a system used for distinguishing between correct and incorrect arguments allows using known knowledge to arrive at some further conclusions e.g. a computer is used to automate Socrates is a man. reasoning All men are mortal. Therefore, Socrates is mortal Algorithm a sequence of clearly defined steps that describe a process to follow a finite set of unambiguous instructions with clear start and end points a correct algorithm is the ultimate basis of any computer-based solution Algorithm can be expressed in many different notations, including flowchart, and pseudocode: Pseudocode is an informal means of writing an algorithm. A flowchart is a graphical representation that uses graphic symbols and arrows to express algorithms. Defining algorithms collection of individual steps definiteness (i.e. precisely defined) precisely defined (i.e. carried out in the order specified) Variables only a single step can be under consideration at any one time once a step has been executed, the computer forgets all about it and moves on to the next if we want the computer to remember the result of a step for later use, we have to explicitly tell the computer to do so algorithms provide for this by means of variables Variables a variable is a placeholder for important information the computer should keep note of. it can also have its values updated throughout an algorithm’s execution (this is called assignment) Problem Solving Systematic Approach Form hypothesis. (Understand the problem) Plan experiment. (Devise a plan) Execute experiment. (Execute the plan) Evaluate results. (Review and extend) 1. Don’t be put off by perceived size and complexity 2. Resist the urge to jump straight into writing a solution Defining Problems If someone else gave it to you, try restating the problem in your own words. Try and represent the problem using pictures and diagrams. There will be knowns and unknowns at the start. You should ensure that enough information is known for you to form a solution. If there isn’t, make the unknowns explicit. Whatever the problem, the key thing to remember is that: a goal defines what needs to be done and not how it should be done. Problem Solving Process - Main Points Before all, you need to know a few things about the problem-solving process: Quality (Trade-offs) Collaboration Iteration  Problem Solving Process A heuristic is a specific strategy in problem-solving that usually yields a good enough answer, though not necessarily an optimal one. e.g. include trial and error using a rule of thumb drawing an analogy Defining Problems Decomposition, is an approach that seeks to break a complex problem down into simpler parts that are easier to deal with. Its particular importance to CT comes from the experiences of computer science. Programmers and computer scientists usually deal with large, complex problems that feature multiple interrelated parts. Decomposition is a divide-and-conquer strategy,  Defining Problems Recursion: a technique used to simplify a problem. It defines the solution to a large, complex problem in terms of smaller, simpler problems of the same form as the original problem. Devising a Solution – Tree Structure A tree represents a collection of entities organised into hierarchical relationships. Each ‘parent’ entity may have any number of ‘child’ entities (including none). A tree has a single ‘root’ entity and all childless entities are called ‘leaves’. Tree Structure - Example Figure 1. Science project task breakdown revised 3.1.1 write title page; 3.1.4 write contents section; 3.1.2 write copyright section; 3.1.5 write list of figures section. 3.1.3 write abstract;  Devising a Solution – Decomposition Decomposition won’t result in a complete plan of action. For example, a fully decomposed problem definition can show all the individual tasks, but doesn’t necessarily show the order in which you should tackle them However, relationships between individual sub-problems should become apparent. Decomposition aids collaboration. If you decompose a problem well (so that the sub- problems can be solved independently)  Devising a Solution – Effective Strategies Think critically Solve a concrete instance Find a related problem Work backwards  From generalization to abstraction  Decomposition is breaking the problem down into smaller sub- problems to master the problem complexity.  Generalization/Pattern recognition is identifying patterns among those sub-problems and simplifying them (a sort of hiding details in order to focus on main patterns)  Abstraction: is an activity that identifies the most relevant information needed to solve the problem and eliminates the extraneous details. [In other words: abstraction is removing unnecessary details from the problem so that we can focus on important details]  Additional information for a model Properties: discrete pieces of information about that particular entity or relationship, like a station’s name on the Makkah transit map. Type: a classification that the entity belongs to. This can tell you lots of things about that entity implicitly. For example, a line between two stations relates them by saying they’re on the same line; the color denotes the line’s type Rules: statements about an entity that must hold true. A station might be labeled with a rule saying ‘Closed between 10 and 15 November’. Behaviors: descriptions of actions that may be expressed in natural language or algorithmic form. For example, one section of a Makkah transit line might state that buses travel at a slower pace along it.  Static vs. dynamic models  Static models gives us a snapshot view of the system. They depict entities and relationships at a single point in time (Map of Makkah Transit).  Dynamic models (DM) consider that world you’re modeling changes over time (i.e. explain the changes in states as time proceeds). DM involves the following:  states: description of the entities at specific points in time;  transitions: a change in state. DM generally includes some or all of the following as well:  events: things that happen to trigger transitions;  actions: computations that are carried out as part of a stransition. Debriefing A model represents the entities in a solution and relationships between them. They typically include only details relevant in a certain context (Abstraction). Models come in two types: Static models depict a system at a particular point in time. Dynamic models show how a system changes over time. Models reduce the mental effort required to comprehend a solution. Some models are formal models and help to validate ideas by seeing if any rules are broken. Some models are executable models and predict how a solution will behave  Modeling  Engineers focus on physical models that depict working systems. Scientists often favor mathematical models that reduce phenomena down to variables. Software developers tend to use conceptual models that describe ideas.  Unified Modeling Language (UML) is a general-purpose modeling language used to describe any part of a software-intensive system. UML can be used to model:  entities;  relationships;  processes;  usage.  Modeling Entities  Entities are the focus of static diagrams (aka structural diagrams in UML), which depict components in a solution.  A class diagram shows a solution decomposed into classes. Bug and Error Solutions you create will not work flawlessly. They will contain bugs somewhere, despite your very best efforts. Even the most talented programmers and computer scientists in the world produce software that contains bugs, even if some are loath to admit it. Bugs can be simple typos or major misunderstandings. Bug - a fault in a solution that can cause erroneous behaviour. Error - any behaviour observed when executing a solution that does not match the expected behaviour. Designing Out The Bugs Various types of bugs can cause erroneous behaviour: Typos Poor grammar and ambiguities Inconsistencies Logical and mathematical errors Being exhaustive Typos ‫اﻷﺧﻄﺎء اﻟﻤﻄﺒﻌﻴﺔ‬ Your solution exists in various design forms, documents, notes, diagrams, and algorithm outlines. Any typos could cause problems Typos include: spelling errors incorrect capitalisations; missing words wrong words (for example, ‘phase’ instead of ‘phrase’); numbered lists with incorrect numbering, and so on. Poor grammar and ambiguities Some grammatical errors are quite subtle.. Example: After having a coin inserted, the user will be able to push the turnstile. What or who exactly is having a coin inserted here? Ambiguities can appear in sentences that are grammatically fine Example: After the login process fails a number of times in a row, the incident should be reported in an email to the security administrator. The intention behind this statement is fine, but what does ‘a number of times’ actually mean? Two, five, a hundred? Inconsistencies An inconsistency arises when parts of a solution separately make statements that make no sense when considered together. These bugs are harder to locate because each part of the inconsistency might appear in very different contexts Consider the example of the login process (above) rewritten as follows: After the login process fails five times in a row, this incident should be reported in an email to the security administrator. Also imagine that a different part of the solution contains the following statement: After the login process fails three times in a row, the login screen should automatically lock and refuse further login attempts. If a login attempt fails three times consecutively, the user cannot attempts. Consequently, they can never perform five login attempts in a row, so the first statement is redundant. Being exhaustive Algorithms should be exhaustive and contain instructions for all conceivable outcomes. If you fail to account for any of them, the computer’s behaviour becomes unpredictable, it might : take an unwanted action or do nothing when it should do something. Being exhaustive How to avoid some common errors: Think critically; what might go wrong Look especially at conditionals; if X is the case, what happens if X is not the case? Look especially at loops; Make sure the loop cannot go on endlessly.  Mitigating Errors What you can do to mitigate error effects: Getting defensive Reacting to problems Checking user input Getting defensive Put some ‘protective barriers’ in place. Computer science calls this defensive programming. Physical systems where safety is an important issue are designed defensively. That is, they are safe by default. Getting defensive The default state of an elevator without power is to have its brakes on. To make the elevator move, power must be supplied to the brakes to switch them off. If the elevator loses power, it reverts to its default, powerless state with brakes applied. Hence, when something goes wrong, the people inside the elevator are automatically kept safe without any need for action. Reacting to problems Response to a failed precondition depends on the context. The severity of the error determines the appropriate action, so severity-based Responses: Low severity: Display a message or provide a minor action High severity: Enter emergency mode or shut down the system  Reacting to problems Example: Drink Vending Machine Normal operation: Read money and serve drinks Responses to different problems: Unreadable or foreign money: Return the money with a helpful message Cup fallen over on the tray: Refuse to continue until the cup is righted Leak in water supply: Shut down the machine to prevent damage Reacting to problems General Considerations: System interactivity: Interactive systems can ask the user what to do Transactional systems: Undo changes made during a defective step Checking user input Users can make mistakes or intentionally provide faulty input Adopt a "healthy paranoia" mindset to anticipate errors Types of Input Errors: Incorrect numeric input (e.g., '9O' instead of '90') Input outside of expected range or constraints Incorrect formats (phone numbers, URLs, email addresses, dates, times)  Checking user input Validation Techniques: Verify that input matches the expected data type (e.g., number) Check if input falls within the required range or constraints Ensure input adheres to specific formats (e.g., regular expressions) Testing Testing is a method for locating hidden bugs in a fully or partially working system. Goal: Verify if the system performs as expected Identify areas where the system fails Testing requires a working state of the solution Testing Approach: Top-down testing: Test the solution as a whole Identify design flaws and verify system integration Bottom-up testing: Test the smallest parts individually Ensure each part fulfills its obligations within the system Top-down and Bottom-up Testing  Top-down and Bottom-up Testing Combine top-down and bottom-up approaches: 1 2 3 Start with a skeletal Replace Test the whole structure filled with placeholders with system while placeholders functioning parts for implementing isolated testing individual pieces (bottom-up testing) (top-down testing) Debugging A puzzling error will occur during testing or real-world use of your solution. It will be unclear what particular step of the solution caused the problem, but there’s no need to panic. Debugging is a systematic process of finding and fixing the error. Debugging Your goal is to specify error(s) that occurred and reconstruct the chain of events that led up to them. There are methods you can apply: look for clues make deductions build a hypothesis that might explain the problem put it to the test proceed to think about a fix. Strategies for Debugging Be ruthless with hunches: Trust your intuition and try out your hunches Discard incorrect hunches immediately Stay open to alternative explanations Strategies for Debugging Respect Occam’s Razor Simpler explanations are more likely to be correct Avoid overly complex explanations Start with simple hypotheses and eliminate them Strategies for Debugging Divide and conquer Reduce the search space by dividing the problem Utilize the divide-and-conquer approach used in solution design Eliminate components or areas that are not contributing to the problem Approach of Debugging Change one thing at a time: Debugging is like experimentation Vary one factor at a time to establish cause and effect Apply changes, test, and undo if unsuccessful before trying something else  Approach of Debugging Logging: Insert logging instructions to track execution and values Use logging to investigate unexpected behaviour Identify incorrect values and track program flow Example: Checking a Condition (if x > 10, then do stuff) Add a logging instruction to print the value of a variable Confirm if the variable has the expected value  Approach of Debugging Tracing: Diagnose problems by going line by line through the code Execute each instruction and track changes to the data Hand tracing or using a debugger for detailed analysis Example: Tracing by hand: Go through each line, execute, and track changes Example: Tracing algorithm for a Minesweeper game  Approach of Debugging Explain the problem aloud Explain the problem vocally to gain new insights Step through the issue, attempted solutions, and unexplored options Verbalizing the problem can lead to fresh perspectives  Deciding Which Errors To Fix We need a way to choose which ones to fix 1. Severity Level: Describes how strongly the error prevents proper usage Ranges from Minor, Moderate, Major, to Critical 2. Priority Factors: Frequency: Higher priority for frequently occurring errors Feature Value: Importance of the affected feature determines priority Scheduling: Consider the time required to fix the error Deciding Which Errors To Fix Bug Prioritization: High-priority/high-severity bugs are the most important. Low-priority/low-severity bugs ranked last High-priority/low-severity problems should be tackled earlier