Summer 2003 Exam Solutions CS1003 Whalen 1) a) Just follow the algorithm. draw an arrow in the box pointing up, turning right and then going around the preimeter of the box (the thick line is the "wall"). b) No. Consider what would happen if the robot landed in a corner. Suppose the northwest corner facing west. The robot would detect barrier and then rotate one quarter turn to the right. IT would then attempt to proceed forward regardless, which might cause a collision with the north wall. c) The problem is that process_sensor doesn't return any data and that wall_ahead does not get modified in the scope of main. wall_ahead is altered inside process_sensor correctly, but that value never gets back to main so that the rotate_right() call can be made properly. d) If you just use and int * instead of an int as input to process_sensor, you will get correct results. So: #include #include void process_sensor(int wall_ahead); int main(void) { int wall_ahead = 0; while (1) { process_sensor(&wall_ahead); if (wall_ahead) { rotate_right(); } move_forward(); return 0; } void process_sensor(int *wall_ahead) { char *input_from_sensor; input_from_sensor = look_ahead(); /* if the value read from look_ahead() is equal to */ if (strcmp(input_from_sensor ,) == 0) *wall_ahead = 1; else *wall_ahead = 0; } 2) a) This is just a program trace. It prints out: 6 b) The problem is that we create (define) result on the stack inside input_plus_one. We then return A POUNTER to result back to main. So main is left with x as a pointer to an integer. The problem is that by the time main gets to printf, it tries to look at the memory location pointed to at x. But since that memory was allocated on input_plus_one's runtime stack, it is no longer valid. All the other stuff with foo is there to show that the results are indeed different if you tried to run this on CUNIX. (foo overwrites the stack space used previously by input_plus_one) c) Imagine a stack of memory -- a new block is put on the top when input_plus_one is called. It is then discared when return is issued. Malloc would allocate memory on the heap... entirely separate from the stack so yes, it would help. d) This is a proper swap using pointers outputs 2, 1 (see swap.c in lecture) 3) Just write a struct thinking about the problem. For example: typedef struct { char *root; char **suffixes; char **prefixes; DICTENTRY **related; char *definition; } DICTENTRY; This is a bit much... just thinking about storing the word, definition, and relations to other definitions would have been enough. b) You do not have to change LIST typedef struct { int data; LISTNODE *next; LISTNODE *prev; } LISTNODE; c) I'll keep this simple -- add_node would have to now set the prev link as well as the next link. This isn't hard -- it's an extra assignment statement. cur_node->next = new_node; new_node->prev = cur_noce; Really the only change is the second line above... d) No. You need to have a sorted list. doubly linked lists are not necessarily sorted You need to easily go to the middle of the list. You can't do that here. You'd have find the middle every time around -- very inefficient. 3) Either way, you go up n-1 and over m-1. So m-1+n-1 b) This is purly a permutations problem. The one vs two is irrelevant. In the general case with n spots, you can choose from n vehicles then n-1, then n-2 and so on... so you get something on the order of n!. If you answered this thinking that cars/limos were not unique, then you had two choices at every block. So if you had n squares, you make roughly 2^n choices (true, you actually make less, but even if you only had to make n/2 choices (accounting for big cars), you'd still make n^(n/2) choices, which we consider as the same order of magnitude. For a block of 4 car lengths, you can have: Car Car Car Car Car Car Limo Car Limo Car Limo Car Car Limo Limo For c) and d) see the explanation above... you can sort of see an algorithm in the 4 example above. In short, you go through every possible permutation. 5) a) int fact(int n) { if (n == 0) return 1; else return n * fact(n-1); } b) The fact function only iterates n times. So it takes linear time to *compute* the factorial of n. Note the difference between this and a problem taking n! *steps* to compute.