# Assignment 4 - Prolog?

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Assignment 4 - Prolog?
Hi all,

are we supposed to write a Prolog file in assignment 4 to prove that the functions find the solutions with most Cherries first?

No, you should not write a Prolog program for that.

Please use mathematical reasoning in order to show that! ( meaning that you should write some sentences in English/German)

You may use all Theorems / Definitions we introduced in the lecture to show that.

1 Like

One more question to Assignment 4:

Is it one cherry per node or may there be as many cherries as possible (range 0-15) in one node? Of course considering the random distribution, so 15 in one node is not helpful.

Thank you,
Matthias

Nodes are binary: Cherry or Nothing.

If you have some experience with LaTeX, I suggest to have a look at my template Marius/uebung04/template.tex · master · teaching / AI · GitLab .

I have thought in the meantime about it and I actually came to the conclusion that our A* search task makes only sense when there may be more than 1 cherry at one node, so your answer surprised me a bit

So, if I understand you correctly, there are multiple equivalent solutions for the search problem, for example two paths which have a cherry in each consecutive node. Also this would imply that the maximum number of cherries that are collectable is 4, right?

I am already using your template by the way. It is super helpful, so thanks a lot!

Yes, that’s correct! (or more precisely: if the root is a Cherry, 5 is also possible!)

In general, the tasks are more meant to be rather „educative“ than „senseful“.

If you interpret a task differently, then simply write some arguments/justifications about that and we will try to understand your solution.
If your own solution is inherently correct and uses the tools you were supposed to use (here: A*) [and it is not trivial], I can promise that you will get a fair amount of points.

Now here I’m a little bit stunned. Mainly because I thought that there cannot be a cherry on the root (Pac-Man is already there) and secondly because I thought that a tree of level height 5 means a total of 6 levels (so that you’d have 2^(5) nodes overall), another tutor confirmed me in that thought. Which of these tree definitions is now correct?

Wouldn’t a tree with 6 levels mean that you have 2^6 -1 nodes? I’m pretty sure it’s a total of 2^5 -1 nodes, meaning 2^4 leaves (if I remember correctly that’s the way tyr’s template looked like)

Yup, sorry I meant you would need 63 nodes and not 31 nodes as it is in the template. My tutor told me that we would need 63 nodes and not the variant presented here, that’s why I asked in the first place.

Yeah, that sounds sensible. Sorry about that, but in theory you could argue that it is still possible to have a Cherry at the root. Obviously A* still works then and the students tend to overthink some parts of the tasks, I just wanted to say: „5 is also possible if you use the right arguments“.

Firstly: which tutor? I think we are all okay with talking about us in person and that would make it easier to find such misunderstandings.

Secondly: What is the definition of level you are using? From Google I only get something like „level means 1+ the number of edges from the root to the node“ => a tree with 5 levels can be sliced horizontally into exactly 5 slices.
It is important to notice that [m]height != level[/m].