Datastructures and algorithms VT26

Hi!

For this problem, you should not think of your pseudocode as something that resembles actual python code, but maybe closer to a very low-level programming language. Instead, the only allowed instructions are those that are stated in the problem description.

 

To not discuss the given problem we could take something even simpler: suppose we want a function that returns the value x + 2 for any input integer x. It would be ok to solve this by

 

add_two(x):
res <- 0 # assign value 0 to a new variable is OK 

inc(res)

inc(res)

return res

 

but the "python version" 

 

def add_two(x):

    return x + 2

 

is not what we are looking for in this problem. Is that making it clearer?
Kindly,
Anna

ps. Later in the course, you can of course basic arithmetic operations like multiplication in your pseudocode, just not in this problem.

Hi!

Anna explained already very good what is expected and how it works. Here are some additional information w.r.t. your questions:

Please "try to forget" any language specific knowledge you may have. The definition of algorithm is not based on any specific language like python, C++, Java etc. The definition of an algorithm goes back to Turing Machines. The key point is that the exercise is not asking for normal Python multiplication like return a*b. It is asking you to design multiplication from very primitive steps, almost like you are programming a very simple machine.

What does arbitrary positive integers mean?
A: Any positive whole numbers you choose — without restriction.

inc seems to mean integer+1
A: inc(variable) replaces the value of variable by the value variable + 1.

It says we should assign with 0 and then return the value.
A: No it says, you can assign to a variable 0 and do something and then may return some value.

while-loops are common in python, are DO-functions just common in C++?
A: DO is just pseudocode language, not a special Python or C++ feature. In ordinary pseudocode,
"WHILE condition DO instruction" just means: “while the condition is true, perform the instruction(s).”

i:=m and i:=j seems forbidden.
A: right. Moreover, not allowed is e.g.: direct arithmetic like a*b, a+n, a-1; copying values with j := k; assigning any nonzero value directly, like i := 5

What exactly are the instructions for this problem?
A: In essence, the exercise is saying: Build multiplication using only repeated incrementing, zero-initialization, comparisons, and while-loops.

I have a hard time getting the idea behind it to figure out how to start.
A: This exercise is very close to machine language / assembly thinking, but simplified. In high-level languages like Python, you write: "return a * b". But under the hood, the computer does not “magically” know multiplication. It eventually breaks everything down into very simple operations, like: incrementing values, comparing values, looping / jumping. This exercise is forcing you to think at that low level. In essence, this mimics a simplified model of how computers actually work at a low level (like assembly or even theoretical machines).