Computing Paper 2

Computing Paper 2

1. 2.1 - Elements of computational thinking

   • 2.1.1 - Thinking Abstractly
     • Abstraction is the action of removing unnecessary detail in order to make a problem easier to solve
     • Problem reduction is the process of generalising or reducing a problem to one that has already been solved.
   • 2.1.2 - Thinking Ahead
     • Preconditions
       • When faced with a problem for which you need to devise a solution, be aware that some possible solutions have preconditions
       • Important preconditions
         • Linear search
           • The data must be in a structure that is iterable (i.e. can be moved through one element at a time)
         • Binary search
           • The data must be in order and must be in a structure where elements can be directly accessed
         • Binary search tree
           • The data must be stored in a tree structure and ordered to allow a binary search
         • Hash table
           • The data must be stored in a hash table and the method of dealing with collisions must be understood
     • Inputs & Outputs
       • An input is data that will be entered into the system. Data can be entered manually or it can be automated. Many input systems are semi-automated.
       • The purpose of most computer systems is to process data to product output. Output is the result of processing and can appear in many forms. In traditional data-processing systems, information is usually produced in the form of static reports that are printed or displayed on a screen
     • Caching
       • Fetching data over a network is slow. When data is cached, a temporary copy is stored so that it can be accessed again faster. The ability to cache and reuse previously fetched resources is an essential technique in optimising system performance
   • 2.1.3 - Thinking Procedurally
     • What is structured programming?
       • Structured programming is a way of writing programs that emerged in the 1970s. It introduced a more disciplined approach to programming with the aim of improving the clarity of code.
     • Problem Decomposition
       • The structured approach uses a top-down method of problem solving. You start with a big problem and break it down into smaller and smaller problems. This process is referred to as problem decomposition and it is a 'divide and conquer' technique for solving large, complex problems.
     • Structure & hierarchy charts
       • When the problem has been decomposed, you can draw a structure or hierarchy chart. This is a schema that shows how the problem has been broken down/ Each discrete task will be shown as a box in the diagram, structured in a way that reflects the problem hierarchy
     • Coding the solution
       • When you have a clear set of single-purpose tasks, you can design the algorithms. An algorithm is a finite series of well-defined steps to solve a problem. At the design stage of a project, an algorithm ios typically expressed in pseudocode or as a flowchart. The procedural approach allows you to concentrate on one algorithm at a time
   • 2.1.4 - Thinking Logically
     • Logical arguments
       • An argument is a statement where the conclusion is supported by one or more additional statements. There are two main types of logical argument. In a deductive argument, the conclusion necessarily follows on from the premises; if the premises are true, the conclusion must be true. By contrast, an inductive argument seeks to make a strong case to support the conclusion; if the premises are true, the conlcusion is higly likely to be true.
     • Truth tables
       • A truth table is a efficient way of laying out a logical argument
   • 2.1.5 - Thinking Concurrently
     • Solving a problem using computational methods needs to have certain characteristics:
       • The problem needs to be clearly defined
       • The problem needs to be computable
       • The data requirements of the problem need to be examined
       • You should be able to determine if the problem can be approached using decomposition and abstraction
     • Problem recognition
       • The first step in solving a problem is to perform problem recognition, meaning that you need to examine the description of a given scenario in order to:
         • Identify the nature and parameters of the problem
         • Undertake a thorough analysis of the current situation
         • Specify the problem requirements or success criteria
         • Identify whether the specifics of the problem allow it to be classified as a certain type of problem
     • Backtracking
       • Backtracking is a method that is used in solving a problem that involves examining more than one possible solution. Backtracking algorithm often use recursion in order to move from one state of the problem to another. In every step, the possible options are examined, and a decision is made about which option to follow. When the algorithm reaches a final state, it checks whether that state is accepted or rejected and then 'backtracks' to a previous state to try other options that have not yet been examined
     • Data Mining
       • Data mining is the process of extracting valuable information from large data sets; it can be thought of as turning data into knowledge.
     • Heuristics
       • A heruistic, or heuristic technique, is any approach to problem-solving that uses a practical method or various shortcuts in order to produce solutions that may not be optimal but are sufficient given a limited timeframe or deadline
     • Performance modelling
       • Performance modelling, often called performance testing, is a process of eveluating if a system or a program works as expected or not before it is released, and using this knowledge to make it more effective
     • Pipelining
       • In programming, pipelining refers to when a task is divided into a series of subtasks, where each subtask leads to the next. This means that each subtask to executed by a different process in a series, so that the result of a process feeds into the next one, and this is repeated until the whole task is completed
     • Visualisation to solve problems
       • Visualisation includes a variety of techniques that aim to illustrate what a problem entails, and how to approach its solution.
       • Benefits of visualisation techniques
         • They can be used to explain complex tasks, scenarios, or situations
         • They can be used to model, represent, analyse, or summarise concepts, data, or processes
         • They can present information more efficiently and in ways that are easier to understand
         • They can offer alternative views as to how to solve problems

2. 2.2 - Problem solving & Programming

   • 2.2.1 - Programming techniques
     • Sequence
       • By default, programs run instructions in sequence, one after another in the order which they are written.
       • Nested Selection
         • Nested selection is used to implement branching logic. This means that if a condition of a main selection block evaluates to True, then it leads to sub-conditions, which are included inside that condition
     • Iteration
       • For loops
         • for loops are used to repeat a section of code for a specific number of times, which is why they are known as count-controlled loops
       • While loops
         • Often you will need to repeat a section of code for as long as a condition is met, or until a condition is met. This is what is known as a condtion-controlled loop
         • While loops check the condition at the start of every iteration; this is known as a pre-condition loop. If the condition initially evaluates to False then the code within the while loop will not run, not even once
       • Nested iteration
         • Nested iteration is when a loop is included inside another loop. The inner loop will be executed from the start to the end value repeatedly for all the iterations of the outer loop.
     • Recursion
       • Recursion is the ability of a subroutine to call itself. A recursive call makes use of a stack and stack frames to store the data from each depth of function call. There are some problems for which a recursive algorithm is the natural choice, for example, a recursive algorithm is the natural choice, for example, a recursive tree traversal or the standard algorithm for a merge sort.
       • Rules for recursion
         • Must have a base case
         • Must change its state and move toward the base case and eventually reach it
         • Must call itself at some point
     • Local & Global variables
       • The scope of a variable refers to where in the program a variable or constant can be accessed. The scope of a variable can either be local to a particular subroutine, or port of a subroutine, or global to the whole program
       • Local variables
         • A local variable that is only accessible within a specific part of a program. Local variables are usually local to a subroutine and are declared or defined within that routine. Parameters that are defined by value can also be considered as local variables
       • Global variables
         • A global variable can be accessed anywhere in a program for the duration of the program's execution. A global variable has global scope. GLobal variables need to be preserved in memory until the program has stopped running. This means global variables can sometimes use more resources than local variables, which are removed from memory once a subroutine has ended
     • Modular programming
       • Modular programming is the process of subdividing a computer program into separate sub-programs
     • Functions & Procedures
       • Subroutines can be referred to as functions or procedures. A procedure just executes a set of instructions, whereas a function will return a value when it has finished executing
     • Passing by value or by reference
       • Passing by value
         • When an argument is passed to a subroutine by value, each parameter specified for the subroutine will hold a copy of the data from the original argument
       • Passing by reference
         • When an argument is passed to a subroutine by reference, this creates a pointer that contains the memory address of the original variable. Therefore, any chance to the parameter within the subroutine also affects the value of the original variable
     • Using an IDE to develop/debug a program
       • An IDE is an integrated development environment. Programs are simple text documents and, to create a program, you only need a text editor to enter your code. However, most programming language downloads include an IDE, and these will offer a range of features that will help you develop code
       • Autocomplete
         • Autocomplete is a common feature of an IDE. Autocomplete is a software function that completes words or strings without the user needing to type them in full.
       • Debug tools
         • Most IDEs offer debug tools as well as instant logic and error checking. The ability to trace the value of variables and set breakpoints can be very useful for debugging code. Some IDEs allow you to step through code line by line, and examine the value of variables as you proceed, so that you can see exactly what is happening
       • Running code
         • Most IDEs will allow you to run your code. The IDE must include a relevant translator or must be configured to access a translator that is installed elsewhere. Where a language is compiled, the IDE will usually allow some form of interpretation to allow for development 'on the fly' without requiring full compilation every time the code is changed.
       • Version Control
         • Version control is a feature that wiull record changes that have been made to a prgram file over time. Every time you make a change, you record a note that explains what has been modified. This allows you to find and recall a previous version if you 'mess up' your code
     • Object-oriented Programming
       • Object-oriented programming is an approach to systems development that is focused on objects and the way that they interact. Code is written to define objects and classes, and certain principles such as encapsulation, inheritance and polymorphism are important to the design of an object-oriented program
       • OOP fundamentals
         • OOP programs contain the use of objects, attributes and methods, as well as class definitions. To create an object, you instantiate one and OOP programs also make the use of a constructor
         • Attributes
           • Each attribute is a data item that helps define or describe the object
         • Methods
           • Methods are procedures and functions that access or modify the values of the attributes of an object. Methods must define every operation that is allowed to be carried out on an attribute
         • Class definitions
           • A class definition is a blueprint that defines the properties of all objects of the same type. Each object is one of a group of similar objects, and you define the group as a class. The class definition will describe every object of that type.
         • Constructor
           • Each class will usually have a special method called the constructor. The constructor will carry out any actions that are needed when an instance of the object is create from the class definition. Typically, the constructor will set the initial values of the attributes. These can be default values or values passed in as arguments.
       • Encapsulation
         • Encapsulation binds together the attributes and the methods that manipulate the data. It does this so that the data is protected.
         • Getter and setter methods
           • A getter is a method that gets the value of a property. A setter is a method that sets the value of a property
       • Inheritance & Polymorphism
         • Inheritance is the act of a child or sub class, inheriting attributes and methods of the original (superclass)
         • Polymorphism refers to the ability of a method to exhibit different behaviours depending on the object on which the method is invoked
           • When a subclass is defined, it can override any of the methods inherited from the parent class. Overriding means changing the code. Overriding is a form of polymorphism

3. Algorithms

   • Time complexity
     • There are 6 types of time complexity
       • Constant
       • Linear
       • Polynomial
       • Exponential
       • Logarithmic
       • Factorial
     • Time complexity of sort/search algorithms
       • Linear search
         • Linear
       • Binary Search
         • Logarithmic
       • Binary tree search
         • Logarithmic
       • Bubble sort
         • Polynomial
       • Merge Sort
         • Logarithmic
   • A good algorithm
     • Has clear and precisely stated steps that produce the correct output for any set of valid inputs
     • Should allow for invalid inputs
     • Must always terminate at some point
     • Should execute efficiently, in as few steps as possible
     • should be designed in such a way that other people will be able to understand it and modify it if necessary