Skip to content

Latest commit

 

History

History
180 lines (164 loc) · 4.72 KB

notes.org

File metadata and controls

180 lines (164 loc) · 4.72 KB

Notes

Problem:

  • writing latex2e algorithms is cumbersome
    • latex has terse syntax
    • need to learn specific syntax
  • Yet it is preferred to a source block
    • it is universal no dependency on a specific language
    • Looks good

Idea

  • write your algorithms in python
  • it is sometimes even compared to pseudocode
  • Map constructs to the closest equivalent e.g. comments
  • Can we do the inverse process algorithm2e -> python In general not. But algorithms that were translated should be also possible to translated back python -> algorithm2e -> python
  • Interface algorithm2e < test.py > algorithm.txt Will produce tex source code

How

  • leverage the AST want to test this module
  • simple text replacement may also work

Further

  • could this be abstracted to other languages than python?

Progress

  • [-] FormattedValue
  • [-] JoinedStr
  • [-] Dict
  • [-] Starred
  • [ ] IfExp (ternary)
  • [ ] Subscript, Slice
  • [ ] Comprehensions!
  • [ ] Raise
  • [ ] Assert
  • [ ] Delete
  • [ ] Import
  • [ ] ImportFrom
  • [ ] alias
  • [ ] Try
  • [ ] ExceptHandler
  • [ ] With
  • [ ] withitem
  • [ ] MatchSequence
  • [ ] MatchStar
  • [ ] MatchMapping
  • [ ] MatchClass
  • [ ] MatchAs
  • [ ] MatchOr
  • [ ] FunctionDef.decorator_list
  • [ ] ClassDef

I would argue that classes have also no place here They require a precise semantic But different programming languages vary alot So it is not clear what it would be in pseudocode As an alternative maybe allow classes as a kind of wrapper So put the attributes as global vars and the methods as normal functions Then we need to be careful with “self”

  • [ ] async
  • [ ] AsyncFunctionDef
  • [ ] Await
  • [ ] AsyncFor
  • [ ] AsyncWith
  • [-] Global
  • [-] NonLocal

I think we shouldnt support global and nonlocal as they are generally bad practice and should have no place in pseudocode

Tasks

  • [-] Find example code
  • [ ] what is the expected result
  • [X] preview the result compile the latex use a minimalistic header
  • [-] create a test file with all possible constructs
  • Challenges: when to insert math $$ delimiters. How can we check if a line is ended? I think \; should be added.
  • How to map constructs that have no algorithm2e equivalent? either just ignore them or replace them literally
  • check the algorithm2e documentation for options

Examples

Colorful Paths

a = None
b = "foo"
c = (1, 2, 3)
d = 3.13412342314234
def colorful_paths(V, N, gamma):
    for v in V:
        P[i][(u, v)] = set()
        for x in N(v):
            for S in P[i-1][x]:
                if gamma(v) not in S:
                    P[i][(u, v)] = P[i][(u, v)] | {S | { gamma(v) }}

\begin{algorithm} \ForAll{\( v ∈ V \)}{ \( P_i(u, v) ← ∅ \) \; \ForAll{\( x ∈ N(v) \)}{ \ForAll{\( S ∈ Pi-1(x) \)}{ \If{ \( γ (v) ¬\in S \)}{ \( P_i(u, v) ← P_i(u, v) ∪ \{ S ∪ \{ γ (v) \} \} \)\; } }}} \end{algorithm}

Minimal Cut

\begin{algorithm} \( G’ ← G \) \; \While{\( \lvert V (G’) \rvert > 2\) }{ \( e ← \) uniform random edge in \( G’ \) \; \( G’ ← G’ / e \) \; } \Return{Size of the unique cut in \( G’ \) } \end{algorithm}

Flows

\begin{algorithm} \SetKwInOut{Input}{input} \SetKwFunction{FordFulkerson}{Ford-Fulkerson} \Input{ \( m, r, c_1, … , c_m, L_1, … , L_m \) }

\( (V = (X ∪ G ∪ \{ s, t \} ), A, c, s, t) \) ← build Network as described in part a)\; $f$ ← \FordFulkerson{ \(V, A, c, s, t \) }\;

\If{ \( val(f) ≠ ∑i=1m c_m \)}{ \Return{Assignment not possible} \; } \Else { \ForEach{\( i ∈ [r] \) }{ \( G_i \) ← ∅ \; } \ForEach{\( i ∈ [m] \) }{ \ForEach{ \( j ∈ [r] \) } { \If{ \( f(x_i, g_j) = 1 \) }{ take next available name from \( L_i \) and put it in list \( G_j \)} } } \Return{\( G_1, … , G_r \) } }

\end{algorithm}

Quickhull

\begin{algorithm} \caption{convexHull} \SetKwInOut{Input}{input} \SetKwFunction{mergeHull}{mergeHull} \SetKwFunction{convexHull}{convexHull} \SetKwFunction{partition}{partition} \DontPrintSemicolon \Input{ Set of points \( P ⊂ \mathbb{R}^2 \) } \Output{ Convex hull of \( P \) }

\If{ \( \lvert P \rvert \leq 3\) }{ \Return{ \( P \) } \; } \( P_1, P_2 ← \) \partition{P} \; \( H_1 ← \) \convexHull{P_1} \;
\( H_2 ← \) \convexHull{P_2} \; \ \Return{ \mergeHull{ \( H_1, H_2 \) } } \end{algorithm}