222-computational-methods

Question 1

Computational thinking

Answer 1

• The ability to think systematically about a problem and apply techniques for solving it
• techniques: data mining, heuristics, visualisation, backtracking, pipelining, performance modelling

Question 2

data mining

Answer 2

• looks through vast quantities of unconnected data, finding a correlation between data that may not be obvious
• There may no predetermined matching criteria
• Pattern matching algorithms/brute force approach possible with high speed computers/ big data analysis software
• parallel processing to speed up

Question 3

data mining applications

Answer 3

• increasing response rates/sales/profits
• improve marking
• target more accurately to customer needs
• anticipating resource demands
• detecting fraud and cybersecurity issues
  -finding hidden connections between seemingly unconnected events,
• predict n plan future trends/events
• used for business modelling

Question 4

Limitations of data mining -

Answer 4

• powerful computers and vast processing requirements
• privacy concerns, personal data, GDPR, transparency, consent
• misuse
• inaccurate information can produce false results
• bias

Question 5

Challenges in producing a solution to a computational problem

Answer 5

• algorithm must be correct and work for all possible inputs
• algorithm must be efficient
• algorithm can solve it within finite steps in realistic time
• limitations: hardware, memory & time requirement, big o complexity

Question 6

Programming standards why

Answer 6

for modules to be reusable they need to conform to these so it’s easy to use for other programmers + maintainability

Question 7

Programming standards what

Answer 7

• naming conventions: consistent, understandable names. Easier for developers to know their purpose, and reduce chance of duplication (reusing). camel Case variables, Pascal Case classes, upper case constants
• clear documentation: preconditions, classes and functions expected behaviour comments, explain nonobvious logic
• code length: function no longer than a page: reduce complexity, focused, manageable
• each function single-entry points with exit point: consistent starting execution (e.g if statement making it nest start at different places violates), and not premature/inconsistent multiple points of return e.g return in loops
• Restrict variable scope - avoid global, local isolation

Question 8

Backtracking when

Answer 8

• each decision leads to new choices (generation)
• more than one sequence could be a solution (combinations & permutations, crosswords, puzzles)
• pathfinding (maze)
• uncertainity on optimal (maximise/minimise, allocation, exploration)
• searching/traversing (graphs/trees)
• predict outcomes (games)
• constraint satisfication (sudoku)

Question 9

Backtracking

Answer 9

recursive algorithm.
takes one path as far as possible. when node does not have any nodes to visit (dead end)/ abandons each partial success if determined that it cant be completed
returns to previous node (decision point) and checks for further nodes to visit/aternative solution
- Repeats until solution is found.
- suitable for route problems, depth first search

Returning to a previously successful result to find an alternative solution
Abandons each partial success as soon as it determines that the partial solution cannot possibly be completed

• finds all (or some) solutions

Question 10

Heuristics

Answer 10

• problem is complex to that perfect solution would be very difficult/impossible to find
• So can get a solution that is good enough, no guarantee of being most optimum for practical purposes
• purpose: Finding a reasonable solution in a reasonable time.
• may involve using extra knowledge to reduce time complexity
• approx solution to intraceable problems

Question 11

Heuristics example

Answer 11

A* algorithm.
Crow’s path heuristic
- difficult to calculate all the possible routes from gas flow to London on a car sat nag so pathfinding algorithm is led in the general direction to save time and processing power. Or when crossing the road: don’t gather all data about vehicle speeds, we scan the data most likely to help us and make a judgement based on experience

Question 12

performance modelling

Answer 12

• ## computational modelling (simulation) using mathematical approximation and data provided to test system behaviour (performance) and capabilities in scenarios/workloads-reduce extensive true performance testing reliance (expense, time, no loss, safer)
• testing how system will respond to normal (load), and heavy load (stress) and traffic/weaknesses/conditions
• validation, early error detection, risk management, resource allocation

Question 13

enumeration algorithm

Answer 13

an algorithm that performs an exhaustive search, attempts all solutions until correct one is found

Question 14

theoretical approach

Answer 14

representing a problem using mathematical equations

Question 15

simulation

Answer 15

using computer system to model real life situation to attempt to understand its behaviour
makes use of abstraction
e.g climate change, financial risk analysis

Question 16

automation

Answer 16

• targets repetitive predictable problems
• process of building system/program that is put into action to run automatically/independently with minimal human intervention
  makes use of abstraction

Question 17

problem recognition

Answer 17

• identifying and defining the problem, it’s issues and its requirements, may involve stakeholders
• analysing strengths and weaknesses with existing, nature of problem, limitations/constraints, desired outcomes, resources needed
• determining inputs, outputs, data stored, data size
• initial requirements and definitions can evolve

Question 18

divide and conquer

Answer 18

• breaking problem down by halving it every iteration/recursively
• into sub problems until they become simple enough to solve individually
• reduce comp complexity in scale, parallelism
• solutions of sub problems are combined
• if implement recursive, problems: stack overflow will cause program to crash, large programs are difficult to trace
• space, not always

Question 19

visualisation

Answer 19

-when data/problem and processes are represented in a visual or graphical format
problems easier to solve, presented in a easier to understand way
- identify trends/patterns otherwise not obvious to inform decisions
- for the mind to process, clears up confusion
- e.g flowcharts, graphs

Question 20

tractable problem

Answer 20

any problem that can be solved in a polynomial time or better
runs quick enough to be practical and useful
has computable features /can be solved using computational methods

Question 21

intractable problem

Answer 21

• any problem that cannot be solved in polynomial time or better.
• as the input size increases to anything other than a very small data set, a computer can’t solve it within a reasonable timeframe. - approx solved using heuristics