64
edits
Changes
m
→Assignment 1
Original source code can be found [https://github.com/shafeeq/Sudoku here].
At best, we expect the process time to drop from 17.13 secs to about 17.13 / 1.88 = 9.11 secs
CheckSquare()
O(n) = 8n^3 + 3n^2 + 10n
CheckColumn()
O(n) = 6n^2 + 4n
CheckRow()
O(n) = 6n^2 + 4n
Print()
O(n) = 4n^3 + 3n^2 + 3n
StorePositions()
O(n) = 4n^3 + 3n^2 + 3n
GoBack()
O(n) = 11n
PlaceNum()
O(n) = 7n^2 + 5n
SolveSudoku()
O(n) = 8n^3 + 3n^2 + 2n
Main()
O(n) = 15n^3 + 7n^2 + 15n
Entire program
O(n) = 42n^3 + 38n^2 + 59n
The Big-O of the Sudoku program is O(n^3), or cubic. This program would be idea for parallalizing.
The reason we chose the Sudoku solver was because we felt that the Sequence Alignment was too complex of an algorithm to work with, and the image processor seemed a bit too simple to parallelize. The sudoku solver seemed to be the right balance in terms of complexity as well as potential speed up. We are nearly cutting the time in half for a standard 9x9 puzzle, but as the puzzles get harder, through either an increase in the matrix size, or through an increase in blank numbers to be solved, we would expect even better performance through parallel programming than standard serial programming.
