I .chp 1. The Role of Algorithms In Computing

Question 1

What are Algorithms?

Answer 1

An algorithm is thus a sequence of computational steps that transform the
input into the output.

Or also a tool for solving a well-specified computational problem.

An algorithm can be specified in English, as a computer program, or even as
a hardware design. The only requirement is that the specification must provide a
precise description of the computational procedure to be followed.

Question 2

Instance of a problem:

Answer 2

In general, an instance of a problem
consists of the input (satisfying whatever constraints are imposed in the problem
statement) needed to compute a solution to the problem.

Question 3

Correct Algorithm means what?

Answer 3

An algorithm is said to be correct if, for every input instance, it halts with the
correct output.
We say that a correct algorithm solves the given computational
problem.

Question 4

Convex Hull:

Answer 4

The convex hull is the smallest convex polygon containing the
points.

Question 5

Sorting problem

Answer 5

Input: A sequence of n numbers [a1; a2,….,an].
Output: A permutation (reordering) [ a1,a2,…,an] of the input sequence such that a1 <= a2 ....<= an.

Question 6

Data Structure

Answer 6

A data structure is a way to store

and organize data in order to facilitate access and modifications.

Question 7

Traveling-salesman problem:

Answer 7

Consider a delivery company with a central depot. Each day, it loads up each delivery truck at the depot and sends it around to deliver goods
to several addresses. At the end of the day, each truck must end up back at the depot
so that it is ready to be loaded for the next day. To reduce costs, the company wants
to select an order of delivery stops that yields the lowest overall distance traveled
by each truck.

Question 8

Use of Algorithms:

and why should they be efficient?

Answer 8

Time and space (memory ) are resources which should be used wisely. Better algorithms takecare of them.
A more efficient Algorithm will help us even with rusty compilers and slow computers..
Algoriths whose growth is slow, cool.
Merge sort : Cnlogn
Insertion Sort: C`n^2
The advantage of merge sort is even more pronounced when we sort 100 million numbers:
where insertion sort takes more than 23 days, merge sort takes under four hours.

It is at larger problem sizes that the differences
in efficiency between algorithms become particularly prominent.

Question 9

Algorithm as technology:

Answer 9

We should consider algorithms, like computer hardware, as a technology. Total system performance depends on choosing efficient
algorithms as much as on choosing fast hardware. Just as rapid advances are being
made in other computer technologies, they are being made in algorithms as well.

Question 10

Is algo really neccesary when we have:
advanced computer architectures and fabrication technologies,
easy-to-use, intuitive, graphical user interfaces (GUIs),
object-oriented systems,
integrated Web technologies, and
fast networking, both wired and wireless.

Answer 10

Moreover, even an application that does not require algorithmic content at the
application level relies heavily upon algorithms. Does the application rely on fast
hardware? The hardware design used algorithms. Does the application rely on
graphical user interfaces? The design of any GUI relies on algorithms. Does the
application rely on networking? Routing in networks relies heavily on algorithms.
Was the application written in a language other than machine code? Then it was
processed by a compiler, interpreter, or assembler, all of which make extensive use of algo.