The Summer 2024 application has closed. The Summer 2025 application will open in early 2025.

Program

The Montana State University Algorithms Research Experience for Undergraduates (REU) is a ten-week residential program in the summer of 2024 that focuses on collaborative algorithm development and problem solving for topics in the broad themes of optimization and sustainability with specific topics including computational biology, computational geometry and topology, graph optimization algorithms, machine learning, and cybersecurity. Participants will work with each other and faculty members to develop their research skills and work to solve novel problems.

Program Details:
  • May 28 - August 2 (10 weeks)
  • $7,000 stipend
  • Travel alowance
  • $120 per week food allowance
  • Free on-campus housing
  • Social activities

Application

Applications for the summer of 2024 are currently being accepted. Applications will be accepted until April 15th, 2024, with acceptance decisions being made on a rolling basis. We strongly encourage American Indian students to apply. Please indicate in your application materials if you belong to a federally recognized tribe.

Participant Requirements:
  • NSF requires applicants to be citizens or permanent residents of the United States.
  • Applicants must be undergraduate students in good standing.
  • Applicants must have completed a course in Algorithms and programming.
Applications can be submitted online via the NSF's ETAP system by following this link: NSF ETAP. The following applications material are required:
  • Undergraduate transcript (unofficial is ok)
  • One letter of recommendation from college professor/instructor
  • Personal statement detailing:
    • Your interest in the program
    • Career aspirations
    • The (ranked) top three projects discussed below you are interested in working on.

Location

Montana State University is located in the beautiful town of Bozeman, Montana. As the epicenter of the Northern Rocky Mountains, there are endless outdoor activities on your doorstep including access to Yellowstone National Park a mere 80 miles away. Bozeman also hosts many community events in the summer that are easily accessible from campus including Shakespeare in the park, music on Main Street, and farmer's markets. Montana State University hosts many high-tech laboratory and comfortable work spaces with diverse summer dining options.

Projects

Participants in this program will partake in organized seminars and workshops to aid the development of their research skills. The cornerstone of the program is working on a project with another participant, with close mentoring from a faculty member. These projects will be centered on applied algorithms, but the application fields are quite diverse. Possible projects include:

Network Optimization

This project will develop novel network optimization techniques to help design viable CO2 capture and storage (CCS) infrastructure. CCS is a critical tool for mitigating climate change and needs to be widely deployed in the very near future by many industries. Designing massive CCS infrastructure is a complicated network optimization problem that requires careful and comprehensive planning to ensure decisions are made in a cost-effective manner. Other fundamental graph problems such as the fixed-charge network flow problem and the facility location problem may be explored as well.

Computational Geometry

Geometric and Combinatorial Optimization problems occur in various applications, for instance, how to schedule some drones to cover a specific region of interest. In the previous year, we finished an REU project "Guarding precise and imprecise polyhedral terrains with segments" which has already been published. This year, we hope to continue this thread in a similar manner. In Combinatorial Optimization, we are also interested in fundamental string problems originated from applications, for instance, variants of the Longest Common Subsequence problem, etc. Students participated are supposed to be involved in designing algorithms as well as in implementations.

Graph Problems in Computational Biology

The assembly of full RNA and DNA sequences from short sequence data is a fundamental computational problem in biology. A highly successful approach to addressing assembly problems has been to express them abstractly in terms of computational problems on graphs, such as finding a minimum path cover or decomposing flow in a network. A recent problem of interest is to determine what viral strains are present in a sample (e.g. Covid or the flu). This project will look at some new approaches using graphs and new algorithms to tackle this and related problems.

Computational Topology

Topological data analysis (TDA) tries to find structure and shape in data. We'll study data sets where using persistence diagrams (a fundamental tool in TDA) can be used for classification. Then, we will investigate how to simplify the diagrams to obtain reasonably similar classification results.

Malware and Vulnerability Analysis

This project will develop data visualization-assisted techniques aimed at addressing challenges in malware analysis and vulnerability analysis across various architectures, compilers, and optimizations. Our approach emphasizes robust theoretical guarantees and high-performance outcomes. To achieve the objectives, we will utilize binary analysis and context-sensitive feature engineering to capture the crucial semantics of program execution and subsequently quantify these semantics through data visualization. Our methodology involves the formalization of hidden structures within the data, followed by the design of efficient algorithms. These algorithms leverage techniques such as non-convex optimization and tensor decomposition to effectively group the artifacts of programs.\

Optimal Factor Architectures for Factored Evolutionary Algorithms

Recent work in cooperative coevolutionary algorithms has focused on distributing subpopulations of problem spaces when solving complex optimization problems. Historically, these approaches assume the subpopulations are disjoint and only interact by way of a global context. The development of Factored Evolutionary Algorithms (FEA) at MSU has extended the cooperative coevolutionary method to allow for overlap among the subpopulations (called factors) and has been designed to work with virtually any stochastic search method (e.g., simulated annealing, genetic algorithms, or particle swarm optimization). This enables cooperative coevolution to run in a distributed setting without requiring the global context information and even allows a mix of optimization methods to be applied. The primary challenge with the FEA approach, however, is in the determination of the appropriate factor architecture (i.e., the best set of subproblems/subpopulations) for efficient and effective optimization. This project will take a closer look at determining factor architectures, taking ideas from feature extraction methods such as principal component analysis and autoencoders.

Contact Information

  • Dr. Sean Yaw, Program Director, sean.yaw@montana.edu
  • Dr. Brendan Mumey, Program Co-director, brendan.mumey@montana.edu
  • Dr. Binhai Zhu, Program Co-director, bhz@montana.edu