Programmes useful for INF234 course at UiB

This repository includes a lot of algorithms being useful for the UiB course INF234 Algorithms

Programmes

• BellmanFord.py: Solving a distance problem with Bellman-Ford
• BellmanFordLong.py: Solving a distance problem with Bellman-Ford printing states
• DFStime.py: DFS including prefix order
• Dijkstra.py: Solving a distance problem with Dijkstra
• EditDistance.py: Calculating the EditDistance between two words
• FordFulkerson.py: Finding the flow with FordFulkerson
• FordFulkersonInner.py: Finding the flow with FordFulkerson by starting at one inner state
• GraphMST.py: Solving Minimum Spanning Tree with Kruskal
• GraphMST2.py: Solving Minimum Spanning Tree using networkx
• Hufman.py: Calculates Hufman code
• HufmanWithoutWord.py: Calculates Hufman Tree without generating the code
• Knapsack.py: Solving a Knapsack problem
• ShortestDistance.py: Calculates the EditDistance between two strings
• SubsetSum.py: Solving a SubSet sum problem (special case of Knapsack)

How to use them

Subset sum

python SubsetSum.py 20 3S4S5S7S11
Parameter: max weight, sequence of weights (separator: S)
Attention: List of elements doesn't work, use Knapsack

Knapsack

python Knapsack.py 20 3S4S5S7S11 3S4S5S7S11
python Knapsack.py 10 4S4S5S3S2S6 10S11S14S6S5S14
Parameter: max weight, sequence of weights (separator: S), sequence of values (S)
Subset sum by setting weights and values equal

Minimum Spannung tree

Two programmes: GraphMST self programmed Kruskal
GraphMST2 is framework implementation of Prim and Kruskal
GraphMST only accepts numbers as node names
python GraphMST.py
python GraphMST2.py

Edit distance

Takes as input two words
Calculates control value via Levensthein framework
python EditDistance.py klinger klingre

BellmanFord

Calculates shortest path in graph
Input path lengths in code
Does not output internal table
Long version has output
python BellmanFord.py
python BellmanFordLong.py

Dijkstra

Shortest path without negative edges
Input path lengths in code
Argument is start node
python Dijkstra.py a

FordFulkerson

Two programmes, one for the entire algorithm and one for one iteration

Entire programme: insert edge weights in tuple orig_cap
python FordFulkerson.py

Just one iteration, three lists (third redundant, sorry)

• orig_cap: edge weights in original graph
  
• g_edges_used: used flow at the moment
  
• g_f_edges: all edges of residual graph
  python FordFulkersonInner.py

Hufman

insert string as argument, spaces with "_" string Make sure the | are positioned like Pål wants them to be (like at beginning or end of word)
Second programme without words, but frequencies
python HufmannTree.py testiest_sensitiveness
python HufmanWithoutWord.py