Google University - Problem Set Exploring Algorithms

Problem Set* As a software engineer, it is important for you to develop a deep understanding of the algorithmic approaches presented in this module, and how and when to use them. In addition, software engineers and computer scientists require a working knowledge of common algorithms. In this problem set, you are given an opportunity to analyze a problem and apply these algorithmic approaches. 1. Write the most efficient algorithm you can think of for the following: Find the kth item in an n-node doubly-linked list. What is the running time in terms of bigtheta? 2. Write the most efficient algorithm you can think of for the following: Given a set of p points, find the pair closest to each other. Be sure and try a divide-andconquer approach, as well as others. What is the running time in terms of bigtheta? 3. Design and implement an algorithm that finds all the duplicates in a random sequence of integers. 4. Reconsider the three algorithms you just designed given the following change: the input has increased by 1,000,000,000 times. 5. You have two arrays of integers. Within each array, there are no duplicate values but there may be values in common with the other array. Assume the arrays represent two different sets. Define an O( n log n ) algorithm that outputs a third array representing the union of the two sets. The value "n" in O( n log n ) is the sum of the sizes of the two input arrays. 6. You are given an increasing sequence of numbers u1, u2, ... um, and a decreasing series of numbers d1, d2, ...dn. You are given one more number C and asked to determine if C can be written as the sum of one ui and one dj. There is an obvious brute force method, just comparing all the sums to C, but there is a much more efficient solution. Define an algorithm that works in linear time. 7. Design and implement a dynamic programming algorithm to solve the change counting problem. Your algorithm should always find the optimal solution--even when the greedy algorithm fails. 8. Joe has a factory with many interesting machines. His business is to create any kind of part anyone might need. Joe just lines up the machines in different sequences to stamp, cut metal, or drill holes. Joe's business has really picked up lately. Today, he has n jobs to complete (j1, j2, ..., jn). Each job (ji) takes a certain amount of time (ti), has a value (vi), and a deadline (di). Joe does not have enough machines to do more than one job at a time, so each job must run uninterrupted for ti time. If job ji is completed by its deadline di, Joe makes money vi. If he does not make the deadline, he does not get paid at all. This is way too complicated for Joe to deal with, so he has asked you to design an algorithm to determine the "best" schedule, that being the one where he makes the

most money. To simplify things, assume all the processing times are integers between 1 and n. Determine the running time of your algorithm. 9. The knapsack problem comes up when there is resource allocation with various constraints. For example, given a fixed budget, how do you select what things you should buy? Everything has a cost and value, so we want the most value for a given cost. The term "knapsack problem" invokes the image of the backpacker who is constrained by a fixed-size knapsack and must fill it only with the most useful items. A typical form is the 0/1 knapsack problem, where each item must be put entirely in the knapsack or not included at all. Objects cannot be broken in pieces arbitrarily. This 0/1 property makes the knapsack problem difficult. It's easy to find a greedy algorithm for the optimal selection when we are allowed to break objects up. For each item, we could compute its "price per pound", and take as much of the most expensive item until we have it all or the knapsack is full. Then do the same with the next most expensive item, etc., until the knapsack is full. Unfortunately, the 0/1 constraint is usually a requirement. So let’s say you are a thief with a knapsack of a certain capacity. You look around the place you just broke into and see items of different weights and values. You would like the items you choose for your knapsack to have the greatest value possible yet still fit in the knapsack. This is the 0-1 Knapsack Problem because you, the thief, can either take (1) or leave (0) each item. Given a set of items, each with a cost and a value, determine the number of each item to include in a collection so that the total cost is less than some given cost and the total value is as large as possible. The 0/1 knapsack problem restricts the number of each items to zero or one. We must: Maximize sum(include_item(i) * value(i)) where include_item(i) = 0 or 1 Subject to sum(include_item(i) * weight(i)) <= C There are several greedy approaches to try: o

o

o

Greedy by Profit: At each step select from the remaining items the one with the highest profit. This approach tries to maximize the profit by choosing the most profitable items first. Greedy by Weight: At each step select from the remaining items the one with the least weight. This approach tries to maximize the profit by putting as many items into the knapsack as possible. Greedy by Profit Density: At each step select from the remaining items the one with the largest profit density, that is, pi/wi. This approach tries to

maximize the profit by choosing items with the largest profit per unit of weight. Design an algorithm to solve this problem for a small set of data. Assume five items of weights 20, 50, 40, 10, 30 with values 15, 20, 5, 25, 10 respectively. Test various greedy approaches and heuristics to see if you can find the optimal solution to this instance. Then, once you have defined your algorithm, test it on larger and larger data sets to see how it performs. 10. Determine the best way to solve TSP given the following requirements: o There are 20 stops to make and we are to visit each exactly once. o Each time we have to make a tour, the stops (and distances) change. o Near-optimal is fine - we do not require an optimal solution, but we do need good solutions because of the costs involved in bad ones. Start by implementing the nearest neighbor algorithm with a specific set of data that you create. For the purposes of this problem, assume each stop is connected to every other stop, so we don't have to worry about finding a tour - we just have to find the tour with the shortest total distance. A common way to store the distance information is in a 2-D array with n rows and n columns. Then, enhance it with the all-city nearest neighbor, described at the bottom of the first lesson in this module (on brute force, greedy and heuristics). Finally, apply the heuristic of letting each city be a starting city. Compare the running times for each on just this set of data. Then try your three solutions on a completely different set of data and compare the results. Try ten more different sets and compare. Which algorithm performs the best?

* Except as otherwise noted, the content of this presentation is licensed under the Creative Commons Attribution 2.5 License.