This page is no longer being updated and remains online for informational and historical purposes only. The information is accurate as of the last page update.
For questions about page contents, contact the Communications Division.
The work that Rupesh Gajurel ’09 (Kathmandu, Nepal) did this summer researching network connectivity could one day make cell phones and other communication devices work more effectively.
The electrical & computer engineering and math double major served as a research assistant for Ge Xia, assistant professor of computer science, during a Research Experiences for Undergraduates (REU) project. Lafayette’s REU program is an intensive, eight-week summer research experience in which undergraduate students from colleges and universities throughout the country investigate unsolved problems in mathematics. Student participants work in small groups directed by individual faculty members.
Under the Xia’s guidance, Gajurel; Teruhisa Haruguchi ’07 (Saitama, Japan), a computer science and math double major; Janine LoBue of Loyola College in Maryland; James Pierce of Illinois Institute of Chicago; and David Roberson of North Carolina State University, teamed up to research a graph theory problem called Maximum Independent Set.
“Informally speaking, given a set of dots and some lines between them, the problem is to find the largest subset of dots such that there is no line between any two of them,” Xia explains. “It is a classic problem in computer science and has a lot of applications in areas of science and engineering.
The goal, Xia adds, is to find a new and faster algorithm for solving this problem. In doing so, the students gain experience in fields such as graph theory, discrete math, and computer programming. They are also exposed to the methodology of conducting independent and original research.
“We are trying to understand greedy routing in unit disk graphs,” says Gajurel. “It is very applicable even though it is math-intensive. If we could figure out a way to improve current routing methods, it would be beneficial in terms of communication and connectivity. For example, cell phones can be used more efficiently.”
A unit disk graph is an intersection graph of circles of unit radius on a plane. Gajurel explains that in greedy routing, if you start with node A and the destination is node D, then it follows that you choose a neighbor of node A that is closest to D.
“We have found out that greedy embedding might present some obstacles in planar graphs but if we use hyperbolic space then those problems can be solved,” he says. “From this research we can better understand how we can improve network connections in our technological innovations.”
Gajurel appreciated Xia’s hands-off approach to the project, since “research is not like a class, he lets you become more independent.” He also enjoyed the opportunity to work with students from other colleges and universities.
“Different students come with different skills, backgrounds and knowledge,” Gajurel says. “This diversity of experience creates a very rigorous and multi-dimensional environment for research.”
In turn, Xia was impressed with Gajurel’s abilities.
“Rupesh showed a lot of potential and interest as a student when he took my introductory course in computer science,” Xia says. “I thought that it might be helpful to expose a good student to research as early as possible. He is very diligent.”
Research opportunities such as REU were catalysts for Gajurel choosing math as a major at Lafayette.
“I became interested in electrical and computer engineering after I enrolled in Lafayette but I have always loved math and the fact that it is universal in our life,” he explains. “And with the department being one of the strongest, because of its excellent faculty, I decided to go for math. Lafayette is a good place to major in math because of friendly competition, excellent professors and outstanding research opportunities. Lafayette encourages students to pursue projects that many undergraduates don’t get to do in other larger schools.”
Xia says that by exposing undergraduate students to research, the REU program allows students to reach for something that is beyond the classroom.
“In doing so, they would consolidate and apply the knowledge they have learned in classrooms,” Xia continues. “In particular, if they are going to attend graduate school and get a PhD, this experience will be a head-start for them.”
Most students who have participated in Lafayette REU program have published papers in professional journals and presented talks on their summer research at national mathematics conferences. The students who worked on Xia’s project are preparing a paper that will be submitted to a journal and for presentation at a national conference.