2.2 - Problem Solving and Programming

Page 1

2.2.1 - Programming Techniques

Constants and Variables Basics:

Values of constants never change whilst the program is being run:

There is no chance that a programmer will accidentally change its value in a long and complex program.

Variables are identifiers given to memory locations, whose contents will change during the course of a program.

Variable Name Standards:

Start all variable names with a lowercase letter.

Do not ues underscores in variable names.

Use "camelCaps" to separate parts of variable names.

Do not have overly long names, but keep them meaningful.

Use all uppercase letters for constants.

When defining a class in object-oriented, start with an uppercase letter.

Recursion:

A subroutine is recursive if it is defined in terms of itself.

Three essential characteristics:

A stopping condition must be included where the routine will not call itself and begin to unwind.

For input values other than the stopping condition, the routine must call itself.

The stopping condition must be reached after a finite number of calls.

Global and Local Variables:

Global:

Used in the main program.

Can be used anywhere in the program, including subroutines.

Local:

Can be used within the subroutine they are defined in.

Only exists during the execution of a subroutine.

Changing them has no effect outside the subroutine.

Benefits:

Each subroutine is completely self-contained and independent of any global variables.

Encapsulation allows for independent testing of subroutines, where a programmer using it does not need to know what variables it uses.

Any variable that has the same name in the calling program as a local variable declared in the subroutine will not cause any unexpected side effects.

Modularity:

Breaking down the problem into a number of sub-tasks, using a top-down approach.

Subroutines:

Small enough to be understandable, so easy to debug and maintain with clearly documented information.

Subroutines can be tested independently.

Subroutines can be reused with confidence once it has been fully tested.

Each programmer working on a large project can be given a set of subroutines to work on.

Larger projects are easier to control and maintain.

Functions:

Returns a value.

Procedurs:

Peforms a command - does not return a value.

Passing By Value:

The actual value of the parameter is passed to the subroutine, where it is treated as a local variable.

Changing the value in the subroutine does not change the value outside of it.

Passing By Reference:

The address of the parameter is passed to the subroutine.

Its value in the main program will reflect any changes in the subroutine.

Usage of an Integrated Development Environment (IDE):

Used for creating programs in their given languages.

Provides tools to enter, edit, compile test and debug programs.

Tools used for debugging:

Breakpoints - causes the program to stop on the specified line, so that you can see if it reaches it or not.

Watch - set on a variable, to see its value whenever it changes.

Step Through - goes through each line in the program at a time to see what happens.

Testing Strategies:

Black Box Testing:

Carried out independently of the code.

Looking at the program specification, creating a set of test data that covers all inputs and outputs and program functions.

White Box Testing:

Dependent on the code logic, and derives from the program structure rather than its function.

Program code is studided and test are devised which test each possible path at least once.

Will not detect any missing functions.

Alpha Testing:

Often carried out by the developer's inhouse testing team.

Reveals both eorrs and omissions in the system requirements.

Beta Testing:

Gives the package to a number of external users, who will provide feedback and report any problems to the developers.

Exposes the product to real use and detects unanticipated problems.

Test Data:

Normal Data:

Data within the range that would be expected, and of the data type expected.

Boundary Data:

Data at the very extreme ends of the intended range.

Erroneous Data:

Data that is outside the expected range, or a completely different data type than expected.

Object-Oriented Techniques:

Everything is viewed as a collection of objects, such as a person, animal or place.

An object-oriented program is created with a number of interacting objects, each of which is responsible for its own data and data operations.

Objects:

Each object has its own attributes, such as colour, size, name.

Each objects has a state, such as on or off.

Classes:

A template for an object, often defining the attributes and methods of objects in that class:

An attribute is data associated with the class.

A method is a functionality of the class - something that it can do.

Objects belonging to a class are an instance of the class.

Private and Public:

Instance variables or attributes are declared as private.

Most methods are declared as public, so that other calsses may use methods belonging to another class but cannot change their attributes.

Instantiation:

The creation of a new object.

A constructor is used to create objects in a class.

Encapsulation:

An object encapsulates both its state and its methods.

All the data and methods of each object are wrapped into a single entity so that they cannot affect the way in which another object functions.

Information Hiding:

Details of an object's instance variables are hidden so that other objects must use messages to interact with that object's state.

Inheritance:

Classes can inherit data and methods from a parent class.

A child class is referred to as a subclass.

A parent class is referred to as a superclass.

Inheritance diagrams are like trees, except there are arrows which go upwards towards the superclass.

Subclasses may have their own attributes and methods.

Polymorphism:

The ability for a language to process objects differently depending on their class.

Defining a method with the same name and formal argument types as a method inehrited from a superclass is called overriding.

Page 2

2.2.2 - Computational Methods

Computable Problems:

A problem is defined as being computable if there is an algorithm that can solve every instance of it in a finite number of steps.

Intractable Problems:

An algorithm may exist for their solution, but it would take a very long time to find the solution.

Example:

Travelling Salesman Problem.

For larger problems, the time taken to solve will increase dramatically.

Methods of Problem Solving:

Enumeration:

Using an exhaustive search, trying all possible solutions until the correct one is found - known as brute force in encryption.

VERY inefficient.

Number of possible solutions increase exponentially as the size increases.

Simulation:

The process of designing a model of a real system in order to understand the behaviour of the system.

Makes use of abstraction to reduce the problem down to its essentials.

Useful for replacing expensive physical models, such as building spacecraft.

Strategies for Problem Solving:

Divide and Conquer:

Reduces the size of the problem with every iteration, breaking it down into smaller and smaller parts.

Problem Abstraction:

Removing details until the problem is represented in such a way that it is possible to solve because it reduces to one that has already been solved.

Problem Solving:

Visualisation:

The manner in which a problem is presented.

Makes it easier to view the problem at hand, and thus how to handle it.

Example:

A table of a binary tree can be represented as a graph.

Backtracking:

A methodical way of trying out different sequence until you find one that leads to a solution.

Example:

A maze, or a depth-first traversal.

Data Mining:

The process of digging through big data sets to discover hidden connections and predict future trends.

Big data is the term used for large sets of data that cannot be easily handled.

Big Data Analysis:

Massive benefits in healthcare, business, communication, speech recognition, banking.

Heuristic Methods:

Finding an approximate or good-enough answer (mostly to intractable problems).

Solve a simpler or restricted version of a problem.

An approach that uses an algorithm not guaranteed to be optimal is called a heuristic approach:

The objective is to find a good solution in a reasonable time frame.

Performance Modelling:

The process of simulating different user and system loads on a computer using a mathematical approximation, rather than doing actual performance tests which may be difficult and expensive.

Example:

It could be used to test the performance of a network under different conditions.

Pipelining:

The technique of splitting tasks into smaller parts and overlapping the processing of each part of the task.

Used in processors:

While one instruction is being fetched, another is being decoded and another is being executed.