Course week 2

The topics for this week are as follows: (i) Algorithm efficiency; introduction, (ii) Sharing data, (iii) Recursion

The following links will take you to the video-lectures and the accompanying slides:

Algorithm efficiency¶

Algorithm efficiency part 1.

Algorithm efficiency part 2.

slides for Algorithm efficiency

Sharing data¶

Sharing data.

slides for Sharing data

Recursion¶

Recursion part 1.

Recursion part 2.

Recursion part 3.

slides for Recursion

Week02 - Glossary

Lecture-questions¶

Question 1

What do we actually measure when measuring an algorithm’s efficiency?

The number of executed operations

Milliseconds

The number of variables used in the algorithm

The number of lines of code in the algorithm’s pseudocode

Question 2

Why is the asymptotic performance of an algorithm interesting?

With it the number of code rows in the implementation can be estimated

With it, we know how quickly the amount of computations the algorithm increases as the size of the input data increases.

It allows a very precise measure of the implemented algorithm ’s true runtime

Question 3

Choose the correct claims. (There may be more than 1).

An algorithm’s asymptotic performance always gives precise values for the algorithm’s performance.

Using asymptotic performace we can compare two alternative algorithms for computing the same task.

The asymptotic performance indicates the rate an algorithm slows down when the amount of data grows.

An efficient algorithm is one that always slows down very quickly as the amount of data grows.

Question 4

Why is measuring the amount of time an algorithm takes to compute the solution not a feasible way to measure an algorithm’s efficiency?

One can never know when an algorithm has stopped computing.

There does not exist any clock that is accurate enough to measure the computational time of any algorithm on any computer.

The amount of time depends on too many factors.

If there exists a better algorithm, then measuring the computational time of a weaker algorithm is futile.

Question 5

Suppose we have pseudocode for some algorithm A and we are given the efficiency analysis for this pseudocode. What can we do with this efficiency analysis?

We can compute exactly the computational time of algorithm A for some given input on some given computer.

We can state exactly the situations when algorithm A will compute correctly and those when it will fail.

If algorithm B exists for solving the same problem as algorithm A and we have the efficiency analysis for algorithm B as well, then we can compare the efficiencies of A and B.

We can state exactly how many variables algorithm A uses.

Question 1

In what aspects of programming does wise data sharing help? (There may be several correct choices.)

in the upkeep of the data

in making the code more readable and understandable

in preventing unnecessary waste of storage

in speeding up the execution time of the code

in writing the code

Question 2

Suppose computer language X uses value semantics and computer language Y uses reference semantics. Suppose a large object A exists and we have the following code line: B=A. Which of the following is incorrect?

In Y both A and B refer to the same object.

After the code line B = A has been executed, both X and Y use the same amount of memory.

A and B occupy different areas in memory in X.

Question 3

Suppose in C++ each element of array A contains a large object. Several techniques can be used to share the elements of A: pointers, smart pointers, indices and so on. Which of the following are true? (There may be several that are true.)

All the different ways of sharing have automatic garbage collection if some element in A is destroyed.

Each technique requires the formation of some auxiliary data structure (or data structures) for referring to the elements of A.

If we use one of the techniques, then we can no longer make a copy of A.

By using some auxiliary data structure, we can effectively process the elements of A in some particular order without actually having to change A at all.

In a single C++ function one may not use more than one sharing technique.

Question 1

Recursion is very useful because

a recursive procedure always has better performance than a corresponding iterative procedure

one never has to use for-loops, while-loops or if-statements in a recursive procedure

big problems that can broken into smaller versions of the same problem

a recursive procedure only contains trivial (base) cases

Question 2

When a recursive procedure is executing, which of the following statements about the call stack is true? (There may be more than one true statement.)

The parameters (or arguments) to the procedure are different at different levels in the stack.

The programmer must explicitly include code in the procedure that keeps track of the stack size.

The call stack can be thought of as an ordered collection of all calls to the procedure that have not yet been completely executed.

Once a call is added to the call stack, it cannot ever be removed.

When a recursive procedure executes a trivial (or base) case, the call stack is always emptied.

Question 3

Suppose array A contains numbers that are ordered from smallest to largest and we use a recursive binary search to search for an element. Which of the following statements are true? (More than one may be true.)

We only execute the trivial (or base) case when the smallest element of A is larger than the element for which we are searching.

Each time the binary search algorithm is called, both the left and right locations change.

If at some recursion level we are searching from a subarray of size m and m >= 2, then at the next recursion level we will be searching from a subarray whose size is at most (m+1)/2.

In a recursive (or non-trivial) case, a location that is midway between the left and right locations is always computed.

Question 4

Suppose X is a recursive procedure. Which of the following is true regarding the cases that are present in X?

In a base (or trivial) case, X calls itself once and in a recursive case X calls itself at least twice.

In both a base (or trivial) case and a recursive case, X can call itself.

In a base (or trivial) case X can only call itself but not any other procedure, and in a recursive case X can call any other procedure but itself.

In a base (or trivial) case, X does not call itself and in a recursive case X calls itself at least once.

Question 1

What is a central question, related to this course, whose answer can be found in this week’s videos?

Question 2

Of the following topics, which do you think deserves further discussion/explanation during the weekly consultation session?

algorithm efficiency

data sharing

recursion

Question 3

Were there any parts of the video lectures that were particularly difficult? Particularly interesting? Something about which you wish to learn more?

Course week 2¶

Self-study (in English)¶

Algorithm efficiency¶

Recursion¶

Lecture-questions¶

Submit weekly exercises¶