As students begin to plan their summer agendas, Horizon Academic is excited to bring high schoolers a new research opportunity: Algorithms & Data Structures. Offered as part of our Seminar track and strictly available during summer terms, this course will be led by Georgia Tech’s longtime professor Guillermo Goldsztein.
With over 2 decades of teaching experience, Dr. Goldsztein carefully designed the class curriculum to focus on efficient algorithm design, something which allows smaller and less complex devices like wearables to do tasks that once required powerful processors and which has brought down the cost of life-saving research like genomic sequencing from billions to only hundreds of dollars.
Breaking apart the Python programming language into its individual parts, algorithms can be best defined as sets of instructions that execute tasks. The task may seem as simple as sorting alphabetically a set of words, or complex such as the reconstruction of genomes from biochemical experiments or the encryption of sensitive data for safety purposes. There are several algorithms to accomplish the same task, but some algorithms are more efficient than others. The efficiency of an algorithm depends on the number of operations and the memory space required for its execution. If an algorithm is not efficient, it may require so much time or memory to execute that it becomes useless. As for data structures, they refer to how the data is represented. Data structures go hand-in-hand with algorithms. Different algorithms may require different data structures
Students can expect to walk away from this course having better understand the mechanics of how real-world computer programs work and how to develop their own programs in Python. Given its scope, the Algorithm & Data Structures course is best suited for students who enjoy computer science, mathematics, and what lies at their crossroads.
High schoolers are welcome to pursue any of the following pre-approved topics or propose their own research focus:
1. Given an unsorted integer array, find a pair with the given sum in it.
2. Finding the longest subsequence present in two given sequences in the same order, i.e., find the longest sequence which can be obtained from the first original sequence by deleting some items and from the second original sequence by deleting other items.
3. Given an integer array, find a contiguous subarray within it that has the largest sum.
4. Given an unlimited supply of coins of given denominations, find the total number of distinct ways to get the desired change.
5. We are given a set of items, each with a weight and a value, and we need to determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
6. Given a set of positive integers and an integer k, check if there is any non-empty subset that sums to k.
7. The Longest Palindromic Subsequence (LPS) problem is finding the longest subsequences of a string that is also a palindrome.
8. Matrix chain multiplication problem: Determine the optimal parenthesization of a product of n matrices.
9. The longest common substring problem is the problem of finding the longest string (or strings) that is a substring (or are substrings) of two strings.
10. Given a rod of length n and a list of rod prices of length i, where 1 <= i <= n, find the optimal way to cut the rod into smaller rods to maximize profit.
11. Word Break Problem: Given a string and a dictionary of words, determine if the string can be segmented into a space-separated sequence of one or more dictionary words.
12. The Levenshtein distance between two words is the minimum number of single-character edits (i.e., insertions, deletions, or substitutions) required to change one word into the other. Each of these operations has a unit cost. Develop an algorithm to compute the Levenshtein distance between two words.
13. Given a chessboard, find the shortest distance (minimum number of steps) taken by a knight to reach a given destination from a given source.
14. Given a set of positive integers, check if it can be divided into two subsets with equal sum.
15. 3-partition problem: Given a set S of positive integers, determine if it can be partitioned into three disjoint subsets that all have the same sum, and they cover S.
16. Find the minimum number of throws required to win a given Snakes and Ladders board game.
17. Given an integer array, find the largest subarray formed by consecutive integers. The subarray should contain all distinct values.
18. Given an array containing only 0’s, 1’s, and 2’s, sort it in linear time and using constant space.
19. Given a chessboard, print all sequences of moves of a knight on a chessboard such that the knight visits every square only once.
20. Given an N × N matrix of integers, find the maximum sum submatrix present in it.
21. Given a string, find the maximum length contiguous substring of it that is also a palindrome. For example, the longest palindromic substring of “bananas” is “anana”, and the longest palindromic substring of “abdcbcdbdcbbc” is “bdcbcdb”.
22. Given a list of tasks with deadlines and total profit earned on completing a task, find the maximum profit earned by executing the tasks within the specified deadlines. Assume that each task takes one unit of time to complete, and a task can’t execute beyond its deadline. Also, only a single task will be executed at a time.
23. The N–queens puzzle is the problem of placing N chess queens on an N × N chessboard so that no two queens threaten each other. Thus, the solution requires that no two queens share the same row, column, or diagonal.
24. Given an integer array, find the subarray that has the maximum product of its elements. The solution should return the maximum product of elements among all possible subarrays.
25. The Longest Repeating Subsequence (LRS) problem is finding the longest subsequences of a string that occurs at least twice.
26. Given an unsorted integer array, find a triplet with a given sum in it.
27. The Shortest Common Supersequence (SCS) is finding the shortest supersequence Z of given sequences X and Y such that both X and Y are subsequences of Z.
28. Given an array containing positive and negative elements, find a subarray with alternating positive and negative elements, and in which the subarray is as long as possible.
29. 4-sum problem: Given an unsorted integer array, check if it contains four elements tuple (quadruplets) having a given sum.
30. In the k–partition problem, we need to partition an array of positive integers into k disjoint subsets that all have an equal sum, and they completely cover the set.
31. Given a set of positive integers S, partition set S into two subsets, S1 and S2, such that the difference between the sum of elements in S1 and S2 is minimized. The solution should return the minimum absolute difference between the sum of elements of two partitions.
32. Wildcard Pattern Matching: Given a string and a pattern containing wildcard characters, i.e., * and ?, where ? can match to any single character in the string and * can match to any number of characters including zero characters, design an efficient algorithm to check if the pattern matches with the complete string or not.
33. Consider an event where a log register is maintained containing the guest’s arrival and departure times. Given an array of arrival and departure times from entries in the log register, find the point when there were maximum guests present in the event.
34. Graph coloring (also called vertex coloring) is a way of coloring a graph’s vertices such that no two adjacent vertices share the same color. This post will discuss a greedy algorithm for graph coloring and minimize the total number of colors used.
35. The Longest Increasing Subsequence (LIS) problem is to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous or unique.
36. There are two players, A and B, in Pots of gold game, and pots of gold arranged in a line, each containing some gold coins. The players can see how many coins are there in each gold pot, and each player gets alternating turns in which the player can pick a pot from either end of the line. The winner is the player who has a higher number of coins at the end. The objective is to “maximize” the number of coins collected by A, assuming B also plays “optimally”, and A starts the game.
37. Activity Selection Problem: Given a set of activities, along with the starting and finishing time of each activity, find the maximum number of activities performed by a single person assuming that a person can only work on a single activity at a time.
38. The longest alternating subsequence is a problem of finding a subsequence of a given sequence in which the elements are in alternating order and in which the sequence is as long as possible. In order words, we need to find the length of the longest subsequence with alternate low and high elements.
39. Given an integer array, find the length of the longest subsequence formed by the consecutive integers. The subsequence should contain all distinct values, and the character set should be consecutive, irrespective of its order.
40. Trapping rainwater problem: Find the maximum amount of water that can be trapped within a given set of bars where each bar’s width is 1 unit.
41. Given a list of jobs where each job has a start and finish time, and has profit associated with it, find a maximum profit subset of non-overlapping jobs.
42. The Longest Bitonic Subarray (LBS) problem is to find a subarray of a given sequence in which the subarray’s elements are first sorted in increasing order, then in decreasing order, and the subarray is as long as possible. Strictly ascending or descending subarrays are also accepted.
43. Suppose we are given n red and n blue water jugs, all of different shapes and sizes. All red jugs hold different amounts of water, as do the blue ones. Moreover, there is a blue jug for every red jug that holds the same amount of water and vice versa. The task is to efficiently group the jugs into pairs of red and blue jugs that hold the same amount of water. (Problem Source: CLRS)
44. Given a positive number n, find the total number of ways in which n hats can be returned to n people such that no hat makes it back to its owner.
45. Given a set of intervals, print all non-overlapping intervals after merging the overlapping intervals.
46. Write an efficient algorithm to find the longest common prefix (LCP) between a given set of strings.
47. Given a rod of length n, find the optimal way to cut the rod into smaller rods to maximize the product of each of the smaller rod’s price. Assume that each rod of length i has price i.
48. Given a set of rectangular 3D boxes (cuboids), create a stack of boxes as tall as possible and return the maximum height of the stacked boxes.
49. Given an integer array, find the maximum product of its elements among all its subsets.
50. Given a binary tree, find the size of the Maximum Independent Set (MIS) in it.
Additional topics available for students interested in projects with a higher level of difficulty include:
1. Applications of number theory and cryptography: Learn and implement in Python the RSA algorithm.
2. Applications in bioinformatics: Learn and implement in Python the algorithm used to reconstruct genomes.