Lesson 1.3: Algorithms

Question 1

Is defined as the finite sequence of instructions, each of which has a clear meaning and can be performed with a finite amount of effort in a finite length of time.

Answer 1

Algorithm

Question 2

IT is a set of steps, to accomplish a task.

Answer 2

Algorithm

Question 3

Optimization of a program is directly concerned with __________?

Answer 3

Algorithm Design

Question 4

Incremental approach to the construction of program structure. Modules are integrated by moving downward through the control hierarchy. Starting module is the main program.

Answer 4

Top-down design

Question 5

Works in opposite direction. Starting with specific modules and build them into more complex structures, ending at the top.

Answer 5

Bottom-up design

Question 6

This algorithm complexity deals with the amount of time it needs to run to completion

Answer 6

Time Complexity

Question 7

This algorithm complexity deals with the amount of space it needs to run to completion

Answer 7

Space Complexity

Question 8

Choosing an approach depending on the constraints.

Answer 8

Time-Space Trade-Off

Question 9

Is a characterization scheme that allows us to measure the properties of algorithms.

Answer 9

Big Oh

Question 10

The 7 algorithms. (CLLQPEF)

Answer 10

1. Constant time algorithm
2. Logarithmic time algorithm
3. Linear time algorithm
4. Quasilinear time algorithm
5. Polynomial time algorithm
6. Exponential time algorithm
7. Factorial time algorithm

Question 11

Algorithms under this class take a constant amount of time no matter how big is the problem. For example, taking the average of three numbers.

Answer 11

Constant time algorithm O(1)

Question 12

These algorithms typically divide the number of items it must consider by a fixed fraction every step. Usually, the base of the algorithm is 2 because inputs are being divided into two groups repeatedly.

Answer 12

Logarithmic time algorithm O(lg n)

Question 13

These algorithms go through all of the elements or inputs that they need to process. An example is finding the maximum (or minimum) of an array).

Answer 13

Linear time algorithm O(n)

Question 14

These algorithms loop over all the items and for each loop performs O(lg n) calculations on that item. Examples are some efficient sorting algorithms we will cover in Module 4 like quicksort, mergesort, etc.

Answer 14

Quasilinear time algorithm O(n lg n)

Question 15

These algorithms loop over the input, and for every input, loop over the inputs again (for the case of O(n2)). This is considered a polynomial runtime if runtime involves any polynomial involving n. A good example is of a polynomial algorithm O(n2) is bubble sort.

Answer 15

Polynomial time algorithm O(n^2), O(n^3), …, O(n^100), etc.

Question 16

These algorithms grow extremely quickly so these are practical only for small problems. An example is the knapsack problem.

Answer 16

Exponential time algorithm O(2^n)

Question 17

These are relatively inefficient algorithms that look for the optimal arrangement of the inputs. An example is the traveling salesman problem.

Answer 17

Factorial time algorithm O(n!)

Question 18

It indicates processing steps that are essential in the specification of any algorithm. Basically, the lines of codes are executed one after the other as they appear.

Answer 18

Sequence

Question 19

This provides the facility for selected processing based on some logical fact. For example, IF condition in Java.

Answer 19

Conditional

Question 20

When a set of instructions are executed a number of times.

Answer 20

Repetition

Question 21

In Java, _____ is still a reserved word but it does not have any function.

Answer 21

goto

Question 22

Such programming which gives exact readability and procedural flow to the reader is called __________.

Answer 22

Structured Programming