Aditya Karan Kamireddy

This week I mostly worked on the final video, as well as making some small final touches to the paper based on Charlie’s suggestions.

I mostly worked on my poster during this week. There were a number of small issues with my original poster created using LaTeX, which I could not fix without delving into a lot of code, so I recreated it using power point and improved it based on Charlie’s feedback. Igor, my advisor, also pointed out … Read more

I worked on the feedback I received from Igor concerning some of the difficult notation, and overall organization of my paper. I also removed some obvious lemmas and simplified the basic results for the second draft.

I worked on presenting the proof in the most succinct way possible for the poster. I worked on several iterations and finally narrowed down on what is the current first draft. I also received feedback on the first draft of my paper from Charlie, and discussed the paper as well as Charlie’s feedback with Igor.

I spent this week on finishing up a very detailed proof that Parks is NP complete. I also worked on improving the exposition of ideas leading up to the main result in my paper, which really helped me with the software video.

I did not get to do much due to the various disruptions caused by Corona virus. I am currently working on getting things in order and figuring out meeting times with my adviser and whatnot.

I am currently working on a proof that non-contiguous kPARKS is NP-Complete. I am also mostly done with my paper.

Parks Puzzle is a popular puzzle game that is played on a square grid. A Parks Puzzle consists of an nxn grid with contiguous regions known as parks. The aim of the puzzle is to place trees within parks such that every row, column, and park contains one tree, and no two trees are on … Read more

Now that I have a proof for the parks puzzle, I am spending time working on a more general puzzle that we’ve dubbed kPARKS, which is the analogous problem of placing k trees in every row, column and Park. I am also working on writing the proof and the results that build up to the … Read more

This week I worked on finalizing my proof for the IFF and OR gadgets, and rewriting the final proof for the paper draft. I am now planning on working on an explicit algorithm for the reduction for use in the program.

The proof has been completed. This week I will work on writing it out rigorously, as well as designing the program.

This week I took a short break from working on the proof to start working on the app. I am currently trying to figure out whether it is worth designing the Parks app as a webapp, while also starting work on some of the basic modules.

I worked with possible ways of proving that non-contiguous Parks is NP-Complete, and found one good avenue for exploration. Over the week I produced a general technique to convert any instance of 3-SAT to an instance of the non-contiguous Parks Puzzle, thus proving that it is NP-Complete, our first major result. I am working to … Read more

Over this week I finished up an non-contiguous IFF and OR gadgets, however I came to the conclusion, after meeting with Igor, that there does not seem to be a way to effectively put together these two gadgets. However, we also concluded that in most cases, it is not a particularly difficult challenge to find … Read more

This was the first week so I worked on getting back up to speed with the research, and on creating presentations for the first class.

I finished my final proposal and I’m rechecking everything for submission this week.

I only worked on finishing the first draft of the proposal this week.

I finished a first pass of all but one of the papers in my reading list, and also read some of the papers that are highly relevant to my project, which I had already read for a first pass, for a second or third pass depending on how relevant the content seemed. I have also … Read more

I went over the broad categories that need to be addressed by the project proposal, and created a proposal outline for Assignment 7. I also worked with my advisor, Igor, to find a good candidate for the reduction adn start working on the proof. We found that there was a natural way of reducing a … Read more

This week I worked on improving my understanding of the Parks Puzzle and exploring possible proof techniques to show that it is NP complete from two directions. I continued working on the Time Complexity chapters of “Introduction to The Theory of Computation” by Michael Sipser to round out my theoretical understanding, while also solving many … Read more

This week I spent some time finalizing my proposal idea. I discussed the Parks Puzzle with Igor and come to the conclusion that I should work on proving its NP-Completeness for my final project. I had to discuss this idea with my advisor Igor, as well as Charlie and Xunfei before I could finalize this … Read more

I found a very promising paper called “an introduction to the conjugate gradient method without the agonizing pain” and started working through it. I have only gotten through the first 10 pages or so, but it is helping me think of narrower research questions. I have also skimmed through a fair number of NP-completeness reductions, … Read more

I have pretty much decided on my main topic, which is working on the complexity of the Parks Puzzle. I found a survey paper that goes over a number of puzzle problems, and provides a vast reading list, which I am working through now.

Idea #1Name 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 … Read more

Changes to Idea #1There were no major changes recommended, except that the scope of the project could be limited to classical iterative solvers of linear systems. Idea #2Name 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 … Read more

Name of Your Project Iterative solvers for systems of Linear Equations What research topic/question your project is going to address? The effectiveness of various iterative methods at finding solutions to systems linear equations with various characteristics. Taking experimental / numerical analysis perspectives. What technology will be used in your project? C++ for implementing the solvers. … Read more