|
[ This content is protected and may not be shared, uploaded, or distributed. ]
(Please also check out PA1 FAQ.) Lab 2 has three parts: I was told by CS 170 instructor that you should all be experts in the BFS and Dijkstra's algorithms. If you have forgotten about these algorithms, we will review them briefly (please see PA1 lecture slides) during the first two weeks of the semester. Please also checkout the pseudo-code below.It would be to your advantage if you can write your code for this lab in a general enough way so that it can be easily extended so that it can be used in PA1. It's probably a good idea to be familiar with the PA1 spec before you start to design your code for this lab. Part A (lab2a) - graph and adjacency list:Create an empty directory (call it "lab2") and change directory into it. Part B (lab2b) - breadth first search (BFS):Write a program in "lab2b.cpp" (in C++) and add a section to the above "Makefile" so that when you type "make lab2b", an executable called lab2b will get created, when you type "make clean", all ".o" files and lab2b will be deleted, and when you type "lab2b number filename", it will treat filename as a file that represents a graph, create an adjacency list data structure (as in Part A of this lab), run the BFS (Breadth-First-Search) algorithm starting at node number (zero-based index), and print the BFS result. We will refer to this node as the "start node". (If you are not familiar with the BFS algorithm, we will review it during the first week of lectures.) A graph file has the same format as in Part A of this lab. For a graph that looks like the graph above, if number is 0, the start node would be node 0 and it must be assigned a level of 0, and your printout may look like (you can break ties any way you want): Part C (lab2c) - Dijkstra's algorithm:Write a program in "lab2c.cpp" (in C++) and add a section to the above "Makefile" so that when you type "make lab2c", an executable called lab2c will get created, when you type "make clean", all ".o" files and lab2c will be deleted, and when you type "lab2c number filename", it will treat filename as a file that represents a graph, create an adjacency list data structure (as in Part A of this lab), run Dijkstra's algorithm starting at node number (zero-based index), and print the result of running Dijkstra's algorithm. We will refer to this node as the "start node". (If you are not familiar with the Dijkstra's algorithm, we will review it during the first week of lectures.)
All pseudo-code is incomplete and error checking is often left out in pseudo-code.
Feel free to send your questions (and not your code) to the instructor.
Please note that the read_a_line(fd) pseudo-code below is basically the same read_a_line() function in "my_readwrite.cpp" with a slightly different notation. Pseudo-code for lab2a:
/* read N and E */
fd = open(argv[1], read-only)
line = read_a_line(fd)
N = get-int(line)
line = read_a_line(fd)
E = get-int(line)
/* create empty adjacency list */
nodes = new Node[N]
for (i=0; i < N; i++) do:
nodes[i].list = empty-list
end-for
/* read E edges, update adjacency list */
for (i=0; i < E; i++) do:
line = read_a_line(fd)
(n1,n2) = get-two-ints(line)
nodes[n1].list.append(n2);
nodes[n2].list.append(n1);
end-for
close(fd);
/* print out the adjacency list */
for (i=0; i < N; i++) do:
print "neighbors of node " + i + ": "
if (nodes[i].list is not empty) then:
print-list(nodes[i].list)
end-if
print "\n"
end-for
Pseudo-code for lab2b:
/* read graph */
fd = open(argv[1], read-only)
line = read_a_line(fd)
N = get-int(line)
line = read_a_line(fd)
E = get-int(line)
nodes = new Node[N]
for (i=0; i < N; i++) do:
nodes[i].list = empty-list
nodes[i].level = (-1)
nodes[i].pred = null;
end-for
for (i=0; i < E; i++) do:
line = read_a_line(fd)
(n1,n2) = get-two-ints(line)
nodes[n1].list.append(n2);
nodes[n2].list.append(n1);
end-for
close(fd);
/* BFS */
queue = new Queue of integers
nodes[start_node].level = 0
queue.append(start_node)
while (!queue.empty) do:
v = queue.delete_head()
print "level " + nodes[v].level + ": " + v
for each of nodes[v]'s neighbors u do:
if (nodes[u].level == (-1)) then
nodes[u].level = nodes[v].level+1
nodes[u].pred = v
queue.append(u)
end-if
end-for
end-while
Pseudo-code for lab2c:
/* read graph */
fd = open(argv[1], read-only)
line = read_a_line(fd)
N = get-int(line)
line = read_a_line(fd)
E = get-int(line)
nodes = new Node[N]
for (i=0; i < N; i++) do:
nodes[i].list = empty-list
nodes[i].distance = 999999999
nodes[i].in_solution = false
nodes[i].pred = (-1)
end-for
for (i=0; i < E; i++) do:
line = read_a_line(fd)
(n1,n2,c) = get-three-ints(line)
nodes[n1].list.append((n2,c));
nodes[n2].list.append((n1,c));
end-for
close(fd);
/* Dijkstra initialization */
nodes[start_node].distance = 0
nodes[start_node].in_solution = true
nodes[start_node].pred = start_node
for each of start_node's neighbors u do:
nodes[u].distance = edge_cost(start_node,u)
nodes[u].pred = start_node
end-for
list = new List of node indices
for all node u do:
list.add_sorted(u)
end-for
/* Dijkstra */
itr = 0
while (!list.empty) do:
w = list.delete_min() /* find and delete and return the node with smallest "distance" value */
if (w == null || nodes[w].distance == 999999999) then
break;
end-if
nodes[w].in_solution = true
print "itr " + itr + ": add node " + w + ", distance " + nodes[w].distance + ", predecessor " + nodes[w].pred
for each of w's neighbors v with c=cost(w,v) do:
if (!nodes[v].in_solution) then
if (nodes[w].distance + c < nodes[v].distance) then
nodes[v].distance = nodes[w].distance + c
nodes[v].pred = w
end-if
end-if
end-for
itr++
end-while
Below is the grading breakdown:
Please keep in mind that even though lab grading is "light", it doesn't mean that you can just put anything into your submission! It's still your responsibility to make sure that the files in your submission contains information that's relevant to the tests you were supposed to run. Use the "more" command to view your script/log files to make sure that they contain the right information. If a file has the wrong stuff in it, you should delete it and create the file again and verify. If most of the stuff in your script/log files are wrong and you did not notice it, we will most likely have to take points off.
To submit your work, you must first tar all the files you want to submit into a tarball and
gzip it to create a gzipped tarfile named "lab2.tar.gz".
Then you upload "lab2.tar.gz" to our Bistro submission server.
Change into the "lab2" directory you have created above and enter the following command to create your submission file "lab2.tar.gz" (if you don't have any ".h" files, don't include "*.h*" at the end):
tar cvzf lab2.tar.gz lab2*.script Makefile *.c* *.h*
ls -l lab2.tar.gz
The last command shows you how big the created "lab2.tar.gz" file is.
If "lab2.tar.gz" is larger than 1MB in size, the submission server will not accept it.
If you use an IDE, the IDE may put your source code in subdirectories. In that case, you need to modify the commands above so that you include ALL the necessary source files and subdirectories (and don't include any binary files) ane make sure that your code can be compiled without the IDE since the grader is not allowed to use an IDE to compile your code. You should read the output of the above commands carefully to make sure that "lab2.tar.gz" is created properly. If you don't understand the output of the above commands, you need to learn how to read it! It's your responsibility to ensure that "lab2.tar.gz" is created properly. To check the content of "lab2.tar.gz", you can use the following command:
tar tvf lab2.tar.gz
Please read the output of the above command carefully to see what files were included in "lab2.tar.gz"
and what are their file sizes and make sure that they make sense.
Please enter your USC e-mail address and your submission PIN below. Then click on the Browse button and locate and select your submission file (i.e., "lab2.tar.gz"). Then click on the Upload button to submit your "lab2.tar.gz". (Be careful what you click! Do NOT submit the wrong file!) If you see an error message, please read the dialogbox carefully and fix what needs to be fixed and repeat the procedure. If you don't know your submission PIN, please visit this web site to have your PIN e-mailed to your USC e-mail address. When this web page was last loaded, the time at the submission server at merlot.usc.edu was 27Nov2025-18:59:53. Reload this web page to see the current time on merlot.usc.edu. If the command is executed successfully and if everything checks out, a ticket will be issued to you to let you know "what" and "when" your submission made it to the Bistro server. The next web page you see would display such a ticket and the ticket should look like the sample shown in the submission web page (of course, the actual text would be different, but the format should be similar). Make sure you follow the Verify Your Ticket instructions to verify the SHA1 hash of your submission to make sure what you did not accidentally submit the wrong file. Also, an e-mail (showing the ticket) will be sent to your USC e-mail address. Please read the ticket carefully to know exactly "what" and "when" your submission made it to the Bistro server. If there are problems, please contact the instructor. It is extreme important that you also verify your submission after you have submitted "lab2.tar.gz" electronically to make sure that every you have submitted is everything you wanted us to grade. If you don't verify your submission and you ended up submit the wrong files, please understand that due to our fairness policy, there's absolutely nothing we can do.
Finally, please be familiar with the Electronic Submission Guidelines
and information on the bsubmit web page.
|
||
