 |
Skill Test 3 and Final |
| CSC 220 |
The instructor will draw a specific graph on the board. It will have from 5 to 10 vertices and about as many edges. It may be directed or undirected, but in either case it will be fully connected from the designated start node. You will create a C++ program from scratch that will first store this specific graph in memory using an appropriate data structure. You may use "brute force" memory storage that just initializes the proper variables or data structures with the appropriate constant values to represent this specific graph. You may store the graph in any data structure that is normally used to store graphs as long as you use the data structure appropriately. You do not have to create a new "Graph" abstract data type for this test. You may simply use arrays or the Standard Template Library directly.
After creating the graph in memory, then you must write either a breadth-first or a depth-first search algorithm on your graph in memory, starting at a designated node and printing the results to the screen. The instructor will specify whether to code the breadth-first or depth-first algorithm. Your code may be tailored for your specific representation of the graph in memory, but it must actually perform the search according to an accepted algorithm for searching a graph, and it must be easily adaptable to work with other graphs represented in memory with the same data structures. You cannot just print out the answer to the screen, without actually performing the search.
This is a closed book test. You may not use any text, notes, or programs on your computer, except Microsoft Visual C++'s help screens. You may receive help only from the instructor.
Skill Test 3 and Final will be worth the following 10 points toward the final course grade:
Note: You must take the final on the assigned date and time to get any credit. Nothing will be accepted or graded for this course after the final.
4 points: Your C++ program correctly stores the graph in an appropriate data structure in memory.
4 points: Your C++ program runs the specified breadth-first or depth-first algorithm on your graph in memory, and prints the correct answer to the screen.
2 points: Your C++ program is properly written according to standard C++ style, with full commenting.
Wednesday, December 12th at 7:30 PM (normal class time).
 |
Office: M233a | Phone: 353-2250 | sbadman@parkland.edu | |