|
CSE 417, Wi '05: Assignment #6, Due: Thursday, March 10, 2005, 6:00 PM |
|
 CSE Home |
About Us |
Search |
Contact Info |
Given as input a graph G = (V,E), determine the number of k-cliques in G, and print the first such clique found, where k = floor((1/2)*log2n). (n = the number of vertices in V, and for any real x, floor(x) = the largest integer ≤ x, and log2n = log n/ log 2.) Search for cliques using the "pruning" version of backtrack search outlined on the slides labeled "Backtracking for k-Clique, II" (approximately slides 8 & 9 of the NP slide set).
Input format: Same as HW #5: To keep things simple, assume the input will consist of a positive integer "n" followed by some number of pairs of integers in the range 0 to n-1. "N" represents the number of vertices in the graph, and each pair u v represents an edge between vertices u and v. Although a good program really should check for the following malformed inputs, you may simply assume that you never get: negative numbers, numbers outside the range 0 to n-1, an even number of integers in total (i.e., the last pair is unfinished), or a pair u v where u=v, or where either (u,v) or (v,u) duplicates a previous pair in the list.
You may reuse code from last week for reading/storing the graph. (However, give some thought to whether an adjacency matrix might be more convenient than an edge list for this assignment.)
Output Format: Print out the number of nodes, number of edges, the value of k, the number of k-cliques found, the run time used for this search (excluding input/output; see below), and, if any k-cliques were found, list the vertices in the first such clique found during your search.
Testing: run it on this specific sample graph and turn in a printout of your result. (You should of course do more extensive testing as well, but you only need to turn in this one case.)
Timing: First, give a big-O analysis of the run time of your program. Then, run it on a variety of graphs of different sizes and different densities (average number of edges per vertex) and measure its run time on each. Include at least 20 size/density combinations. (Start with small graphs; increase sizes until runs are taking a minute or two.)
Write a brief report (2-3 pages, say) summarizing your big-O analysis and measurements. Include a graph (old fashioned scatter plot) of run time versus problem size. Compare to the theoretical big-O bounds for your sample graphs. Are your observations in line with the dogma I've been spouting all quarter about the utility of big-O analysis? Are there discrepancies? Can you explain them? Does number of edges versus number of vertices have any bearing on performance? Also, if possible, give us a quick summary of the kind of processor on which you ran your timing tests. E.g., "233 Mhz Intel Pentium II with 64k cache and 96Mb RAM."
To simplify your job doing the timing measurements, the random graph generator from the last assignment could be used. [Alternatively, make your own random graphs by putting edges between vertices with some small probability p. The expected average degree of the resulting graph will be about p*n.]
Hints on timing measurements: Again, it may be so fast on small graphs that you can't get accurate times. If so, rerun it several times on the same input and measure total time. Also, record separately or exclude from your timing measurements the time spent reading inputs, since this may dominate the interesting part.
Another warning: this algorithm will be very slow on large graphs with many edges, so start with small and/or sparse examples and work up cautiously. (Do you know how to abort a running program without rebooting? No? Did you save your files before you started it running? No? Can you wait 100 years for it to finish?)
 |
Computer Science & Engineering University of Washington Box 352350 Seattle, WA 98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to cse417-webmaster@cs.washington.edu] |