Paper 1

• Algorithm


  Set of rules or sequence of steps specifying how to solve a problem. The specification indicates that the steps indicated by the algorithm must terminate, but many disagree with this. An Algorithm generally contains an INPUT step, a PROCESSING step and an OUTPUT step.
• Data Types


  • Integers
  • Real (floats)
  • Boolean
  • Character
  • String
  • Date / Time
  • Arrays
  • Records (Struct)
• Program Constructs


  • Sequence
  • Selection
  • Iteration
• Sequence


  One statement after the other
• Selection


  Statements used to find which statement should be performed next, making use of conditional operators
• Iteration


  Two types - definite and indefinite. Definite has a clear assignment at the beginning of the loop of how many loop cycles would occur. Indefinite uses conditions, such as in a while loop, where the loop would occur while the condition is being met.
• Using Variables


  1. Declaration

  2. Assignment

  3. Use
• Identifier Names


  Names used for everything from variables to classes and functions. It is helpful to use useful identifier names as it makes the program more readable.
• Integer vs Float Division

  Integer division returns the answer without the remainder, float division returns the answer in decimal form. Modular division can be used to get just the remainder.
• Truncation


  Process by which the number of digits after the decimal point are limited
• Boolean Operations


  Effectively passing variables through logic gates, such as AND, OR, and NOT
• Variables vs Constants


  Variables are identifiers with values that change, constants are values that remain constant throughout the program
• Exception Handling


  Mechanism by which the program caters for any possible issues that occur through the running of the program, such as accessing non-existent variables
• Subroutines


  • Functions
  • Procedures
• Subroutines


  • Functions can return a result, procedures do not
  • Main program can pass parameters to subroutines
• Structured Programming


  Breaking a long program into a number of subtasks offers advantages like easier readability, editability, algorithm writing, and reduced complexity
• Hierarchy Charts


  Show the structure of the program, including how it flows, including subroutines and subroutines inside these subroutines. However, they don't show the detailed program structures in every module.
• Structure Charts


  Show the detailed program structures in every module
• Call Stack


  • Stores information about the active subroutines while a program is running, including holding return addresses, parameters, and local variables
• Recursive Algorithms


  Algorithms that call themselves, have a base case, and must call the base case after a finite number of calls
• Recursive Tree Traversal


  • In-order
  • Pre-order
  • Post-order
• Object Oriented Programming


  The world is seen as a collection of objects, each responsible for its own data and operations. Objects communicate by sending messages and receiving answers.
• Why Object Oriented Programming

  • Forces designers to go through an extensive planning phase
  • Encapsulation
  • Reusability
  • Software maintenance
• Objects


  Have attributes and a state, and behaviours (functions)
• Classes


  Blueprints or templates for objects, defining their attributes and methods
• Encapsulation


  An object encapsulates both its state and its behaviours and methods. Related to information hiding, where details of how a class can be used can be ignored when utilising this class.
• Inheritance


  Classes can inherit data and behaviour from a parent class. A child class is a subclass and parent class is a superclass.
• Relationships between classes


  • Association
  • Aggregation
  • Composition
• Polymorphism


  The ability to process objects differently depending on their class, using overriding
• Composition over Inheritance


  A less rigid relationship between objects, generally preferred over inheritance
• Program to an Interface

  An interface is a collection of abstract methods that a group of unrelated classes may be implemented. This ensures that all required features are implemented.
• Encapsulate What Varies


  Encapsulate concepts that are likely to change, to reduce maintenance and testing effort
• Static vs Dynamic Data Structures
• Static Data Structure


  Fixed in size, takes up this size forever
• Dynamic Data Structure


  Can grow or shrink in size, with the aid of a heap
• Abstract Data Types


  Logical descriptions of how data is stored and the operations that can be performed on it, not the implementation details
• Queue


  First In First Out (FIFO) data structure. New elements added to the end, elements retrieved from the front.
• Queue Operations


  • enQueue
  • deQueue
  • isEmpty
  • isFull
• Circular Queue


  Gets rid of the problem of the queue pointer eventually pointing to the first element
• Priority Queue


  Acts like a queue but the logical order is determined by the priority of the items, with the highest priority at the front