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

Problem Solving and Computational Thinking

• Problem Solving for Programmers: To write effective programs, programmers must first understand the solution to the problem themselves. They rely on a toolkit of various methods to analyze potential solutions.
• Developing Computational Thinking: Successful solutions require breaking problems into manageable pieces and simplifying complex situations. Computational thinking allows a problem to be represented as a set of logical steps, which can then be formatted as algorithms for computer execution.

Decomposition and the Smart Card System

• Definition of Decomposition: This is a technique used to break a large, complex program into a series of smaller sub-problems.
  • Goal: Each sub-problem should be described with the same level of detail and remain independently solvable from others.
  • Integration: The individual solutions for these sub-problems are combined to form the complete solution for the whole problem.
• Advantages and Disadvantages of Decomposition:
  • Advantage: It allows team-based work where different individuals manage different sub-problems.
  • Disadvantage: There is a risk that the individual solutions may not integrate correctly to solve the original large problem.
• Case Study: School Smart Card System: A school implements a system for pupils to pay for food and drinks. The programmer breaks the main problem into three primary segments:
  1. Allowing parents to add money to a child’s card.
  2. Allowing pupils to pay for food and drink.
  3. Updating the card balance.
• Further Decomposition Example: The sub-problem “Allow parents to add money” is further broken down into:
  • Adding money over the internet (Logging on, identifying the child, entering bank card details, confirming payment, and logging off).
  • Adding money via cash or cheque at the school office.
  • Adding money using a cash-loading machine in the dining hall.

Abstraction and Simplification

• Definition of Abstraction: A technique that reduces a problem to its simplest set of relevant characteristics, ignoring fine or unnecessary details. This allows the programmer to focus on the most important aspects.
• Example: Drawing a Square in Scratch: To draw a square with four sides of $50$ units and angles of $90^{\circ}$, a sequence of repeated commands is used. Under abstraction, these repeated commands are simplified using a loop.
• Procedures: The abstract code is defined as a procedure that can be called whenever needed, hiding the internal complexity from the rest of the program.

Variables and Constants in Programming

• Variables: Used to store data that can change during program execution. They are given “identifiers” (names).
  • Self-documenting Identifiers: Example txt_FirstName implies the data type is text and represents a first name.
• Constants: Used to store data that remains unchanged throughout the program. Often written in capitals to distinguish them.
  • Examples: $Pi = 3.14$, BOILING_POINT_OF_WATER = 100.

Local and Global Variables: Scope and Efficiency

• Scope: Refers to where a variable is accessible within a program.
• Local Variables: Defined within a specific sub-procedure. They are only accessible within that sub-procedure.
  • Advantage: Easier to track changes and understand why those changes occurred within a specific segment of code.
• Global Variables: Defined globally and accessible from anywhere in the program.
  • Advantage: Efficient for sharing critical data, such as the details of a currently logged-in user, across all sub-procedures.
• Example Analysis (Area of a Circle Algorithm):
  • Global variable: Radius (accessible throughout).
  • Local variable: Area (defined only within the FindArea sub-procedure).
  • Error Identification: Attempting to output the Area variable outside of the FindArea procedure (line $17$) would result in an error because the variable is local to the procedure.

Static and Dynamic Variables: Memory and Lifespan

• Static Variables: Stored in a specific memory location for the entire duration the program is running. If you assign a value like $2.14$ to a static variable, it persists until the program terminates.
• Dynamic Variables: Assigned a new memory location every time they are defined. Their lifespan ends when the sub-procedure in which they are defined concludes. If a value like $2.14$ is assigned, it will be lost once the sub-procedure ends.

Algorithms: Clarity, Flowcharts, and Pseudo Code

• Definition of an Algorithm: A set of clear, ordered instructions used to solve a problem. It should be language-agnostic (not written in specific computer code).
• Qualities of a Good Algorithm:
  • Finite: It must eventually end.
  • Well-defined Instructions: Every step must be unambiguous and carry out the exact intention.
  • Effective: It must result in the correct solution.
• Presentation Formats:
  • Pseudo Code: English-like instructions.
  • Flowcharts: Diagrams illustrating the order of operations.
• Flowchart Conventions:
  • Start/Stop: Oval shapes.
  • Decision Box: Diamond shapes.
  • Input/Output: Parallelograms.
  • Operation: Rectangles.
  • Connector: Small circles.
  • Store/Subroutine call: Rectangles with vertical lines on the sides.
  • Flow of control: Arrowheads indicating direction.

Basic Programming Constructs: Sequence, Selection, and Iteration

• Sequence: The specific order in which instructions must be carried out. Computers follow these instructions exactly as ordered.
• Selection: Instructions where a decision must be made (e.g., if...else statements).
• Iteration: Repeating a set of steps multiple times, often called a “loop” (e.g., for i...next or while...repeat).

Controlling Loops: Count and Rogue Values

• Loop Termination: Loops must have a condition to end.
• Count Values: Records the number of times a process occurs; the loop ends when the count reaches a specific threshold.
• Rogue Values: A value outside the range of possible data used to trigger loop termination.
  • Example: Using $-1$ as a rogue value to stop a loop calculating the average age of children, as age cannot be negative.

String Handling Techniques

• Commands and Functions:
  • len(string): Returns the total number of characters, including spaces and special characters.
  • mid(string, start, length): Returns a specific section of a string. “start” refers to the offset, and “length” is the number of characters to return.
  • replace(string, find, replacewith): Swaps part of a string for another value.
    • Example: replace("Have a happy birthday", "happy", "fantastic") results in “Have a fantastic birthday.”
  • str(Comp(string1, string2)): Compares two strings. Returns $0$ if identical (True) and $-1$ if not (False).
  • Textual Comparison: Adding a parameter ($1$) to the str(Compare) command ignores case sensitivity (e.g., “hello” vs “Hello” becomes a match).

Concatenation and Data Manipulation

• Concatenation: The process of joining strings or text together using the & operator.
  • Example: Joining txt1 ("Sarah") and txt2 ("Smith") with a greeting: "Welcome " & txt1 & txt2 outputs “Welcome Sarah Smith”.
• Sorting Overview: Organizing data into numeric or alphabetic order. Sorting is significantly slower if the data is currently in reverse order (e.g., sorting descending data into ascending order).

Sorting Algorithms: Merge Sort and Bubble Sort

• Merge Sort: Uses a “divide and conquer” approach.
  • Process:
    1. Continually divide the list into equal halves until reaching single-item lists.
    2. Combine (merge) these lists back together in the correct sorted order.
  • Example: List 37, 14, 10, 27, 24, 19, 44, 35 is split and eventually reassembled into 10, 14, 19, 24, 27, 35, 37, 44.
• Bubble Sort: A simpler algorithm based on comparing and swapping adjacent items.
  • Process: Compares the first two items; if they are out of order, they swap. It repeats this throughout the list (one iteration). Iterations continue until no swaps are needed.
  • Limitation: Not suitable for large datasets.

Searching Algorithms: Linear and Binary Search

• Linear Search (Sequential Search): Each item in a dataset is compared with the search criteria in sequence.
  • Characteristics: Unordered data can be used. Every item might need to be checked (inefficient).
• Binary Search: A much more efficient method that requires sorted data.
  • Formula for Midpoint: $\text{mid point} = \text{low} + \frac{\text{high} - \text{low}}{2}$
  • Process:
    1. Compare search item to the midpoint.
    2. If the item matches, the search ends.
    3. If the search item is smaller, discard the upper half of the list. If larger, discard the lower half.
    4. Repeat on the remaining data.
  • Example Walkthrough: Searching for $31$ in a list with indices $0$ to $8$.
    • First midpoint: $4$ (value $29$). $31 > 29$, so discard lower half.
    • Second midpoint: $6.5$ (integer result $6$, value $37$). $31 < 37$, so discard upper half.
    • Final comparison: Index $5$ (value $31$). Match found in $3$ comparisons.

Web Development with HTML Standards

• Importance of Standards: Standardizing HTML ensures web browsers (Chrome, Safari, Firefox, Opera, IE/Edge) render pages consistently and allow developers to understand each other's code.
• Browser Usage Stats (December 2018):
  • Chrome: $62.9\%$
  • Safari: $14.3\%$
  • IE and Edge: $7.1\%$
  • Firefox: $6.2\%$
  • Opera: $3.0\%$
• HTML Tags and Elements:
  • Pairs: Usually have an opening tag (e.g., <html>) and a closing tag (e.g., </html>).
  • <head>: Container for document title, scripts, styles, and meta information (author, keywords, last altered).
  • <body>: Contains the webpage content.
  • <p>: Defines a paragraph; browsers add space around segments.
  • <a href="url">: Creates hyperlinks.
  • <img>: Displays images and does not require a closing tag (e.g., <img src="logo.gif">).
  • Formatting: <h1> to <h6> for headings; <b> for bold; <i> for italics; <center> for alignment; <ul> and <li> for bulleted lists; <blockquote> for quoted text; <hr> for horizontal rules to separate content.

Low-Level Programming: Assembly Language

• Levels of Languages: Hardware communicates via Machine Code ($0$s and $1$s). Assembly Language is low-level but uses mnemonics. High-level languages like Python and VB.NET are closer to English.
• Pros of Assembly Language: Requires less memory/execution time and allows direct hardware interaction (suitable for device drivers and time-critical processes).
• Mnemonics and Functions:
  • INP: Input value to accumulator.
  • OUT: Display accumulator contents.
  • STA: Transfer number from accumulator to RAM.
  • LDA: Transfer number from RAM to accumulator.
  • ADD: Add RAM address contents to accumulator.
  • SUB: Subtract RAM address contents from accumulator.
  • BRA: Branch (jump) to a location for loops.
  • HLT: Stop the processor.
  • DAT: Define variables.

Object-Oriented Programming (OOP) Concepts

• Fundamental Terms:
  • Objects: Entities with states (properties like name/breed) and behaviors (actions like moving/grunting).
  • Classes: Templates or blueprints for creating objects. Class names must begin with an uppercase letter.
  • Methods: Behaviors defined within a class. Method names must begin with a lowercase letter.
  • Instance Variables: Variables bound to specific class instances (objects). For example, multiple wombats each have a unique leaves variable to track personal consumption.
• Four Properties of OOP:
  1. Encapsulation: Wrapping code and data into a single entity (class).
  2. Abstraction: Showing essentials while hiding non-essential features (e.g., hiding internal states but showing behaviors).
  3. Inheritance: A derived (subclass) class inherits states and behaviors from a base (superclass) class. Example: Actor is a superclass for Wombat.
  4. Polymorphism: Actions performing differently based on the object (e.g., a makeSound() method makes a Wombat grunt but a Sheep bleat).

Greenfoot Coding and Data Structures

• Greenfoot Requirements: Programmers should be able to create/edit classes and worlds, invoke methods, move objects, handle keyboard input, play sounds, use collision detection, and implement inheritance and encapsulation.
• Data Structure Competencies: Ability to create 1D/2D arrays, files, and records.
• Data Types: Integer, Boolean, Real, Character, String.