GSoC 2013 Application Ishaan Batta: Group Theory

Personal Information

Name: Ishaan Batta Email: [email protected] Telephone(mobile) : +918860486068

IRC nick: ishbat Skype: live:ishaanbatta GitHub username: ishaanbatta Blog: http://gsoc2013ishaan.blogspot.in/ Residential Address: 86, Street-6, Guru Angad Dev Nagar Amloh Road, Khanna-141401 Punjab province India University Address: WC-12 Shivalik House, Indian Institute of Technology, Hauz Khas-110016, Delhi

University Information

University: Indian Institute of Technology, Delhi Major Subject: Computer Sciences Degree: B.Tech + M.Tech (Dual) Current year: 1st (entering 2nd) Expected Graduation year: 2017 (B.tech+M.Tech)

Project Proposal Information

Proposal Title: Group Theory

Motivation: I am not just a coding enthusiast but also curious about implementation of algorithms. I believe that applying the theoretical principles of Mathematics and Computer Sciences through coding can drastically contribute to the way we use computers and similar devices and can provide mind-blowing facilities to common people. So being a computer science undergraduate student, I strongly wish to input my best efforts for the same.

Background

Regarding Groups: I have done an exclusive course on Group Theory and abstract Linear Algebra(MAL124) last semester. So, i have a very nice knowledge from the basics to the particular implications of the Group Theory.

References: thoroughly explored: Contemporary Abstract Algebra by JA Gallian Topics in Algebra by IN Herstein partially explored: Matrix Analysis and Applied Linear Algebra by Carl.D.Meyer

Regarding Algorithmic Thinking: The courses i have done till now are mainly regarding Algorithmic thinking. I did a course on Data Structures and Applications this semester. So, have an apt knowledge to build short running algorithms and use the correct data structure a particular phase so as to reduce the running time and the space required for an algorithm to work.

Regarding coding: I have been coding mainly in python and java. I am sufficiently familiar with python, which happens to be the coding language of the project. I prefer to use python in the Ubuntu machine but i also use IDLE platorm.

Regarding Sympy: I am only 2-3 weeks old to sympy in Gsoc 2013. Under the Sympy module on github, i have been focusing on the combinatorics part. I have analysed the source codes related to the following under combinatorics: generators, group constructs, permutations, permutation groups, subsets, polyhedron etc.

Execution Plan: With my current semester ending on MAY8, I will be free all through the summers to get started with Gsoc! I have kept my plan a bit dynamic so that if a part takes a longer time to accomplish, there is enough flexibility available to complete the task in time. I have divided my plan into the following tasks:

TASK 1: (~1 week) {Till MAY 22 } To Understand properly the present features available for groups in the Sympy library and discuss any queries regarding this with the mentor. 1.To understand all the present features supported by sympy for groups. 3. To come up with a List of extended additions required to enhance the library including the corresponding specifications found out by step 2. 4. To discuss the final documentation with the mentor and make further modifications if required.

TASK2: To Analyze the different improvements and/or additions required in the present implementation of the groups module and To sort out the possible ways to do the same.

Note: All the steps below may require long discussions with the mentor. Note: All the steps below include studying analyzing the existing corresponding code too.

• (May 22-28, 1 week)To find out the shortcomings of the current implementation and deduce the guidelines. -(May 28-June 5, ~1 week) To analyze different types of input queries required to support the library and To analyze all possible 'tokens' which can be incorporated for the groups module.
• (Jun 5-7, 2-3 days)To analyze the support of groups through generators. -(Jun 8-9, 1-2 days) For non cyclic groups, sort out a way to generate them through multiple generators of the subgroups.
• (Jun 9-11, 2-3 days)To analyze additions/improvements for Normal Subgroups.
• (Jun 11-14, 3-4 days)To analyze the permutations group and come up with improvements.
• (Jun 15-19, 4-5 days )To Analyze the possibilities of including/improving Euclidean Domains in the library.
• (Jun 20-22, 3-4 days)To deal with incorporating the infinite order groups and try to find a way out.
• (Jun 22-25) Discuss all the results, preferably in a documented form, with the mentor and select the viable options with guidance from the mentor. -(Jun 26)-- FINALIZE a list of all the required additions/improvements obtained from the above steps

TASK3: To Develop improved algorithms (NOT CODES) and analyze the required data structures for the results of Task 2.

Note: This is THE MOST IMPORTANT PART of the whole project as it will be difficult to handle the further steps without executing this one properly. This part may require a little less guidance from the side of the mentor as it will is the aspect of the coder's mindset.

-(Jun 27-29, 2-3 days) To analyze the base cases, hypothesis and induction result (or the Invariant) for all the Methods to be implemented. -(Jun 29-July 5, more than a week) To sit and draft all the algorithms for the various outcomes of Task-2, along with the guidance by the mentor for the same. (This and the next part is a bit time consuming but required for the efficient code drafting) -(July 6-10, 4-5 days) To analyze all the possible and required data structures for the various algorithms of the above step. Since every outcome may have multiple possible algorithms, an analysis of best possible data structures for them is a must so as to select the most suitable one. (The mentor needs to be consulted for finalization of the choice) -(July 10-12) Finally for every required outcome of Task 2, an algorithm along with a suitable data structure will be selected keeping in mind that out of all analyzed ones, it takes the least time and space.

TASK 4: The CODING Part. To start implementing all the methods and classes (in Task 2) one by one using the corresponding algorithms and data structures (in Task 3) as follows:

-(July 12-19, 1 week) To code away the IMPROVEMENTS required that came up in Task 2 & 3. -(July 20-30, 10 days) To code away the ADDITIONS required that came up in Task 2 & 3. -(August 1-10, 10 days ) To run all the test cases on the files and debug accordingly. -(August 11) get the finalized improved and updated version of the Sympy groups module, ready.

-(August 11- 18) Buffer Period: Discussions with the mentor. Refining of the final documentation and make sure that every thing is clearly mentioned in it.