On Undergraduate Research in Computer Science: Tips for shaping successful undergraduate research projects

Note: Khuller was the recipient of the 2020 CRA-E Undergraduate Research Faculty Mentoring Award, which recognizes individual faculty members who have provided exceptional mentorship, undergraduate research experiences and, in parallel, guidance on admission and matriculation of these students to research-focused graduate programs in computing. CRA-E is currently accepting nominations for the 2023 award program.

One of the goals I hope to accomplish with this article is to open the eyes of faculty to the ways in which bright and motivated undergraduates can contribute meaningfully to their research projects and groups. This piece intends to  help educate folks who  have limited experience with undergraduate research or are unsure how to come up with research projects. I hope it helps others learn quickly from the knowledge I have gained over the years.

Exposing undergraduates to research may encourage them to pursue PhDs
At the CRA Conference at Snowbird this summer, data was presented that showed that the overall number of PhDs granted in Computer Science (CS) in the US has not changed substantially in the last decade even though undergraduate programs have grown significantly. Meanwhile, the percentage of US students getting PhDs in CS showed a pretty substantial decline from 48%  to 31%. While there are many factors at play–notably a strong job market for undergraduates– I do know from prior discussions with undergraduate students (UGs), that many CS departments also do not make a substantial effort in exposing UGs to research opportunities. Moreover, when I started as a faculty member I too struggled in defining good research projects for undergraduates (they were either too easy or too similar to PhD research topics, and so were likely not appropriate for undergraduates). I think getting UGs excited about research is perhaps the first step to getting them excited to think about getting a PhD as a career option.

Is research by undergraduate students an oxymoron?
I will admit that initially I too was skeptical about the possibility and success of true undergraduate research. My own research experiences as an undergraduate were pathetic. As a student often I would hear people say “I am going to the library to do research”. So I too went to the library to do research. Research to me meant finding something in the library that was not in a textbook, understanding it, and telling people about the work.  At that point I thought I had done some research! I never gave much thought to how new material got into journals to begin with.

Talking to a colleague recently – he said “maybe what all UGs do in a chemistry lab is wash test tubes….”.  The truth is that I do not really know what UG research in chemistry looks like.  But the point I wanted to make with this article is that high level UG research in CS is entirely doable. Indeed, in theoretical computer science (TCS) we have witnessed brilliant papers in top conferences by undergraduate students, and I would argue that UG research can be done quite effectively in other areas of computing research as well.

So what should UG research in CS look like?
I have advised over 30 undergraduate researchers and based on my experiences, I have a few observations. Most successful research projects involving undergraduates require a lead time of about 18 months before graduation. It usually takes a few months for the student to read the relevant papers, and for us to identify a topic that aligns with the student’s interests and background. I usually expect that students would have taken both an undergraduate level class in algorithm design as well as discrete mathematics. If they can take a graduate level class, that would also be incredibly valuable.

Tips for shaping successful undergraduate research projects
Below is my process for defining a successful UG research project. UGs typically have 12-18 months for a research project, not 3-4 years like most Ph.D. students.

1. At my first meeting, I ask the students about the different topics they learned about in their Algorithms class and what appealed to them the most.
2. Using their answer from bullet #1, I usually spend some time thinking about the right topic for them to work on. The key here is that any paper that the student has to read should not have a long chain of preceding papers that will take them months to get to. Luckily many graph problems as well as combinatorial optimization and scheduling problems lend themselves to easy descriptions. So in a few minutes you can describe the problem.
3. The research should be on a topic of significant interest and related to things I have worked on, and one in which I have some intuition about the direction of research and conjectures that might be true and provable with elementary methods.
4. I usually treat undergraduates the same way as PhD students, while being aware that they have limited time (a year) as opposed to PhD students who might begin a vaguely defined research project.
5. Have them work jointly with a PhD student, if the research is close enough to the PhD students interests and expertise. It’s also a valuable mentoring experience for the PhD student. Simply having a couple of undergrads work on a project jointly can be motivating for both.
6. One benefit of tackling hard problems at this stage is that there is no downside. If a student does not make progress, in the worst case they read a few papers and learn some new things. This allows us to work on problems with less pressure than second and third year graduate students are under.

Over the last 25 years, I have had the opportunity to work with a very large number of talented undergraduates –from University of Maryland (UMD) and Northwestern  University, but also many via the NSF funded REU site program (REU CAAR) that  Bill Gasarch (UMD) and I co-ran from 2012-2018. Many of the students I advised, have published the work they did and subsequently received fellowships and admission to top Ph.D programs. Recent graduates are Elissa Redmiles (Ph.D. UMD), Frederic Koehler (Ph.D. MIT) and Riley Murray (Ph.D. Caltech).  I specifically wanted to mention An Zhu (Ph.D. Stanford University) who first opened my eyes to the amazing work that is possible by undergraduates.

About the Author
Samir Khuller received his M.S and Ph.D from Cornell University in 1989 and 1990, respectively, under the supervision of Vijay Vazirani. He was the first Elizabeth Stevinson Iribe Chair for CS at the University of Maryland. As chair he led the development of the Brendan Iribe Center for Computer Science and Innovation, a project completed in March 2019. In March 2019, Khuller joined Northwestern University as the Peter and Adrienne Barris Chair for CS.

His research interests are in graph algorithms, discrete optimization, and computational geometry. He has published about 200 journal and conference papers, and several book chapters on these topics. He served on the ESA Steering Committee from 2012-2016 and chaired the 2019 MAPSP Scheduling Workshop, and served on the program committee’s of many top conferences.  From 2018-2021 he was Chair of SIGACT. In 2020, he received the CRA-E Undergraduate Research Mentoring Award and in 2021 he was selected as a Fellow of EATCS.

He received the National Science Foundation’s Career Development Award, several Department Teaching Awards, the Dean’s Teaching Excellence Award and also a CTE-Lilly Teaching Fellowship. In 2003, he and his students were awarded the “Best newcomer paper” award for the ACM PODS Conference. He received the University of Maryland’s Distinguished Scholar Teacher Award in 2007, as well as a Google Research Award and an Amazon Research Award. In 2016, he received the European Symposium on Algorithms inaugural Test of Time Award for his work with Sudipto Guha on Connected Dominating Sets. He graduated at the top of the Computer Science Class from IIT-Kanpur.