DidaWiki

Questa pagina è in sola lettura. Puoi visualizzare il sorgente, ma non puoi modificarlo. Contatta l'amministratore se pensi che ci sia un errore.
==== 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.