# DidaWiki

### An example of interaction with student "A."

Instructor “RG” made a little editing for the sake of presentation:

A.: For my report for the Algorithm Design course I would like to write about min- or max-cut randomization of graphs or maybe a comparison of both of them. Would this be alright?

RG: Ok A., please send me a sketch of the organization when you are ready.

A.: Attached you can find the basic outline for my report:

  Min-Cut vs. Max-Cut randomization for Graphs
0. Introduction
1. Basics
2. Min-Cut
3. Max-Cut
4. Comparison
5. Conclusion
6. References

RG: are you discussing also somehow the approx limitations of the max cut problem?

A.: I could add a subchapter about the approximation limitations in the Max-Cut chapter or write something about it in the Basic Idea of Max-Cut subchapter.

RG: Ok A., please proceed to the next step.

A.: Attached you can find an updated and more detailed outline for my report.

  Min-Cut vs. Max-Cut randomization for Graphs
  0. Introduction
Introduction to the reports topic and goals:
- Explain the idea of Min-Cut and Max-Cut
- Comparison of the approaches

1. Basics
Give some basic definitions for later used concepts in the report
a. Graphs
Description of the basic understanding of Graphs and Multigraphs in the context of this report
b. Randomizations
Definition of Randomization in the context of this report

2. Min-Cut
a. Basic Idea of Min-Cut
- Description about how min-cut works
- Example graph for Min-Cut
b. Better Min-Cut
Description of how the probability of the algorithm can be improved

3. Max-Cut
a. Basic Idea of Max-Cut
- Description of the basic idea behing Max-Cut
- Example graph for Max-Cut
b. Approximation Limitations
Description of the limitations for the approximation of Max-Cut
c. Approaches for Max-Cut
Description of the different approaches of Max-Cut we have learned
i. Local Search
Description of the algorithm we learned in the lecture with example graph
ii. Greedy
Description of Greedy algorithm from the lecture
iii. Randomization and Derandomization
- Max-Cut with randomization and with derandomization
- Use of universal hash functions and conditional expectations

4. Comparison
Runtime and output comparison
a. Similarities of the Cut randomization
Where are the approaches similar
b. Differences
Where are the obvious and not so obvious differences between the approaches of Min- and Max-Cut
c. Uses
Description where the different approaches are being used and how effectful they are being used

5. Conclusion
Summary of the different approaches mentioned in the report and of the results of the comparison

6. References
List of references that were used in this report


RG: Very good plan! You can proceed and finalize the report. When ready, contact me, so we can fix a date to read togther and comment your report in my office.

magistraleinformatica/ad/ad_19/interaction/start.txt · Ultima modifica: 20/02/2020 alle 09:38 (23 mesi fa) da Roberto Grossi