From yuana@cs.toronto.edu Wed Aug 21 06:58:47 2002 Date: 1 Aug 2002 17:33:14 GMT From: Yuan An Newsgroups: ut.cdf.csc270h Subject: comments on A3 Comments for A3 ================ 1. Style: (1) Pay attention to efficiency when you implement graph data structure and graph related algorithms. In this assignment, the graph is not a simple graph, you don't know the number of edges in advance. Therefore, dynamic memory allocation is unavoidable. Linked List is the primary choice, but using array to implement Linked List is not efficient as well as using double dimensional array to represent the graph. (2) If you used algorithm other than the well-known search algorithms, like DFS, BFS and Fleury, please describe the algorithm in the function description parts or make a good comments. Again, brute-force approaches to check connectivity and find tour are unacceptable. (3) Don't forget check the return value of malloc() and don't forget release the dynamically allocated memory upon the termination of your program. (4) If your data structure and implementation for such assignment are needlessly overcomplicated, you will get penalized. (5) NO magic number. The number of districts and the length of the name of bridges should be macros. You got penalized if you did things like: fleury(district *d1, district *d2, district *d3, district *d4) 2. Correctness: (1) Make sure your program can be compiled. There are four testing cases to test the correctness of your program: TEST CASES ---------- The first test case is the Bridges of Koenigsberg from the assignment. It should return "No path found." The second test case is a simple loop: 1-----2 | a | |d b| | c | 4-----3 The third test case is the following: _______ / donkey\ / ____ | 2 | /cat \ | |/ \ / pig 1--------3---------4 \ dog / \ / \____/ \_____/ mouse cow The fourth test case is the following: 1 2 /\ /\ / \ / \ cat| |dog pig | |cow | | | | \ / \ / \ / \ / 3 4 Did your program handle all these cases ? (2) If you used the Theorem to check whether there is an Euler tour, make sure that it is only true for *CONNECTED* graph. For this assignment, your program should satisfy these two conditions: a. got back to starting district; b. crossed every edge exactly once. 3. Documentation: (1) Please submit all files needed to compile you program. Some students didn't submit the header files, this caused you lost marks. (2) Don't put each function in a separate file. How could you maintain your code spreading a number of small files ? Overall, you did a good job. Thanks. From niloofar@cs.toronto.edu Wed Aug 21 06:59:16 2002 Date: 2 Aug 2002 23:49:42 GMT From: Niloofar Arshadi Newsgroups: ut.cdf.csc270h Subject: Marking Scheme for A3 Documentation ============= No header -5 (includes your name, student ID, ..) No function description -5 (explaining paramters and its main functionality) Poor Comments -10 Poor Indentation -2 Print Error -5 (If the print is not complete and only the first 80 cols were printed) Correctness =========== No use of dynamic memory -10 No check the return value of malloc -5 Not deallocating the memory -5 No function protypes -5 Program does not compile -10 Program does not work for test cases -15 Incorrect value for the bridge length -1 Style ===== Poor or complicated data structure -5 Efficiency -5 Brute-force approach - in finding isthmus -5 - in finding Euler circuits -5 Bad function signature -10 Magic numbers -2 Poor Modularity -2 Bonus ===== check the degree of each vertex before +5 looking for Euler circuit