cps721: questions about the 3rd assignment.  

Questions related to the 3rd assignment

This page contains questions from students and my answers to them. If a question is asked that has already been answered, then I will not post another answer. So if your questions seems to go unanswered, you should check over previous questions.

Q1
A question about Part 1: should we follow exactly the dependency graph for this cryptarithmetic problem?
A1
Use your dependency graph as a guidance when you decide how to reorder your constraints. It is up to you how closely you follow your dependency graph. Remember to provide your explanations (as comments in the file).

Q2
I was wondering do we need to print one unique list? Suppose there is only one answer, but because of the way queries are structured I can get permutations in any order of those courses, all correct, just in a different order. I was trying to keep my prolog code as general as possible for the courses, and hardcode as little as possible.
A2
You are right that this CSP problem has the unique solution and it is sufficient for your program to find only one solution. Make sure that your printed solution is well formated and readable, i.e., the TA can quickly (1) run your program to see if it works, and (2) read the timetable that your program computes and (3) check that it is correct. There is no need to print a fancy table, any clearly readable table will be OK. Make sure it is your program that finds the solution, not you. You lose marks for encoding a part of the solution in the program. In this assignment, you have to demonstrate you learned 2 techniques for solving CSPs.

Q3
I just have a general question regarding Part 2 of assignment 3. I am just wondering if I am allowed to split a constraint into smaller constraints and implement them at different stage of the program? Right now, I define each constraint in a block of code, but the program is pretty slow.
A3
Any program correctly implementing the interleaving of generate and test technique discussed in class should be fine. In general, moving constraints around is allowed, as long as you do not forget to include them all, eventually. From examples in class, we know that rearranging the order of constraints can significantly speed-up the program. In my solution, I implement constraints not in the order they are listed in the assignment. My program takes less than 1 second to find a solution.

Q4
In Part 2 of the 3rd assignment, some of the constraints say "and possibly other systems as well" when sending an email between two networks, some however such as constraint 5, and 7 don't include that can we assume that they could also pass through other systems unless it says they exchange files directly?
A4
Read carefully the assignment. It is clearly stated under the last item 8 that: Assume that in the constraints (1), (3), (5), (7) the packages can possibly pass through more than one system (not only one computer system that is mentioned explicitly).

Q5
This is question regarding Part 2 of the 3rd assignment. Is it acceptable to have a hard coded constraint stating that system 3 cannot be Zickerman (since 3 is the only system with more than two connections)? Or should that thinking be done by the program?
A5
Read the preambule of the 3rd assignment. It is explained there that all thinking should be done by the program. In particular, your program should not be using any of the numbers shown on the diagram in the assignment. The purpose of this assignment is learning a technique of writing the programs that solve the puzzles. Any hard coding is against the spirit of this technique (and it will be penalized by the TA who will be marking this assignment).
If you read the hint carefully, you notice that the last argument of the predicate trip is the list of vertices. Since it is the list, you can use the helping predicates like "member" to check complex constraints.

Q6
Is it fair to assume that if an email is being passed through a system, it could be the system of one of the people who are sending the emails ? Example is Item1: "The email between Lizzie and Osborne is being passed through pricenet". Does this mean that Lizzie or Osborne could have pricenet as a system address?
A6
No, assume the opposite, i.e., if email from A to B passes through the system X, then X is different both from A and from B. Moreover, you can assume that A is different from B, since they send email to each other. For example, from Item 1, we know that Lizzie is different from Osborne, and in addition that neither Lizzie, nor Osborne can be administrators of pricenet.

Q7

In the 2nd Part of the assignment, I'm not quite sure if we're expected to match each system number on the map with the full name of the sys. admin and the address? So, for instance: System 6(from the map): Admin - Daniel Kim, Address - 'netvue.com'
A7
The numbers on the map can be used in the atomic statements specifying the topology of the given network graph. As stated in the assignment: "Your Prolog program must match each computer system on the map with its Internet address and with the full name of its system administrator". So, these numbers on the map are closely related to the problem that your program has to solve. Therefore, your program is expected to match each admin (the first and last name) with the system's internet address, and with the number on the map. When your program prints a solution, make sure it is clear how the admin's names, the system's address, and the number on the map are related to each other.

Q8
Do we have to do a dependency graph and get the fastest solution possible with each question in assignment 3?
A8
It is up to you if you would like to use a dependency graph in Part 2, but it can be useful in Part 1. You are not asked to write the most efficient programs, but programs that are designed following a specified technique and that are reasonably fast, i.e., take at most a few seconds or less. If your program takes about a minute or longer before it computes a solution, then you must rewrite it to make it much faster. For your information, my program for Part 2 takes less than 1sec to compute a correct solution.

Q9
Can we use the predicates var(X) and atom(X) from the standard library anywhere in the Part 3 of the 2nd assignment?
A9
Yes, this is the only case when you can use the library predicates not discussed in class.

Q10
In the assignment 3 it is stated that atom([nil]) is true, but it is actually false. Is it a typo ?
A10
Yes, this is a typo.

Q11
What is expected as input to predicate flat(InputTerm,OutputTerm) ?
A11
You can assume that InputTerm to flat() is produced by list2term() predicate. There is no need for your program to handle arbitrary input terms, only the terms produced by list2term() predicate.

Q12
In Part3 (a), we developed a pogram for appendT predicate. Can we use this program in sub-questions (b) and (c)?
A12

Technically speaking, you can. But before you use appendT() in (b) and (c), try to write first a recursive program directly, without using anything like appendT(). Recall you have to do a complete case analysis to write a recursive program. Make sure your rules apply to mutually exclusive cases. There are direct recursive programs for (b) and (c) then do not use appendT() at all.

Q13

A13

Q14

A14

Q15

A15

Q16

A16

Q17

A17

Q18

A18

Q19

A19

Q20

A20

Q21

A21

 

 


CPS721