search

Inocxh / k-connectivity

Repository for a software technology project about k-connectivity
2 stars 0 forks source link

Implementer algoritme 3 #1

Closed Inocxh closed 2 years ago

Inocxh commented 2 years ago

Implementer algoritme 3 Den skal gerne returnere en sandhedsværdi og hvis inputtet ikke er 3-edge-forbundet skal et 2-edge-cut returneres

Inocxh commented 2 years ago

For algoritme 3 skal vi bruge en sortering af n intervaller

Jeg foreslår: Byg en class, bestående af en liste af intervaller Implementer en in-place version af RadixSort på den class ??? Profit.

Denne burde gerne køre i noget der ligner ~O(2(2n)) tid med O(1) space Tænker at in-place er bedst eftersom alternativet ville kræve at opretter alle mulige lister som bliver tømt igen og blablabla, hvor man i in-place versionen kun swapper elementer at most n-1 gange

Update: Jeg går i gang nu med at implementere en collection af intervaller og en sorterings algoritme for dem.

Inocxh commented 2 years ago

Har pushet Intervals klassen der sammen med RadixSorter og RadixSortable kan sortere intervallerne i linær tid. TODO: Implementer omvendt sortering

s204496 commented 2 years ago

Jeg arbejder videre med implementation.