What are the solutions to these questions?
I am trying to re-learn algorithms, since I'm feeling really unconfident about solving interview questions. These are some of the starter questions from the book "Algorithms in C, Part 1-4" by Robert Sedgewick. I am not really confident in any of my answers.
- Give the output that a connectivity algorithm should produce when given the input 0-2, 1-4, 2-5, 3-6, 0-4, 6-0, and 1-3.
My solution:
| Input | Output | Connection |
|---|---|---|
| 0-2 | 0-2 | - |
| 1-4 | 1-4 | - |
| 2-5 | 2-5 | - |
| 3-6 | 3-6 | - |
| 0-4 | 0-4 | - |
| 6-0 | 6-0 | - |
| 1-3 | - | 1-4-0-6-3 |
- List all the different ways to connect two different objects for the example in Figure I.I.
https://lemmy.ml/pictrs/image/a6893d99-aa47-45d2-ae42-39f9dfe8174c.png
My solution:
No idea, honestly.
- Describe a simple method for counting the number of sets remaining after using the union and find operations to solve the connectivity problem as described in the text.
My solution:
We use a variable "count" that increments for the pair of objects that were not previously connected, using the find function.