.. (לתיקייה המכילה) | ||
I don't think you can actually implement the <pre style="display: inline">find_reachable()</pre> function in time linear in the number of edges in the component. | |
Yes, that's technically true. The _computational_problem_ of determining which vertices are reachable from a given vertex can be solved in time linear in the number of edges in the component - but this requires a different representation of the graph, not the adjacency matrices we use in this assignment. So - no need to aim for that complexity. |
In problem 1, can the string <pre style="display: inline">str</pre> be empty? Can it contain only spaces? Can it contain pairs of spaces between words? | |
The string may be empty. It cannot contain only spaces. It cannot contain consecutive spaces. It cannot contain a space after the last word or before the first one. All words in str, by the way, contain some letters - there are no 'empty words'. |
In problem 2b, can we define arrays of size depending on <pre style="display: inline">NUM_VERTICES</pre>, e.g. | |
No, that wouldn't be O(1), since NUM_VERTICES is a parameter of our complexity estimate, it's not a constant at least in this respect. |
In Problem 2, can we assume the graph is cycle-free (i.e. no two paths from one vertex to another)? | |
No, you may not. The graph in the example doesn't have cycles but graphs in general most certainly may have them (a lot of them, even). |