Course week 1

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.

Course week 1¶

Weekly exercises sessions¶

Self-study (videos and slides in English)¶

Algorithms and Pseudocode¶

Decrease-and-conquer¶

Insertion sort¶

Lecture-questions¶

Submit weekly exercises¶