Major Qualifying Project

For my Senior capstone project, I researched different methods to more efficiently solve large binary matrices on small scale computer hardware. Together with my advisor Professor Koksal Mus, the resulting algorithm we developed uses concepts from both Gaussian elimination and an exhaustive search to recursively find partial solutions for each row at a sub-exponential time complexity.

 

Using 1 coefficients for reference, the algorithm iterates through possible solutions for a current row. Solution validity is based on the solutions for previous rows, eventually building to a valid full solution at the end of the matrix. By building and chaining solutions in this fashion we preemptively eliminate invalid full solutions and more quickly find valid ones.

​

​