| Date | Questions | Answers | ||||||||
| 12.3 | Assignment #4 solution. |
here
Part II (P6 and P7) marking guide and test cases can be found at http://www.cs.ualberta.ca/~yaling/c366/as4marking.html |
||||||||
| 12.3 | Assignment #3 solution. |
The answers to problems 1 to 4 are at http://www.cs.ualberta.ca/~wgang/sol_assn3.htm The answers to problem 5 and 6 are at http://www.cs.ualberta.ca/~yaling/c366/as3soln.html |
||||||||
| 12.2 | Where there be labs December 3? | Yes, there will be a TA in the lab in the morning from 8-11am to answer questions on assignment 4. | ||||||||
| 12.1 | Announcement | You can check your used late days at http://www.cs.ualberta.ca/~wgang/latedays.htm | ||||||||
| 11.25 | Announcement |
Here are the final exam papers in the previous three years.
| ||||||||
| 11.24 | Announcement | This year's final exam will be closed-book. You are allowed to bring one "cheat sheet" (up to 8.5"x11", possibly double-sided). | ||||||||
| 11.25 | Announcement | The final exam for this course has been scheduled at 2-5pm on Monday Dec. 15th, 2003. It will be in our usual classroom (CSC B10). | ||||||||
| 11.21 | Announcement | A page has been set up here for the Soccer Tournament, which you can use to enter the name of your team and look up the results. | ||||||||
| 11.18 | Announcement | The sample bags of words in Problem 7 has been changed. They are now shorter than before. | ||||||||
| 11.18 | Announcement |
The grammar rules for 'that', 'cat' and 'with' has been added to the grammar in Problem 6 (thanks to Mark Lee for point this out). Problem 6b would have involved 123 arcs, which are a bit too many. So we have changed it to a shorter sentence. Please see the updated assignment spec. |
||||||||
| 11.17 | Announcement | There has been a bug fix in the Viterbi function in hmm.cpp. Please download as4.tgz again. | ||||||||
| 11.17 | Assignment #2 solution. |
The answers to questions in problem 1,2,5 are at http://www.cs.ualberta.ca/~wgang/sol_assn2.htm The answers to problem 3 and 6 are at http://www.cs.ualberta.ca/~yaling/c366/as2soln.html The answers to questions in problem 4,7,8 are at http://www.cs.ualberta.ca/~schmidt/c366ass2.html |
||||||||
| 11.14 | In as4, q4a, could you explain the format of lexicon.txt? | Each line in this file consists of two tokens. The second token is a word. The first token is a part of speech of the word. The meanings of the part of speech tokens are explained in here. | ||||||||
| 11.14 | Announcement | Problem 3.d in Assignment 4 has been rephrased. | ||||||||
| 11.11 | How do make one player the goalie? |
To create an goalie, you need to take the following steps:
1. Edit client.conf file in the player directory. Change the line 'goalie_number : 12' to 'goalie_number : 1' 2. Edit the start script in the player directory. change the following line from ./$programname -file client.conf -file ~/.rcssserver-server.conf -file ~/.rcssserver-player.conf -host $host -team_name $teamname & to ./$programname -file client.conf -file ~/.rcssserver-server.conf -file ~/.rcssserver-player.conf -host $host -team_name $teamname -goalie on & You first player should now be a goalie. |
||||||||
| 11.10 | The shortest path will tell me the which sequence of states have the highest probability. How can I compute the probability of the best sequence? |
The length of the path is the negative logarithm of P(x1:t, e1:t). To compute P(x1:t | e1:t), we need to know P(e1:t).
The lecture notes contains formulas for computing P(Xt=s, e1:t). P(e1:t) can be obtained by summing up for all possible state values at time t: P(e1:t)=SUMs P(Xt=s, e1:t). Since the lectures have been slower than planned, we will treat this part of Problem 5 as a bonus question. |
||||||||
| 11.10 | Can you point me in the right direction for how to access information like what objects a player sees? | Looking at Test.C in the united/player direction should get you going in the right direction. Here is an image of the different static field markers (the names are slightly different in the CMU implementation): Field Markers | ||||||||
| 11.10 | I'm having some trouble getting started on Problem 5(15.12)... | Please take a look at the HMM slides about Viterbi algorithm. You can essentially transform this problem to a shortest path problem. | ||||||||
| 11.10 | For Ass 3 question 6, I am trying to prove P( +x | +z ) >= P( +x | +y, +z ) using P( +z | -x, -y) = 0 but I'm not sure how. Is there any hints you can give me so I can get this proof started? | You probably want to express P(+z) in terms of the different values that x, y, and z could take. You should use the definition of conditional probability and P(A or B)=P(A)+P(B) if A and B are mutually exclusive. | ||||||||
| 11.10 | What is meant by 'independent value' for Ass. 3, Question 4, part c? | Here an "independent value" just means that it cannot be computed from other values. Suppose A and B are binary variables. P(A) has one independent value (since P(A=false) equals to 1-P(A=true)). P(A|B) has two independent values P(A=true|B=true) and P(A=true|B=false). | ||||||||
| 11.10 | How will we be graded for Assignment 3, Question 7? | The mark will be based on your description of the solution, its performance against the default team that come with the United-2000 code, and the performance in the tournament. | 11.10 | Announcement |
The top 5 performers for the BestSAT problem are
|
|||||
| 10.27 | Assignment #1 solution. |
The answers to questions in problem 1 are at http://www.cs.ualberta.ca/~wgang/sol_p1.htm Another solution to P1b
The answers to problem 2 and 4 are at
The answers to problem 3 and test data for problem 5 are at |
||||||||
| 10.21 | Do we need a seperate file for parts B and C of the soccer question? | No, one file that covers both behaviours is fine. | ||||||||
| 10.20 | Do you expect more beside what Part B (different position before kick off) and Part C (players don't flock towards the ball)? | No, but you'd better get familiar with the whole process of the program to prepare for the next assignment. | ||||||||
| 10.20 | For the RoboCup question in as2, we don't have to submit anything for Part A right? | Nothing needs to be submitted for Part A. | ||||||||
| 10.20 | In order to make our players not flock to the ball, can we simply force a few of them to not do anything unless they are given the ball? | You can do that for assignment 2. but you need cosider a better strategy for next assignment. | ||||||||
| 10.20 | Is there any other hints you can give for question 2? | Cosider a new variable Y, which is a tuple (y1,y2). What are the constraints between Y and the variables A, B, C needed | ||||||||
| 10.20 | I'm not sure wehere to start for question 3! | Please see Edge Labeling in slides "Constraint Satisfaction 1" and related pages in textbook. | ||||||||
| 10.20 | Can we check for duplicates in the queue before adding an arc (for AC-3)? | Yes | ||||||||
| 10.20 | Are we supposed to modify files other than behave.C/behave()? | You shouldn't need to modify other files. | ||||||||
| 10.15 | What is the submission procedure for assignment 2. Do we hand in a tar file and if so do we tar our whole player directory or just the files we have modified? | You should include the executable and the source files that you have modified. | ||||||||
| 10.14 | In AS2, Problem 7, is the mouse making the first move or the cat? Do we need to show the final alpha-beta tree only? or step by step? | Just the final tree will be OK. | ||||||||
| 10.14 | Problem 5, Logic Reasoning, when you ask us to use the resolution refutation algorithm, again (refer to question 1), do we have to show intermediate result, because we have to resolve EACH combination of clauses according to the algorithm. | You need only to show the steps that leads to a contradiction. In cases where the conclusion does not follow, you need to show that you have derived all the clauses that can be derived. | ||||||||
| 10.14 |
Minimax, when you ask us to draw a game tree in which MAX
can do better using a suboptimal strategy against a suboptimal MIN.
Is "the better" comparing to when:
- MAX and MIN both play optimal strategy, - or MAX play optimal and MIN play suboptimal? |
The second one. | ||||||||
| 10.14 | AS2, Problem 1, I traced through each single step, and show the queue of arcs, domains of each node for each single step and my answer is like several page long. Can I not show step that did not change anything? | You can take each call to remove-arc-inconsistancy that results in a reduction of a variable's domain as a single step. | ||||||||
| 10.14 | This is a general question, in the assignment, we have to apply some algorithms to get answers, do we have to show each single step in the algorithm? | If the steps would be too long, you can skip steps that leads no where or doesn't change anything. As long as your steps clearly shows that you understand the algorithm, it would be ok. | ||||||||
| 10.11 | For question 2, what does it mean by "a new variable that takes on values which are pairs of other values"? Could you give an example of what this would be and how it would used? | Suppose variable x has the domain {1, 2, 3}, and variable y as the domain {a, b}. The variable z takes on values which are pairs of values of x and y if z's domain is {(1,a), (2,a), (3,a), (1,b), (2,b), (3,b)}. | ||||||||
| 10.11 | I was looking into downloading the simulator for this assignment so that I could work on my own machine rather than SSH-ing in to the lab machines. I was wondering which version you are using (for testing purposes) and whether you know of any significant differences between that and other releases (Of course, I realize that my code must work on the lab machines, but it would be nice to know which release is closest to the testing ones.) | The soccor simulator we are using is rcsoccersim-8.05.10. Some of the later versions of the simulator server have compatibility issues with the United-2002 software. If you want to run it on your own machine, you should copy the source code from ~lindek/366/rcsoccersim-8.05.10. | ||||||||
| 10.1 | Will we lose marks if our program does not terminate after 1 minute | We are going to test the programs with problems that can be solve by a reasonablly efficient program. If the program cannot solve them in a minute, then marks will be deducted. | ||||||||
| 10.1 | For questions 1.c) and 1.d), will there be test cases where there is no path to the food | No, there will be at least one path to the food. | ||||||||
| 10.1 | When and where is the written portion of the assignment due if it is handed in late? | If is handed in late, the written portion is due in Dr. Lin's office (Ath 3-57) before the doors of Athabasca hall are locked (10pm on weekdays) on the day that it is being handed in. | ||||||||
| 10.1 | The example problem given for question 5 is very trivial and several of the ones on the website are very challenging or unsatisfiable, can you provide some sample problems that are in between these two cases. | The following problems represent cases that are not trivial but your algorithms should still be able to solve within one minute (preferably much less): aim.cnf, aim2.cnf. | ||||||||
| 10.1 | hi, for question #1, does our agent have to account for fast server settings? ex) if the server speed is set to < 250ms, and the agent sends a 'see' command, the next tick will execute before the 'see' resutls are recieved. This causes problems for my agent. |
The amount of computation needed by the server to respond to a LOOK (or other) command is quite small. It will not take anywhere close to 250ms. However, if your program spend (say) 240ms after a tick to decide what to do and then issue a LOOK command, the next tick will probably come before the SEE message. So you have to make sure your program runs fast enough (welcome to real time programming!). We'll use 500ms to test your assignments. |
||||||||
| 9.30 | Do we have to be able to solve all of the challenge problems (at ftp://dimacs.rutgers.edu/pub/challenge/satisfiability/benchmarks/cnf/) within one minute? | No, you only need to use 1 minute efficiently for each algorithm. | ||||||||
| 9.30 | Is the 11:59pm deadline for the code applied for the written portion | The written part is still due before class. | ||||||||
| 9.30 | What naming coventions do we use for coding solutions to problem 5? | Please use the same naming conventions as in question 1 (so gsat will be p5a, walksat will be p5b, and bestsat will be p5d) | ||||||||
| 9.30 | Which heuristic do we use for question 3.b) | Please use the same heurisitc as for question 3.c) | ||||||||
| 9.30 | I plan on using one of my late days for this assignment. When is the cutoff time before it becomes two late days? Also, where do I hand in my assignment if it is late? | For the code, the deadline is 11:59pm on Thursday. If you submit on Friday, it counts as one day late. If you submit on Saturday, Sunday and Monday, it counts as 2 days late. | ||||||||
| 9.30 | The guidelines ask that we submit "a high-level description of each of the coding question[s]" with our Part 1 hard copy. What exactly should this be? | You should describe so that a person who have taken this course will understand what you did. For example, you can say something like 'it uses A* search to find the shortest path to the goal. The heuristic distance is defined as ..." | ||||||||
| 9.29 | Announcement |
To submit assignment 1 with 'try', please do the following:
|
||||||||
| 9.26 | For problem 3, can we assume any simple pruning techniques like loop detection when we consider expanding nodes? | Yes, you can. | ||||||||
| 9.26 |
the algorithm on the lecture note stated:
2. .....(Note: Flip even if no improvement)...we have to implement that in
q5a too right? (Does our q5a program have to make sure any new initial random assignment is a different assignment from all the previous ones, if so, we have to allocate memory to store all the previous initial random assignemnts) |
Yes, you still need to flip even if there is no improvement (unless you
have found a satisfying assignment or have reached the maximum number of
flips per restart).
I do not think it is necessary to store previous random initial assignments for GSAT (there are an exponential number of them and the algorithm may take more time searching for new assignments than actually applying the heuristic for hard problems). |
||||||||
| 9.26 |
Regarding Question 5:
Should the program have a default value for the max # of flips and restart? can the user specify that in command line when running the program? Similar question for mixed-walk sat, should there a default value of probability p? can the user specify that as an argument to the program? |
Your programs should have the same input-output format as the gsat.c (or gsat.cpp) that was provided. There should be no extra command-line arguments.
You decide what is the max # of flips and restarts. You can experiment with different combinations. Let's say we'll let your program to have 1 minute CPU time on the lab machines (csu5XX). You can determine your max # based on that. You also set the probability p in WalkSAT yourself. |
||||||||
| 9.25 | With regard to assignment 1 q5. We are to extend the code provided which is in C. Yet we are told that our code is to be in C++ (guideline 4 bullet 3). One of these is going to have to go - which one is it? | Since C is a subset of C++, g++ compiler will also compile C files (in theory). In this case, one has to add a couple of include files since C++ is more strict in that department. You can download a modified version of the file (renamed gsat.cpp) as your starting point for Q5. | ||||||||
| 9.24 | Announcement |
Another fix for the SEE command (I forgot to multiply the direction vector). So it was giving the co-ordinates with wrong sign when looking north or west.
Please download as1.tgz again. Thanks to Shane Bergsma for pointing this out. My appologies.... Dekang |
||||||||
| 9.24 |
If so then I am curious as to whether of not a maximum map size can be
provided? I can obviously dynamically allocate and reallocate larger maps if
required - but that doesn't seem to be the point of this course.
If for instance you could guarantee that a map would be no larger than 100x100, then I would allocate a 200x200 map (since I cannot be sure of the starting position). |
Yes, you can maintain a map of the world. There won't be a predefined maximum size of the world. If you use one, you will risk losing a small percentage of the marks. Even though this is an AI course, I wouldn't like to see our graduates getting into the habit of using constant-sized arrays (they have been one of the biggest source of software failures/problems). |
||||||||
| 9.24 | In question 3a), what do you mean by "assuming nodes are considered in top-to-bottom" order? can you give an example? | in uniform-cost search, suppose current node A and B has the same cost and we need choose one to expand. then the next expanded node should be A as node A is on top of node B | ||||||||
| 9.23 | Announcement | The due date for Assignment One is postponed to Oct. 2nd. | ||||||||
| 9.23 | Announcement |
There has been a bug fix for the see command in as1/AgentWorld/AgentWorld.java.
Please download as1.tgz again.
In the buggy version, when the agent look east or west, the coordinates were in the wrong order. For example, when (look east) returns (see (barrier 1 1) (barrier 0 2) (pit -1 3))the correct results should be: (see (barrier 1 1) (barrier 2 0) (pit 3 -1))The coordinates of the objects in the world can be obtained by summing up the coordinates of the agent and the results of look. In the above example, suppose the agent is at (2 4) when it did (look east), the pit's coordinates are (5 3). Thank you, Dirk Henkemans, for pointing this out. |
||||||||
| 9.22 | In the description of Problem 1(c), it is specified that the server will provide, "the location of a bowl of dog food." Can we assume that all worlds our program will be tested on will only have a single bowl of food, or should we allocate for multiple bowls? What about for Problem 1(d)? | In both 1(c) and 1(d), you can assume that there is only one bowl of dog food. | ||||||||
| 9.21 | Should the initial position of worldB.txt be (1,1) instead of (2,5) or are we expected to handle worlds with initial positions other than (1,1) for this question? | You are right. the initial position in worldB should be (1,1) instead of (2,5) | ||||||||
| 9/18 |
if "list.print(cout)" outputs this:
(see (barrier 0 3) (barrier -1 3) (barrier 1 3))the code: RecursiveList* k = list.getSubList(0); will "k" now point to "(barrier 0 3)" ? and if so then how do i get the numbers 0 and 3 out? |
RecursiveList* k = list.getSubList(1);
^^^
points to (barrier 0 3). After that,
k->getAtom(1) returns "0"
k->getAtom(2) returns "3"
There was a bug in getSubList(int) function.
Please download as1.tgz again.
|
||||||||
| 9/17 | the specs says the coordinates of the top left cell are (0,0) but when it is actually (1,1) I put (1,1) in one of the worldX.txt for the initial position of the agent and the agent started off at the top left cell. Can you tell me which should we follow (0,0) or (1,1) as the top left cell? | The cell (0,0) is part of the border of the AgentWorld and is always occupied by a barrier (shown in black) as other border cells. So, the cell (0,0) exists, but you cannot put an agent in there. |
