Warm up Project: Path Finder (DUE February 5)
In this project you have to determine whether a path exist between a secured
data point and an unsecured port in a circuit. In this project, you are
asked to do the following:
- Read in the circuit (done for you already)
- Build basic data structure for the circuit (done for you already)
- Determine whether a path exist or not between the source and destination ports
Consider the circuit c17 below:
For the c17 circuit, the program takes c17 file as input circuit file and
then the user enters the source and destination ports. Suppose our source
port is 1 and destination port is 8, then the output of program should be 'no',
that there does not exists a path from gate 1 to gate 8.
Hint: You have to perform a depth-first search from the source to the destination.
Sample files:
- The description of the circuit file c17 can be found here
- A sample cpp file that reads in the circuit: circuit.cpp
Grading: Grading of this exercise will be based on the following:
- Correctness: 80%
- Program Legibility: 10%
- Execution Speed: 10%
- If your program does not compile (i.e., has syntax errors) - the grade
will be 0.
- If your program runs but the outputs are incorrect for more than 80%
of the cases, the maximum grade is 50 out of 100.
- Please email your program to mhsiao at vt dot edu on/before the
day it is due. For each day delayed, 10% is deducted from this project grade.
To measure how much time your program takes, add "time" before your command
at the unix/linux prompt to capture user and system time. For example, for
my_prog, type "time my_prog ckt" and the time taken to run
my_prog will be reported at the end of the execution.
You are encouraged to discuss among yourselves for this exercise. However,
everyone must write his/her own program. You are allowed to exchange
ideas, algorithms, etc., but NO PROGRAM SEGMENTS, PROCEDURES, FUNCTIONS,
MAY BE EXCHANGED.