Course topics 1 and 2¶

This page has a summary of all the course activities you can attend or submit this week.

Weekly exercises sessions¶

No weekly exercise sessions this week (they start on lecture week 3).

Self-study (videos and slides in English)¶

The topics for this week are as follows: (i) Algorithms and pseudocode, (ii) Decrease-and-conquer, (iii) Insert sort

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

Algorithms and Pseudocode¶

Algorithms and Pseudocode part 1.

Algorithms and Pseudocode part 2.

Algorithms and Pseudocode part 3.

From pseudocode to implementation.

slides for Algorithms and Pseudocode

slides for From pseudocode to implementation

Decrease-and-conquer¶

Decrease-and-conquer.

slides for Decrease-and-conquer

Insertion sort¶

Insertion sort part 1.

Insertion sort part 2.

slides for Insertion sort

Week01 - Glossary

Lecture-questions¶

Question 1

An algorithm is

a computer program written in some programming language like C++ or Java

the hardware in which a computer program runs

a description of a method for solving a problem

a collection of data or information or material needed to solve some problem

Question 2

Which of the following are important properties of a well-specified algorithm? (There may be more than one correct choice.)

Each step or instruction in an algorithm should have only one possible interpretation.

The order in which the algorithm steps are to be done must be unique.

The algorithm must be presented in some programming language like C++ or Java or Python.

Each step or instruction in an algorithm must correspond to exactly one line of programming code.

The only people who can understand or use the algorithm are those who created it.

Question 1

Suppose person X presents an algorithm using pseudocode and person Y reads it. What assumptions can X make about Y? (There may be more than one correct choice.)

X can assume that Y intends to write C++ from the pseudocode.

X can assume that Y understands typical programming language control blocks: for-loops, if-then-else blocks etc.

X can assume that Y understands English.

X can assume that Y understands what a variable is and how a variable is used when writing code.

X can assume that Y knows how to write code, such as C++ or Python, from the pseudocode.

Question 2

Suppose person X has invented a new algorithm for solving some particular problem. X writes pseudocode for the new algorithm. Which of the following best describes what X’s main goal should be in presenting the new algorithm as pseudocode?

to allow any reader to produce as quickly and easily as possible working C++ code for the algorithm

to ensure that the reader knows what is the best hardware to use for executing the new algorithm

to communicate to each reader the computational steps and the essential variables and parameters of the algorithm

to indicate to each reader that X’s new algorithm is the best algorithm for solving the particular problem

Question 1

Typically pseudocode for an algorithm does not include testing for errors or testing the validity of the input data, whereas code for real-life applications should include such testing. Of the following, which is the best explanation for this lack of testing in pseudocode?

Since pseudocode cannot be compiled and run in a computer, it is impossible to include any testing in pseudocode.

The writers of pseudocode have no idea of what sort of testing would be needed.

Since no programmer ever writes code for real-life applications based on pseudocode, including such testing in the pseudocode is pointless.

Including testing in the pseudocode would lengthen it and make it less readable. This in turn would make it harder for a reader to understand how the algorithm works.

Question 2

Suppose we are given pseudocode for some algorithm. When implementing the algorithm in some programming language like C++, which of the following should we take into account? (There may be more than one correct choice.)

We should copy any comments in the pseudocode directly to the C++ code.

We should make sure that the number of lines of C++ code is exactly the same as the number of lines of pseudocode.

We should make sure that the syntax requirements of C++ are met.

We should consider what features of C++ we can use to make the algorithm run faster.

Question 1

Which of the following best describes the decrease-and-conquer strategy?

The original problem is divided into smaller subproblems, that are all solved together.

Only a small part is taken from the original problem and this small part is solved. This is repeated, until the original problem is solved.

We conquer the problem by assuming we need to solve the problem in some particular cases. The other cases we can ignore completely.

A special piece of software called an oracle is used to find the single part of the problem from which the solution can be found.

Question 2

Insertion sort works by

finding the correct place for each element in turn by moving already sorted elements

comparing random elements and swapping them if needed

comparing each adjacent element and swapping them if needed

Question 3

When the size of data input to insertion sort increases, the amount of computations insertion sort must do

stays the same

increases

decreases

might either increase or decrease

Question 4

Which of the following indicates that insertion sort uses the decrease and conquer strategy?

The counter used to indicate which element is to be handled next is decremented in each iteration.

In the final sorted array the elements are sorted from largest to smallest.

At each iteration the number of elements that are still to be sorted decreases.

The size of the array being sorted never increases.

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

pseudocode

divide and conquer

insertion sort

from pseudocode to implementation

Question 3

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

Extra links on the topics:

Wikipedia has examples of different styles of pseudocode

Submit weekly exercises¶

Nothing to submit yet! (Weekly exercises start on lecture week 3).

Course topic 2¶

Self-study (in English)¶

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?

Submit weekly exercises¶

Questions to be submitted this week