Changes to Idea #1
There were no major changes recommended, except that the scope of the project could be limited to classical iterative solvers of linear systems.
Name of Your Project Computational complexity of the ‘Park Puzzle’
What research topic/question your project is going to address? The Park Puzzle is a game that involves splitting a n*n grid into different colored continuous ‘parks’. A solution to a park puzzle involves marking the position of a tree in each park such that no two trees share a row or a column. The research topic involves exploring various algorithms for solving the park puzzle, and determining some bounds on the computational complexity of the puzzle. The most involved version of this project could be to prove those bounds. (The initial, intuitive hypothesis is that the park puzzle cannot be solved in polynomial time)
What technology will be used in your project?A simple Java program for generating park puzzles coded by Igor (similar apps are also available online). Pen and lots of paper.
What software and hardware will be needed for your project? If computational methods seem like the appropriate way to tackle the problem, then the appropriate software may be written in python for reasonably sized puzzles
How is your project different from others? What’s new in your project? The project is more research oriented, and the end result is not a concrete implementation of an idea as a program.
What’s the difficulties of your project? What problems you might encounter during your project? It is quite likely that the problem is very complex, and a more restricted scope in the same direction might have to be chosen.
Name of Your Project Fast multiplication using p-adics
What research topic/question your project is going to address? There have been significant improvements in algorithms for fast multiplication of integers using p-adic numbers, approaching O(nlogn). The research project would be to explore the theory behind these algorithms and verify their results.
What technology will be used in your project? C++ for writing the algorithms
What software and hardware will be needed for your project? Cluster for testing the algorithms
How is your project different from others? What’s new in your project? It is quite similar to the first idea I had proposed, but involves a different area of mathematics.
What’s the difficulties of your project? What problems you might encounter during your project? I expect most of the difficulties to arise with understanding and analysing the algorithms.