Structured Programming and Problem Solving

Structured Approach:

• This approach aims to improve the clarity and maintainability of programs.
• Sequence, selection, and iteration are the 3 basic programming structures used.
• Languages like Python are "block-structured" which allows the use of just three control structures. Allowing you to break out of a loop.
• In structured programming, this is not recommended because each block should have a single entry and exit point.

Tools for Designing Algorithms:

1. Flow diagrams and pseudocode are commonly used for designing algorithms.
2. Pseudocode is generally more useful.
3. Most logic errors occur at decision blocks.

Did I just add that to use an ordered list? Yes.

Thinking Concurrently:

• Parallel computing:
  • Requires multiple processors each executing different instructions simultaneously, with the goal of speeding up computations. This is impossible on 1 processor.
  • Advantages:
    • Enables multiple tasks to be performed simultaneously by different processors, speeding up processing enormously when repetitive calculations need to be performed on large data sets.
    • Graphics processors can render things quickly.
    • Browsers can display several things without being held up by one lengthy search query/operation.
  • Disadvantages:
    • There is an overhead in coordinating the processors and some tasks may run faster with a single processor than multiple (recurrence relations).

Problem Recognition:

Computable Problems:

Computable problem: A problem is computable if there is an algorithm that can solve every instance of the problem in a finite number of steps.

Methods of Problem Solving:

• Enumeration
  • Basically an exhaustive search, trying all possible solutions until you get the best one.
  • As problems scale in input, the efficiency of these problems is quite poor and runtime grows exponentially.
• Simulation
  • Designing a model of a real system in order to understand the behaviour of the system and evaluate various strategies for its operations.
  • Usually, this involves abstraction to only simulate relevant details of the problem.
  • Simulation can also be physical.
• Theoretical Approach:
  • OCR doesn't really explain this….

Graphs:

A strategy after initially abstracting a problem to a graph is "graph unfolding" which basically means constructing a clearer, isomorphic graph (to the original).

This particularly helped in problems such as the "knights tour" we covered in lesson, allowing us to quickly see the winning strategy.

Problem Solving:

Visualization:

Usually consists of thinking of the problem as a graph, removing many unnecessary details or spotting a nice trick which trivializes the problem.

Backtracking:

Backtracking algorithms begin with an empty solution and extend the solution step-by-step. It recursively goes through all of the different ways that a solution may be constructed. An example of this is a depth-first-search.

Data Mining:

The process of digging through big data sets to discover hidden connections and predict future trends. YouTube uses this to recommend "good videos" by looking at variable data points provided by its many users, or Google on how "happy" a user is with its speech recognition when searching (do they retry the search because what they said was not correctly transcribed).

Intractable problems

Problems that would take an unreasonably long time to find a solution. For example, the travelling salesman problem.

The optimal solution for this problem may be found using brute force, but the runtime to find this solution grows exponentially with the number of towns added. (time complexity of O(n!) as it checks every combination of routes for n towns)

Problems like these are often Heuristically solved. We would rather find a near-optimal solution in a short amount of time than find the optimal solution in a very long amount of time because the near-optimal solution is good enough for its purpose. For the travelling salesman problem, programmers have used techniques such as simulated annealing to find a near-optimal solution.

Performance Modeling:

The process of simulating different user and system loads on a computer using a mathematical approximation, rather than doing actual performance testing which may be difficult and expensive. For example, used to test the performance of a network under different conditions, generally used to assist with planning a new system which is suited to the requirements of an organization.

Pipelining:

Splitting tasks into smaller parts and overlapping the processing of each part of the task. Often used in microprocessors so that while one instruction is being fetched, another is decoded and a third executed. (like an assembly line)

A nicer "conceptual" definition is doing multiple tasks step by step, but instead of waiting for one task to finish before starting the next, we start the next task as soon as we finish the first step of the previous one. This is possible because you can wait for data and instructions in a "logical pipeline".