Unit 2 Revision: Problem Solving, Algorithms, and Programming Languages Study Guide

Problem Solving and Computational Thinking

• Understanding Problem Solving: Programmers can only write programs for computers to solve problems if they understand how to solve the problem themselves. A programmer requires a toolkit of different methods to consider ways a problem can be solved.

• Goal of Computational Thinking: To write successful solutions, programmers develop computational thinking skills to break problems into manageable chunks and simplify situations.

• Algorithm Representation: Computational thinking allows a problem to be represented as a set of steps (algorithms) that a computer can carry out.

• Decomposition Definition: This is a technique used to break a large program down into a series of sub-problems.     * The Starting Point: Decompose the large problem so each sub-problem is described with the same level of detail.     * Independence: Each sub-problem should be capable of being solved independently of the others.     * Integration: Solutions to sub-problems are brought together to provide a solution to the whole problem.     * Advantages: Different people can work on different sub-problems simultaneously.     * Disadvantages: Sub-problem solutions might not integrate correctly to solve the whole problem.

• Case Study: Smart Card System: A school introduces a smart card system for dining hall payments.     * Main Problem: Introduction of the smart card system.     * Initial Sub-problems:         1. Allow parents to add money to the child’s card.         2. Allow pupils to pay for food and drink.         3. Update the amount of money remaining on the card.     * Further Decomposition (Adding Money):         * Add money over the internet.         * Add money by giving cash/cheque to the school office.         * Add money via a cash-loading machine in the dining hall.     * Further Decomposition (Internet Payment):         * Logon to school payment system.         * Identify the child.         * Enter bank card details.         * Confirm payment.         * Logoff from the system.

• Abstraction Definition: Abstraction is a technique to reduce something to the simplest set of characteristics that are most relevant to solving the problem.     * Focus: Concentration on the most important aspects without worrying about fine details.     * Example (Drawing a Square in Scratch): A square requires four sides of $50$ units with an angle of $90^\circ$ between them.     * Simplification via Abstraction: Instead of a long series of repeated commands, code is simplified using a loop and defined as a procedure. This hides unnecessary details and allows the procedure to be called whenever needed.

• General Purpose: Computational thinking allows humans to understand complex problems and present analysis in a way that enables a computerized solution.

Variables and Constants

• Variables: Required to store data that can change during program execution.     * Identifiers: Names given to variables should be self-documenting (reflect the data stored).     * Example: txt_FirstName implies the data type is text and stores a person's first name.

• Constants: Used to store data that does not change.     * Naming Convention: Usually written in capitals (e.g., BOILING_POINT_OF_WATER = 100).     * Example: Pi = 3.14 is a self-documenting identifier that remains constant.

• Scope and Lifespan:     * Local Variables: Defined within a sub-procedure and only accessible within that same sub-procedure (its scope). Advantage: Easier to track changes and reasons for changes.     * Global Variables: Have a larger scope; defined globally and accessible from anywhere within the program. Advantage: Efficient way to ensure important data (like user login details) is accessible to all sub-procedures.     * Static Variables: Stored in a memory location for the entire duration the program is running. They retain their value (e.g., $2.14$) between sub-procedure calls until the whole program stops.     * Dynamic Variables: Assigned a new location in memory each time they are defined; their lifespan ends when the sub-procedure in which they are defined ends. They do not retain values between calls.

Questions & Discussion

• Scenario: An algorithm calculates the area of a circle.     * Global Variable: Radius (accessible throughout).     * Local Variable: Area (defined within sub-procedure FindArea).

• Problematic Line: 17 output “The area is ”, Area     * Question: Can you spot the error with the line above? How would you amend the algorithm to correct this?     * Contextual Answer: Because Area is a local variable within FindArea, it is not accessible to an output command outside that specific scope. The algorithm would need to return the value or make the variable global to be accessed at line 17.

Algorithms and Programming Constructs

• Algorithm Definition: A set of clear instructions in the correct order to solve a problem. It is the starting point for writing code but should not be written in computer code itself.

• Representation Formats:     1. Pseudo code: Instructions written in plain English.     2. Flowchart: A diagram showing instructions in their execution order.

• Traits of a Good Algorithm:     * Finite: It must eventually end.     * Well-defined instructions: Each step must be clear and carry out the exact intention.     * Effective: It must provide the correct result or solution.

• Core Constructs:     * Sequence: The specific order in which instructions must be carried out. Computers follow instructions exactly as given.     * Selection: An instruction where a decision must be made, offering different options (e.g., if...else).     * Iteration: A set of steps carried out more than once (loops).

• Loop Control Methods:     * Count: Records the number of times a process is carried out; the loop terminates when a specific number is reached.     * Rogue Value: A value outside the range of possible data (e.g., using $-1$ for age when calculating averages) used to stop the loop.

• Pseudo Code Rules & Conventions:     * Declare subroutine: Declare SubroutineName... End Subroutine.     * Call subroutine: call SubroutineNeeded.     * Arrays: myarray[99].     * Assignment: set counter = 0.     * Data Types: integer, character, string, Boolean, real.     * Selection: if...else...end if (Indented).     * Repetition: for i...next i, repeat...until, do...while, while...repeat.

• Flowchart Symbols:     * Oval: Start/Stop procedure.     * Diamond: Decision box.     * Parallelogram: Input/Output.     * Rectangle: Operation.     * Small Circle: Connector.     * Double-sided Rectangle: Store/Subroutine call.     * Arrow: Flow of control.

String Handling Rules

• Basic Commands:     * Length: len(string) returns the number of characters, including spaces and special characters.     * Mid String: mid(string, start, length) returns part of a string based on an offset ($x$) and length ($y$).     * Replace: replace(string, find, replacewith) replaces specific characters or words.     * Compare: str(Comp(string1, string2)) returns $0$ (true) if identical and $-1$ (false) if not.

• Comparison Variations:     * To perform a textual comparison ignoring case (upper/lower), use str(Compare, txt1, txt2, 1). Value returns $1$ for match in some contexts or handles the case-insensitivity depending on the parameter.

• Concatenation: Joining strings/text using the & operator.     * Example: print “Welcome “ & txt1 & txt2 outputs Welcome Sarah Smith.

Sorting Algorithms

• Merge Sort:     * Concept: "Divide and Conquer."     * Process: Splits the list into two equal halves repeatedly until each list contains a single item. Then, combines them back in sorted order.     * Example Sequence: $37, 14, 10, 27, 24, 19, 44, 35$.         * Split to single items.         * Iterative merge: $(14, 37), (10, 27), (19, 24), (35, 44)$.         * Final merge: $10, 14, 19, 24, 27, 35, 37, 44$.

• Bubble Sort:     * Concept: Compares adjacent items and swaps them if they are in the wrong order.     * Limitations: Not suitable for large data sets.     * Process:         * Iteration: One complete pass through the list.         * At least one item moves to the correct position each pass.         * Termination: The sort stops when an iteration results in no swaps.     * Interesting Fact: Data takes the longest to sort when it is in the reverse of the required order.

Searching Algorithms

• Linear Search:     * Mechanism: Every item is compared sequentialy until found or the end is reached.     * Efficiency: Inefficient. May require comparing every item ($n$ comparisons).     * Requirement: Data does not need to be ordered.

• Binary Search:     * Requirement: Data must be sorted.     * Mechanism: Starts at the mid-point. Discards the half where the item cannot be.     * Mid-point Formula: $\text{mid point} = \text{low} + \frac{\text{high} - \text{low}}{2}$.     * Outcomes: Match found, item is less than mid (discard top half), or item is greater than mid (discard bottom half).     * Example Calculation: For index range $0$ to $8$:         * $\text{mid point} = 0 + \frac{8 - 0}{2} = 4$.         * If search item is higher, new range is $5$ to $8$.         * $\text{mid point} = 5 + \frac{8 - 5}{2} = 6.5$ (Take integer part: $6$).

Programming Languages

HyperText Markup Language (HTML)

• Standardization: Simplifies development so programmers understand each other's code. Ensures browsers (Chrome, Safari, etc.) display pages as intended.

• Browser Market Share (Dec 2018):     * Chrome: $62.9\%$     * Safari: $14.3\%$     * Internet Explorer and Edge: $7.1\%$     * Firefox: $6.2\%$     * Opera: $3.0\%$

• HTML Tags: Usually in pairs (opening/closing).     * <html>: Describes the page.     * <head>: Container for meta info, title, scripts.     * <body>: Contains visible content.     * <p>: Paragraph (adds vertical space).     * <a href="url">: Hyperlink.     * <img>: Displays images (Self-closing: <img src="logo.gif">).     * Formatting: <h1> to <h6> (Headings), <b> (Bold), <i> (Italic), <center> (Alignment).     * Lists: <ul> (Unordered list) with <li> (Line items).     * <hr>: Horizontal rule for separation.     * <blockquote>: For quoted sections (indented by browsers).

Assembly Language

• Nature: Low-level language, one step removed from machine code.

• Machine Code: Binary ($0$s and $1$s); difficult to use.

• Mnemonics: Assembly uses names instead of binary but follows machine code structure.

• Hardware Dependence: Specific to a CPU type; not portable.

• Advantages: Less memory, faster execution, directs hardware interaction (device drivers), suitable for time-critical processes.

• Instruction Set:     * INP: Input value to accumulator.     * OUT: Display accumulator contents.     * STA: Store accumulator value to RAM.     * LDA: Load value from RAM to accumulator.     * ADD: Add RAM content to accumulator.     * SUB: Subtract RAM content from accumulator.     * BRA: Branch (jump to RAM location for loops).     * HLT: Stop processor.     * DAT: Define variables.

Object-Oriented Programming (OOP)

• Object: A collection of states (data like name/breed) and behaviors (actions like grunting/moving).

• Class: A blueprint or template for objects. Names must start with an Uppercase letter.

• Method: A behavior (action). Names must start with a lowercase letter.

• Instance Variables: Variables bound to specific class instances (e.g., leaves eaten by a specific wombat).

• Four Pillars of OOP:     1. Encapsulation: Wrapping data and code into a single entity (the class).     2. Abstraction: Hiding non-essential features while showing essential ones.     3. Inheritance: A subclass (derived class) inherits states/behaviors from a superclass (base class). Actor is a superclass; Wombat is a subclass.     4. Polymorphism: Actions (methods) acting differently based on the object (e.g., makeSound() makes a Wombat grunt but a Sheep bleat).

Technical Skills for Greenfoot (Version 2.4.2)

• Extend classes and create objects/worlds.

• Write/invoke methods and change existing ones.

• Manage properties (public, private, static).

• Object movement and collision detection.

• Keyboard input and sound implementation.

• Parameter passing (by value and by reference).

• Random number generation.

Data Structures and Types Checklist

• Data Structures: 1D arrays, 2D arrays, files, and records.

• Data Types: Integer, Boolean, Real, Character, String.

• Security: Security and authentication techniques (referencing final section).