Skip to content

Instantly share code, notes, and snippets.

View harfangk's full-sized avatar

Bonghyun Kim harfangk

41 followers · 0 following
View GitHub Profile
@harfangk
harfangk / kosaraju.hs
Created April 28, 2019 09:31
Naive implementation of Kosaraju's algorithm in Haskell
module Kosaraju where
import qualified Data.Set as Set
import qualified Data.Map as Map
import qualified Data.List as List
type Graph = Map.Map Int [Int]
sccMain :: IO ()
sccMain = do
@harfangk
harfangk / knapsack.hs
Created October 26, 2019 15:53
Knapsack algorithm
import qualified Data.Array.IArray as IArray
import qualified Control.Monad.ST as ST
import qualified Data.HashTable.Class as HT
import qualified Data.HashTable.ST.Cuckoo as Cuckoo
type HashTable s k v = Cuckoo.HashTable s k v
knapsack :: IArray.Array Int (Int,Int) -> (Int, Int) -> Int
knapsack items (i,x) = ST.runST $
do ht <- HT.new :: ST.ST s (HashTable s (Int,Int) Int)
@harfangk
harfangk / Bellman Ford.hs
Last active May 18, 2020 02:00
import qualified Data.List as List
import qualified Data.Map as Map
import qualified Data.IntMap.Strict as IntMap
import qualified Data.Sequence as Seq
import qualified Data.Array as Array
import qualified Data.Maybe as Maybe
import qualified Control.Monad.ST as ST
import qualified Control.Monad as CM
import qualified Data.PQueue.Prio.Min as MinHeap
@harfangk
harfangk / g3.txt
Created May 17, 2020 05:48
1000 47978
1 8 36
1 33 29
1 38 18
1 63 25
1 76 39
1 100 26
1 105 41
1 120 20
1 131 34
@harfangk
harfangk / bellman-ford.prof
Created May 17, 2020 05:49
Sun May 17 14:42 2020 Time and Allocation Profiling Report (Final)
stanford-algorithms-exe +RTS -N -p -RTS
total time = 3.02 secs (12100 ticks @ 1000 us, 4 processors)
total alloc = 9,296,011,352 bytes (excludes profiling overheads)
COST CENTRE MODULE SRC %time %alloc
bellmanFord.findMin Course4.Week1 src/Course4/Week1.hs:131:5-117 63.1 82.9
@harfangk
harfangk / bellman-ford-2.prof
Created May 17, 2020 06:14
Sun May 17 15:12 2020 Time and Allocation Profiling Report (Final)
stanford-algorithms-exe +RTS -N -p -RTS
total time = 2.71 secs (10860 ticks @ 1000 us, 4 processors)
total alloc = 1,665,818,880 bytes (excludes profiling overheads)
COST CENTRE MODULE SRC %time %alloc
foldl' Course4.Week1 src/Course4/Week1.hs:130:70-177 82.3 47.0
@harfangk
harfangk / bellman-ford-3.prof
Created May 17, 2020 06:24
Sun May 17 15:23 2020 Time and Allocation Profiling Report (Final)
stanford-algorithms-exe +RTS -N -p -RTS
total time = 2.70 secs (10815 ticks @ 1000 us, 4 processors)
total alloc = 1,665,817,824 bytes (excludes profiling overheads)
COST CENTRE MODULE SRC %time %alloc
foldl' Course4.Week1 src/Course4/Week1.hs:130:93-224 78.4 47.0