Algorithms: Question Set – 04
A computer algorithm gets “translated” into a programming language to take the form of a programme. It’s not uncommon to hear phrases like “procedure,” “function,” and “subroutine” used interchangeably with “programme.”
What are the different criteria used to improve the effectiveness of algorithm?
(i) The effectiveness of algorithm is improved, when the design, satisfies the following constraints to be minimum.
- Time efficiency – how fast an algorithm in question runs.
- Space efficiency – an extra space the algorithm requires
(ii) The algorithm has to provide result for all valid inputs.
How will you measure input size of algorithms?
- The amount of time an algorithm needs to complete its task is proportional to the magnitude of the data it receives.
- So the execution time of the programme relies on the size of its input.
- The size of the input is indicated by the parameter n, which is the number of items in the input; this number is used to calculate the size of the input for the algorithm.
Give the two major phases of performance evaluation
Performance evaluation can be loosely divided into two major phases:
- A prior estimates (performance analysis)
- A Posterior testing (performance measurement)
Define input size.
When referring to a particular instance of a problem, the “input size” is defined as the number of words (or the number of items) that are required to adequately explain that particular case.
Define the terms: pseudocode, flow chart
- A natural language is combined with structures that are similar to those found in programming languages to create a pseudocode.
- Pseudocodes are typically capable of higher levels of precision than natural languages.
- A flowchart is a method of expressing an algorithm that consists of a collection of connected geometric shapes that contain descriptions of the steps that are involved in the algorithm.
Define the divide an conquer method.
- The divide-and-conquer technique advises, when presented with a function to compute on ‘n’ inputs, breaking those inputs into ‘k’ separate subsets, where 1 < k < n, which results in ‘k’ subproblems.
- After each of the subproblems has been addressed, a strategy for combining the individual solutions into a whole-problem solution needs to be developed.
- It is possible to reapply the divide-and-conquer technique if the individual problems still constitute a sizeable portion of the overall issue.
What do you mean by Combinatorial Problem?
Combinatorial problems are questions that challenge you to find a combinatorial item (such a permutation, a combination, or a subset) that fulfils certain restrictions and has some desired attribute. These problems can be broken down into three categories: