We wanted to explore concepts from real analysis using algorithms and concepts from computer science. The Bolzano-Weierstrass Theorem states that every bounded sequence has a convergent subsequence. We wanted to develop an algorithm that finds a convergent subsequence provided a sequence and a limit to converge upon. Computers are finite, so we approximate a sequence by computing the first n terms of a sequence. Then we can find the longest convergent subsequence of the approximation.
What It Does
Our program takes a specified sequence or generates a sequence of random floating point numbers. It also takes the limit we want to converge upon. The progress as a percentage of finding the longest subsequence is printed out. The user has the option of printing the longest subsequence along with plotting the longest subsequence and the original sequence on a graph.
How We Built It
Our algorithm finds the longest convergent subsequence by computing all of the subsequences recursively and eliminating ones that don't satisfy convergence. While it does this, it keeps track of a list of the maximum sequences for each entry in the sequence so it doesn't have to repeat the computations. It also doesn't bother computing sequences when there aren't enough elements left to beat the current maximum.
Challenges We Ran Into
At first we weren't keeping track of any previous subsequence computation. This meant that it was an O(n!) algorithm because it was repeating unnecessary computations. We fixed this by caching the maximum sequence from each point after the computation so it didn't have to be re-computed later on. It now has a worst case of polynomial time.
Accomplishments That We Are Proud Of
We are proud of developing an efficient longest path algorithm and applying that to a mathematical concept that is completely unrelated. We successfully identified longest subsequences in random sequences of 10000 elements. We are proud of our overall product. It is always exciting to see what you created after lots of hard work.
What We Learned
We learned about developing software on our own outside of the classroom. We used proper software development techniques such as separating front-end and back-end code. Overall, we learned a lot about maintaining a project.
What's Next for Convergence
We would like to improve our algorithm to compute the longest subsequence of the given sequence and not rely on user input for a limit. We would also like to have a GUI rather than a text based input/output. Finally, it would really cool to implement our solution in Jython instead of Python and run our program as an interactive GUI in a .jar file.