It is a good start. I think the weakest aspect is your lack of experience coding in Python/Cython. You need to set aside time for familiarizing yourself with the Sage development process, preferably during the orientation period. Your goal should be to fix one of the open tickets (not necessarily a matroid one, just pick an easy one), and to review one other ticket.
What matroid intersection algorithm do you have in mind? Can you put in some references? I'm curious about Rajan's algorithm in particular. --Stefan. On Thursday, March 19, 2015 at 2:42:32 PM UTC-5, Chao Xu wrote: > > I won't be around my campus in the summer, so I'm able to work the desired > amount of time. My advisor grants me freedom to work on anything of my > interest during the summer. > > Here is my draft proposal, do you have any suggestions? > > Personal > *Name: *Chao Xu > *Contact: *[email protected] <javascript:> > *Location/Timezone: *Urbana, PST > *University: *University of Illinois at Urbana–Champaign > *Background:* > *What are your technical skills, education, experience, etc. Especially > make sure to explain with what level of mathematics you are comfortable > with and on what level you would like to program.* > I’m a PhD student of computer science at UIUC. I specialize in algorithms. > My adviser is Jeff Erickson <http://web.engr.illinois.edu/~jeffe/>. > Mathematically, my experience lies in combinatorics and theoretical CS. I > have somewhat decent knowledge on matroid because I encounter them when I > work on submodular functions. > Although I mainly program in Java and Haskell, but I do have C++ and > python experience. I frequently help students with their python code > (albeit simple). In my undergrad years I worked on a site > <https://github.com/Mgccl/FlexE/> with Django, which requires me to write > python. > *Who are you? What makes you the best person to work on this particular > project? Special motivation?* > I have an interest in combinatorial optimization. Matroid comes up often > in the field. It will be useful for me to learn the related matroid > connectivity and actually implement some optimization algorithms on > matroids. > I’m used to coding algorithms. Some more recent code samples (in haskell) > include local affine alignment > <https://github.com/Mgccl/mgccl-haskell/blob/master/rosalind/LocalAlign.hs> > , Sardinas Patterson algorithm > <https://github.com/Mgccl/haskell-algorithm/blob/master/SardinasPatterson.hs> > and Aho Corasick automaton > <https://github.com/Mgccl/haskell-algorithm/blob/master/AhoCorasick.hs>. > I have also implemented a simulation for X-ray crystallography in C++ while > working at Brookhaven National Lab, and wrote algorithms for manipulating > curves on surfaces for Moria Chas > <http://www.math.stonybrook.edu/~moira/index/Welcome.html>. > *What platform and operating-system are you using on your computer? > (Sage development is done best on Linux and OSX)* > I use OSX. > *Are you or have you been engaged in other open-source projects?* > I had contributed a few open source codes and documentation for Drupal > when I was in high school. > *Do you code on your own pet projects?* > I have a few pet programs <https://github.com/Mgccl/> written in Haskell. > The largest should be the program that generates my website > <https://github.com/Mgccl/blog>, using Hakyll and a format that I call > MathDoc <https://github.com/Mgccl/blog/blob/master/MathDoc.hs>. > *Are you a Sage user, how long do you know Sage?* > I had 2 months of SAGE experience during an REU in 2012, where I use it in > order to experiment on a game of graph nim > <http://web.engr.illinois.edu/~chaoxu3/paper/spider.pdf>. > Project > *Title:* Connectivity and optimization problems on matroids > *Synopsis:* > This project implements a few fast optimization algorithms on matroids. > This includes fast algorithms for matroid intersection(weighted/unweighted) > and 3-connectivity algorithm by Bixby and Cunningham (1979), 4-connectivity > by Rajan (1987) and higher level connectivity algorithms using matroid > intersection. The project will also provide useful examples of matroid > intersection. > *What is your personal involvement or relationship with your proposed > project?* > I will implement algorithms listed. > *Details:* > > 1. Connectivity: fast algorithms for k-connectivity. > - 3-connectivity algorithm by Bixby and Cunningham > - k-connectivity using matroid intersection. > - 4-connectivity algorithm by Rajan. > 2. Matroid intersection: > - Implement the O(n^{3/2}m) time algorithm for matroid > intersection. m is the groundset size, n is the size of the maximum > common > independent set. (Cunningham 1986) This is important for > faster k-connectivity algorithm. > - faster weighted intersection. (it might be faster than the > current augmenting path implementation) (Schrijver 2003, chapter 41) > - Build a collection of matroid intersection examples: > - matroid partitioning algorithm. This will establish a connection > to the graph theory package, as it can be used directly to find the > arboricity of a graph. > - matroid union rank oracle. > - minimum cost arborescence. > > *Schedule:* > *Now - 25th May*: Background research: Learning about various algorithms > and how the matroid packages work. > *25th May – 10th June:* Implement 3-connectivity algorithm and > 4-connectivity algorithm. > *10th June - 15th June:* k-connectivity algorithm. > *16th June - 26th June:* Work on faster algorithms for matroid > intersection. > *27 June – 5 July:* Midterm evaluation period, finish up left overs. > *6 July - 17 July: *faster weighted matroid intersection algorithm. > *20 July - 11 August: *Building useful examples of the matroid > intersection. Matroid partition algorithm, matroid union rank oracle, min > cost arborescence. > *11 August - 18 August: *Finishing up, provide documentation and a nice > wiki page for everything implemented in the summer. > *Risk Management:* The algorithm implementation of connectivity > algorithms might take longer than expected. Rajan’s algorithm is described > for representable matroids, and I would need to figure out if it is still > fast if it only have access to independence oracle. There is a large amount > of time allocated for useful examples of matroid intersections. I can > always save some time on those and focus on connectivity. > > Best, > Chao Xu > > > On Tue, Mar 17, 2015 at 11:29 AM, Stefan van Zwam <[email protected] > <javascript:>> wrote: > >> These things have a way of filling up your time, so I don't think it's >> too little. You could include some minor work (improving the catalog, e.g. >> by adding options for the type of representation of the matroids in it, or >> forging more links between the coding theory, graph theory, and matroid >> theory parts of Sage, computing the automorphism group of a matroids, ...) >> >> Will you be able to work the desired amount of time this summer? Is your >> PhD supervisor on board with you doing this? >> >> Cheers, >> >> Stefan. >> >> >> >> On Sunday, March 15, 2015 at 7:37:47 PM UTC-5, Chao Xu wrote: >>> >>> Hi Stefan, >>> >>> How fast is the current weighted matroid intersection algorithm? It >>> seems to be the naive augmentation one. >>> >>> Also, I'm thinking about solving the following problems in the proposal. >>> >>> 1. Connectivity: fast algorithms for k-connectivity. >>> - 3-connectivity algorithm by Bixby and Cunningham >>> - k-connectivity using matroid intersection. >>> - track down the faster 4-connectivity algorithm in Rajan's PhD >>> thesis and see if it's reasonable to implement. [Rajan 1987] >>> 2. Matroid intersection: >>> - Implement the $O(n^{3/2}m)$ time algorithm for matroid >>> intersection. $m$ is the groundset size, $n$ is the size of maximum common >>> independent set. [Cunningham 1986] >>> - fast weighted matroid intersection. (this can be ignored if the >>> current one is already as fast) [Schrijver 2003, chapter 41] >>> - Some applications based on matroid intersection: matroid >>> partition algorithm, matroid union oracle. >>> >>> I wonder if this is too little to do for the summer. >>> >>> On Friday, March 13, 2015 at 1:09:05 PM UTC-5, Chao Xu wrote: >>>> >>>> Hi Stefan, >>>> >>>> Thanks for the reply. I know the definitions for many matroid concepts >>>> and its applications. >>>> For example, I have no problem reading the chapter on matroid in >>>> Schrijver's book. >>>> I don't have background with the deeper theories. >>>> >>>> On Monday, March 9, 2015 at 11:35:09 PM UTC-5, Stefan van Zwam wrote: >>>>> >>>>> Hi Chao, >>>>> >>>>> The state of the art in 3-connectivity algorithms is a 1979 book >>>>> chapter by Bixby and Cunningham, see >>>>> http://www.ams.org/mathscinet-getitem?mr=538038 (you'll have to dig >>>>> it up from a library, most likely). For matroid union and intersection, >>>>> Schrijver's 3-volume Combinatorial Optimization is a good reference. >>>>> >>>>> How much do you know about matroids? >>>>> >>>>> Cheers, >>>>> >>>>> Stefan van Zwam. >>>>> >>>>> On Tuesday, March 3, 2015 at 2:39:49 PM UTC-6, Chao Xu wrote: >>>>>> >>>>>> Hi all! >>>>>> >>>>>> I'm Chao Xu, a computer science PhD student at UIUC. >>>>>> - I had experience with Sage a few years ago during an REU, and I >>>>>> sometimes dub in python. >>>>>> - I have lot of experience implementing algorithms(although it's in >>>>>> Java). >>>>>> - I'm interested in combinatorial optimization, and believe >>>>>> implementing some algorithms for matroid seems to be a good introduction >>>>>> to >>>>>> this field. >>>>>> >>>>>> Any papers could bring me up to speed with the current state of art? >>>>>> So I might get a feeling of what is feasible. >>>>>> >>>>>> Best, >>>>>> Chao >>>>>> >>>>> -- >> You received this message because you are subscribed to a topic in the >> Google Groups "sage-gsoc" group. >> To unsubscribe from this topic, visit >> https://groups.google.com/d/topic/sage-gsoc/f4zUkolcX8A/unsubscribe. >> To unsubscribe from this group and all its topics, send an email to >> [email protected] <javascript:>. >> To post to this group, send email to [email protected] >> <javascript:>. >> Visit this group at http://groups.google.com/group/sage-gsoc. >> For more options, visit https://groups.google.com/d/optout. >> > > -- You received this message because you are subscribed to the Google Groups "sage-gsoc" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/sage-gsoc. For more options, visit https://groups.google.com/d/optout.
