algorithm assignment

If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

To log in and use all the features of Khan Academy, please enable JavaScript in your browser.

AP®︎/College Computer Science Principles

Course: ap®︎/college computer science principles   >   unit 4, the building blocks of algorithms.

• Expressing an algorithm

Want to join the conversation?

• Upvote Button navigates to signup page
• Downvote Button navigates to signup page
• Flag Button navigates to signup page

Algorithms, 4th Edition

Online content. , textbook. , for teachers:, for students:.

FIT 100 Assignment 3

Algorithms:   Writing the perfect instructions [1]

Introduction

Before we proceed to programming computers, we need to prepare ourselves by learning how to think about programming.   At the heart of programming is the algorithm , basically a very carefully expressed problem-solving strategy , usually in the form of a structured set of instructions.   We say we “use” or “apply” an algorithm to solve the problem it was designed for.   In everyday life, when we think of instructions, we mean instructions for other people to follow, rather than a machine, and we can conveniently make many unstated assumptions and get away with being ambiguous.   Unlike instructions for people, instructions for computers can leave no room for misinterpretation, so algorithms require an extreme level of precision that will take some getting used to.   Following the guidelines discussed in Chapter 10, in this assignment, we will exercise our algorithmic thinking on a wide variety of problems, ranging from everyday tasks to mathematical problems.

·     concepts

1.       algorithm

2.       input, output

3.       degree of precision required in an algorithm

4.       control flow

5.       conditional

6.       iteration

·     skills

1.       writing an algorithm, given a properly specified problem statement

2.       identifying examples of conditionals and iteration in algorithms

·     Chapter 10:   Algorithmic Thinking

Required Resources

No computers are required.   This assignment consists entirely of written exercises.

All key vocabulary terms used in this assignment are listed below, with closely related words listed together:

algorithm , program control flow conditional, condition iteration, looping, loop condition

Discussion and Procedure

You will be writing algorithms for one kind of problem in this assignment.   However, there are more points possible for tackling an algorithm listed in Part 2 or 3.   No matter which problem you choose for writing an algorithm, remember to answer the 2 questions at the end of the assignment as well.

In Part 1 there are algorithm for completing an everyday task like doing laundry or making a sandwich.   In Part 2, there are options to write algorithms for special everyday tasks carefully chosen to have strong similarities to mathematical or computing problems.   For example, locating a word’s definition in a dictionary is an example of a “search problem,” using computer science terminology.   (Chapter 10’s CD rack sorting example also falls into this category.)   Finally, in Part 3 there are problems that are explicitly mathematical or computational in nature (e.g., finding the average of a large set of numbers).   You are instructed to choose one problem from one of these three groups and write an algorithm.   For whatever single algorithm you write, make sure to follow the following instructions:

Instructions for Writing Algorithms

For each problem stated, write a carefully worded and structured set of instructions for solving the problem.   Just as in the example algorithm in Chapter 10 (for sorting a CD rack), include the following sections, described in detail:

·     inputs or start state, including a list of required materials, if applicable (This might seem obvious for physical tasks like preparing a sandwich.   However, even for mathematical problems, you might want to note which quantities you want to keep track of.)

·     outputs or end result(s)

·     numbered steps

Always keep conscious of the assumptions you are making by writing them down explicitly.   You should adhere to the guidelines discussed in Chapter 10 and follow the format shown in the sample solution below.   (See the CD rack sorting example in Chapter 10 for a more extended example.)

Remember, there is no one right answer .   Many different algorithms might be acceptable for each problem.   Due to the flexibility of the English language, the same algorithm can often be expressed in more than one way.   In addition, there is almost always more than one way to solve a problem.   They might differ in their complexity, time required, and other aspects, which are important differences to consider, but they can all be valid algorithms for the problem.

Finally, both as you write and after you are finished, check your algorithm to make sure it satisfies all of the properties discussed at the beginning of Chapter 10. We have summarized them here in the form of questions you can ask yourself to check your algorithm:

1.              Inputs specified.   Do you precisely describe all of the data (or materials) needed for the algorithm?

2.              Outputs specified.   Do you precisely describe the results of your algorithm?   Your outputs description should clearly state what the algorithm is supposed to do and solve the problem the algorithm is designed for.

3.              Definiteness.   As discussed earlier, an algorithm must be expressed very precisely.   An ambiguous algorithm, if misinterpreted, might be ineffective at solving the problem it was designed for.   It is easy to get carried away, however, and include details that are not essential to the algorithm’s correctness.    Ask yourself the following as you write:   Is this detail essential to the algorithm’s correctness?   Does it add important information that is not evident from what you have already written?   Include the detail if you answer, “yes,” to these questions.

4.              Effectiveness.   Are the required resources (whether they be information or the ability to do certain things) realistic and reasonable?   For instance, an algorithm for converting a temperature from degrees Fahrenheit to Celsius that relies on looking up the temperature in a Fahrenheit-Celsius conversion table is hardly interesting or useful.

5.              Finiteness.   Are you sure that the algorithm actually finishes?   For instance, one algorithm for finding a specific playing card in a deck is to repeat the following:   Shuffle the deck and check the top card.   Strictly speaking, the card you are looking for might never end up at the top of the deck, no matter how many times you reshuffle.   (That would be pretty rotten luck, but it is possible.)   In contrast, checking the whole deck, one card at a time, while time-consuming, is an algorithm that is guaranteed to finish.   At worst, your card would end up being the last one you check.

Before we begin, we will go through a simple example.   Notice that each problem statement in this assignment is very carefully stated, with as many details and as few implicit assumptions as possible.   This is no accident.   It is only reasonable that a detailed and precise algorithm requires an equally carefully stated problem.

Example problem :   Given a VCR, TV, and videotape of twelve episodes of your favorite television show, each 30 minutes long, find a specified episode and cue the tape to the start of the episode.   For instance, suppose you have already seen all but one of the episodes, but you are not sure where the one episode is on the tape.   Your objective is to find this episode on the tape.   Assume that the TV and VCR are both on, and that the tape is in the VCR, cued to an unknown location (i.e., not necessarily rewound).

Example algorithm .  

START STATE :   videotape of twelve 30 min. episodes, VCR, TV with assumptions as stated in problem above; ability to recognize one specific episode

END RESULT:   videotape cued to beginning of specified episode

ASSUMPTIONS:  

o         VCR has tape counter that shows tape position in hours and minutes.

o         Episodes begin at 30 min. multiples, i.e., the first episode is at time 0:00, the second at 0:30, the third at 1:00 , etc.   There is no other video recorded on the tape between episodes.

1)      Rewind tape to start.

2)      Reset tape counter.

3)      Play tape for a few minutes to check whether the episode is the one you are looking for.   If so, proceed to Step 5; otherwise, proceed to Step 4.

4)      Stop play, and fast forward the tape.   Watch the counter for the next 30 min. multiple, and press stop when the tape reaches that point, which should be the start of the next episode on the tape.   For example, if you stopped the tape at 2:04 (two hours, four minutes), fast forward until the counter reads 2:30 .   Go to Step 3.

5)      Stop play, and rewind to the previous 30 min. multiple using the tape counter.   For example, if you recognize the episode you are looking for and the counter reads 3:32 (three hours, 32 minutes), rewind to 3:30 .

Part 1.       Algorithms for Everyday Problems   [worth 8 points- the assignment minimum]

important advice :   Do not assume that problems in this part will be easy just because the procedures for these tasks might be second nature to you.   In fact, the more familiar you are with a task, the more likely it is that you will make implicit assumptions and skip details in your algorithm.

Choose ONE of the problems below and write an algorithm to solve it.   Assume a reasonably equipped kitchen as the context.

1a-1.   Prepare a bowl of cold cereal.   You may choose to include fruit or other ingredients beyond cereal and milk, but make sure to state them explicitly.   Assume that a carton of milk is in the refrigerator.

1a-2.   Prepare a sandwich.   Make sure to state what kind of sandwich you are making and what ingredients and utensils are required.   Again, assume all required ingredients are in the kitchen, refrigerated if needed.

1a-3.   Prepare a cup of tea using a tea bag.   You may describe adding cream, sugar, lemon, honey, etc., but mention these ingredients in your write-up.

Each of the following everyday problems involves repeating some steps in the procedure (just as Step 4 in the above example can be repeated).  

1b-1.   Given a pile of pens, find and discard the ones that do not write any more.

1b-2.   Suppose you are told that your favorite movie is on television right now, but you are not sure which channel it is on.   Without the use of a program guide (that is, without using things like TV Guide or the newspaper program listings), find the channel broadcasting the movie.   Assume, of course, that you could recognize any part of the movie if you saw it.

1b-3.   Brush your teeth.

1b-4.   Wash and dry a load of laundry using coin operated washing machine and dryer.

Part 2.       Algorithms for Computational Everyday Problems [worth up to 12 points]

The problems in this section are real-life versions of computational problems.  

2-1.       Given two words, determine which would come first in alphabetical order.   Do not use a dictionary or other reference book.

2-2.       Given a bag full of cherries, determine whether you could split them evenly among seven people (so that each person has the same number of cherries and none are left over).   The result is a yes or no answer.

2-3.       Given a restaurant check subtotal (before tax) and total (after tax), calculate how much you should leave for a 15% tip.

2-4.       Given fifty apples and a two-pan balance (which can determine whether two items have the same weight), determine which two (if any) have the same weight (have weight close enough that the balance measures them as being equal).

Part 3.       Algorithms for Computational Problems [worth up to 15 points]

Problems in this section are obviously computational, involving computing mathematically interesting results.   They are fundamentally different from the problems in the previous two parts of the assignment in that they involve no physical process.   That is, these problems involve manipulating numbers rather than physical objects like foods, pens, or laundry detergent.  

3-1.       Given a set of 20 numbers, compute the average of the numbers.

3-2.       Given a set of 100 numbers, find the largest and smallest numbers in the set.

Part 4.       Recognizing Control Flow Patterns

Some algorithms are very simple, and applying them just involves proceeding from one step to the next (sequential execution).   We have already seen examples of algorithms, however, which involve skipping ahead to a later step or repeating an earlier step, depending on certain conditions.   Control flow is the programming term used to describe the order in which the steps are executed, and we will discuss two common ways control flow diverges from simple, sequential execution.   In the Post-Assignment Questions, you are asked to examine the algorithms you wrote and identify at least one example of each of these control flow patterns.

Conditionals:   The keyword is “if.”   A conditional (also known as a branch ) is when control flow reaches a point where it can proceed to one of two (or more) alternatives.   The condition is what determines which step to proceed to.   For example, to round off a number to its nearest integer, you first need to check the following condition:   whether the fractional part is less than 0.5.   If so, the result is just the integer part; otherwise, you add one to the integer part.   Use of the phrase structure “if…then…” and instructions to skip ahead/back to other steps in an algorithm are hallmarks of the conditional.

Iteration:   Controlled repetition.   Iteration is basically the repetition of one or more steps in an algorithm.   Iteration is related to the conditional in that the number of times you do the repetition is usually controlled by a condition.   Iteration is also called looping and the condition is accordingly called the loop condition .   The video searching example algorithm at the start of this assignment has a loop in Steps 3-4, where the conditional in Step 3 (checking whether the episode is the one you are looking for) determines whether you repeat Step 4’s fast-forwarding.

Understanding the concepts of control flow and the two standard patterns of the conditional and iteration will help you a great deal as you proceed to expressing algorithms in a programming language.

Post-Assignment Questions

Write your answers after completing the main part of the assignment:

1.       Identify one example of iteration in the algorithm you wrote for this assignment.   Explain which steps are being repeated and what determines when the repetition stops.   It is possible that you did not use iteration for your algorithm: if that is the case, then say so-but be VERY SURE that it is the case!

2.       Identify at least one example of a conditional in the algorithm you wrote for this assignment. It is possible that you did not use iteration for your algorithm: if that is the case, then say so-but be VERY SURE that it is the case!

[1] Algorithms exercise written by Ken Yasuhara .   Edited by Grace Beauchane Whiteaker

Forgot password? New user? Sign up

Existing user? Log in

Hungarian Maximum Matching Algorithm

Already have an account? Log in here.

The Hungarian matching algorithm , also called the Kuhn-Munkres algorithm, is a \(O\big(|V|^3\big)\) algorithm that can be used to find maximum-weight matchings in bipartite graphs , which is sometimes called the assignment problem . A bipartite graph can easily be represented by an adjacency matrix , where the weights of edges are the entries. Thinking about the graph in terms of an adjacency matrix is useful for the Hungarian algorithm.

A matching corresponds to a choice of 1s in the adjacency matrix, with at most one 1 in each row and in each column.

The Hungarian algorithm solves the following problem:

In a complete bipartite graph \(G\), find the maximum-weight matching. (Recall that a maximum-weight matching is also a perfect matching.)

This can also be adapted to find the minimum-weight matching.

Say you are having a party and you want a musician to perform, a chef to prepare food, and a cleaning service to help clean up after the party. There are three companies that provide each of these three services, but one company can only provide one service at a time (i.e. Company B cannot provide both the cleaners and the chef). You are deciding which company you should purchase each service from in order to minimize the cost of the party. You realize that is an example of the assignment problem, and set out to make a graph out of the following information: \(\quad\) Company\(\quad\) \(\quad\) Cost for Musician\(\quad\) \(\quad\) Cost for Chef\(\quad\) \(\quad\) Cost for Cleaners\(\quad\) \(\quad\) Company A\(\quad\) \(\quad\) $108\(\quad\) \(\quad\) $125\(\quad\) \(\quad\) $150\(\quad\) \(\quad\) Company B\(\quad\) \(\quad\) $150\(\quad\) \(\quad\) $135\(\quad\) \(\quad\) $175\(\quad\) \(\quad\) Company C\(\quad\) \(\quad\) $122\(\quad\) \(\quad\) $148\(\quad\) \(\quad\) $250\(\quad\) Can you model this table as a graph? What are the nodes? What are the edges? Show Answer The nodes are the companies and the services. The edges are weighted by the price.

What are some ways to solve the problem above? Since the table above can be thought of as a \(3 \times 3\) matrix, one could certainly solve this problem using brute force, checking every combination and seeing what yields the lowest price. However, there are \(n!\) combinations to check, and for large \(n\), this method becomes very inefficient very quickly.

The Hungarian Algorithm Using an Adjacency Matrix

The hungarian algorithm using a graph.

With the cost matrix from the example above in mind, the Hungarian algorithm operates on this key idea: if a number is added to or subtracted from all of the entries of any one row or column of a cost matrix, then an optimal assignment for the resulting cost matrix is also an optimal assignment for the original cost matrix.

The Hungarian Method [1] Subtract the smallest entry in each row from all the other entries in the row. This will make the smallest entry in the row now equal to 0. Subtract the smallest entry in each column from all the other entries in the column. This will make the smallest entry in the column now equal to 0. Draw lines through the row and columns that have the 0 entries such that the fewest lines possible are drawn. If there are \(n\) lines drawn, an optimal assignment of zeros is possible and the algorithm is finished. If the number of lines is less than \(n\), then the optimal number of zeroes is not yet reached. Go to the next step. Find the smallest entry not covered by any line. Subtract this entry from each row that isn’t crossed out, and then add it to each column that is crossed out. Then, go back to Step 3.

Solve for the optimal solution for the example in the introduction using the Hungarian algorithm described above. Here is the initial adjacency matrix: Subtract the smallest value in each row from the other values in the row: Now, subtract the smallest value in each column from all other values in the column: Draw lines through the row and columns that have the 0 entries such that the fewest possible lines are drawn: There are 2 lines drawn, and 2 is less than 3, so there is not yet the optimal number of zeroes. Find the smallest entry not covered by any line. Subtract this entry from each row that isn’t crossed out, and then add it to each column that is crossed out. Then, go back to Step 3. 2 is the smallest entry. First, subtract from the uncovered rows: Now add to the covered columns: Now go back to step 3, drawing lines through the rows and columns that have 0 entries: There are 3 lines (which is \(n\)), so we are done. The assignment will be where the 0's are in the matrix such that only one 0 per row and column is part of the assignment. Replace the original values: The Hungarian algorithm tells us that it is cheapest to go with the musician from company C, the chef from company B, and the cleaners from company A. We can verify this by brute force. 108 + 135 + 250 = 493 108 + 148 + 175 = 431 150 + 125 + 250 = 525 150 + 148 + 150 = 448 122 + 125 + 175 = 422 122 + 135 + 150 = 407. We can see that 407 is the lowest price and matches the assignment the Hungarian algorithm determined. \(_\square\)

The Hungarian algorithm can also be executed by manipulating the weights of the bipartite graph in order to find a stable, maximum (or minimum) weight matching. This can be done by finding a feasible labeling of a graph that is perfectly matched, where a perfect matching is denoted as every vertex having exactly one edge of the matching.

How do we know that this creates a maximum-weight matching?

A feasible labeling on a perfect match returns a maximum-weighted matching. Suppose each edge \(e\) in the graph \(G\) connects two vertices, and every vertex \(v\) is covered exactly once. With this, we have the following inequality: \[w(M’) = \sum_{e\ \epsilon\ E} w(e) \leq \sum_{e\ \epsilon\ E } \big(l(e_x) + l(e_y)\big) = \sum_{v\ \epsilon\ V} l(v),\] where \(M’\) is any perfect matching in \(G\) created by a random assignment of vertices, and \(l(x)\) is a numeric label to node \(x\). This means that \(\sum_{v\ \epsilon\ V}\ l(v)\) is an upper bound on the cost of any perfect matching. Now let \(M\) be a perfect match in \(G\), then \[w(M) = \sum_{e\ \epsilon\ E} w(e) = \sum_{v\ \epsilon\ V}\ l(v).\] So \(w(M’) \leq w(M)\) and \(M\) is optimal. \(_\square\)

Start the algorithm by assigning any weight to each individual node in order to form a feasible labeling of the graph \(G\). This labeling will be improved upon by finding augmenting paths for the assignment until the optimal one is found.

A feasible labeling is a labeling such that

\(l(x) + l(y) \geq w(x,y)\ \forall x \in X, y \in Y\), where \(X\) is the set of nodes on one side of the bipartite graph, \(Y\) is the other set of nodes, \(l(x)\) is the label of \(x\), etc., and \(w(x,y)\) is the weight of the edge between \(x\) and \(y\).

A simple feasible labeling is just to label a node with the number of the largest weight from an edge going into the node. This is certain to be a feasible labeling because if \(A\) is a node connected to \(B\), the label of \(A\) plus the label of \(B\) is greater than or equal to the weight \(w(x,y)\) for all \(y\) and \(x\).

A feasible labeling of nodes, where labels are in red [2] .

Imagine there are four soccer players and each can play a few positions in the field. The team manager has quantified their skill level playing each position to make assignments easier.

How can players be assigned to positions in order to maximize the amount of skill points they provide?

The algorithm starts by labeling all nodes on one side of the graph with the maximum weight. This can be done by finding the maximum-weighted edge and labeling the adjacent node with it. Additionally, match the graph with those edges. If a node has two maximum edges, don’t connect them.

Although Eva is the best suited to play defense, she can't play defense and mid at the same time!

If the matching is perfect, the algorithm is done as there is a perfect matching of maximum weights. Otherwise, there will be two nodes that are not connected to any other node, like Tom and Defense. If this is the case, begin iterating.

Improve the labeling by finding the non-zero label vertex without a match, and try to find the best assignment for it. Formally, the Hungarian matching algorithm can be executed as defined below:

The Hungarian Algorithm for Graphs [3] Given: the labeling \(l\), an equality graph \(G_l = (V, E_l)\), an initial matching \(M\) in \(G_l\), and an unmatched vertex \(u \in V\) and \(u \notin M\) Augmenting the matching A path is augmenting for \(M\) in \(G_l\) if it alternates between edges in the matching and edges not in the matching, and the first and last vertices are free vertices , or unmatched, in \(M\). We will keep track of a candidate augmenting path starting at the vertex \(u\). If the algorithm finds an unmatched vertex \(v\), add on to the existing augmenting path \(p\) by adding the \(u\) to \(v\) segment. Flip the matching by replacing the edges in \(M\) with the edges in the augmenting path that are not in \(M\) \((\)in other words, the edges in \(E_l - M).\) Improving the labeling \(S \subseteq X\) and \(T \subseteq Y,\) where \(S\) and \(T\) represent the candidate augmenting alternating path between the matching and the edges not in the matching. Let \(N_l(S)\) be the neighbors to each node that is in \(S\) along edges in \(E_l\) such that \(N_l(S) = \{v|\forall u \in S: (u,v) \in E_l\}\). If \(N_l(S) = T\), then we cannot increase the size of the alternating path (and therefore can't further augment), so we need to improve the labeling. Let \(\delta_l\) be the minimum of \(l(u) + l(v) - w(u,v)\) over all of the \(u \in S\) and \(v \notin T\). Improve the labeling \(l\) to \(l'\): If \(r \in S,\) then \(l'(r) = l(r) - \delta_l,\) If \(r \in T,\) then \(l'(r) = l(r) + \delta_l.\) If \(r \notin S\) and \(r \notin T,\) then \(l'(r) = l(r).\) \(l'\) is a valid labeling and \(E_l \subset E_{l'}.\) Putting it all together: The Hungarian Algorithm Start with some matching \(M\), a valid labeling \(l\), where \(l\) is defined as the labelling \(\forall x \in X, y \in Y| l(y) = 0, l(x) = \text{ max}_{y \in Y}(w\big(x, y)\big)\). Do these steps until a perfect matching is found \((\)when \(M\) is perfect\():\) (a) Look for an augmenting path in \(M.\) (b) If an augmenting path does not exist, improve the labeling and then go back to step (a).

Each step will increase the size of the matching \(M\) or it will increase the size of the set of labeled edges, \(E_l\). This means that the process will eventually terminate since there are only so many edges in the graph \(G\). [4]

When the process terminates, \(M\) will be a perfect matching. By the Kuhn-Munkres theorem , this means that the matching is a maximum-weight matching.

The algorithm defined above can be implemented in the soccer scenario. First, the conflicting node is identified, implying that there is an alternating tree that must be reconfigured.

There is an alternating path between defense, Eva, mid, and Tom.

To find the best appropriate node, find the minimum \(\delta_l\), as defined in step 4 above, where \(l_u\) is the label for player \(u,\) \(l_v\) is the label for position \(v,\) and \(w_{u, v}\) is the weight on that edge.

The \(\delta_l\) of each unmatched node is computed, where the minimum is found to be a value of 2, between Tom playing mid \((8 + 0 – 6 = 2).\)

The labels are then augmented and the new edges are graphed in the example. Notice that defense and mid went down by 2 points, whereas Eva’s skillset got back two points. However, this is expected as Eva can't play in both positions at once.

Augmenting path leads to relabeling of nodes, which gives rise to the maximum-weighted path.

These new edges complete the perfect matching of the graph, which implies that a maximum-weighted graph has been found and the algorithm can terminate.

The complexity of the algorithm will be analyzed using the graph-based technique as a reference, yet the result is the same as for the matrix-based one.

Algorithm analysis [3] At each \(a\) or \(b\) step, the algorithm adds one edge to the matching and this happens \(O\big(|V|\big)\) times. It takes \(O\big(|V|\big)\) time to find the right vertex for the augmenting (if there is one at all), and it is \(O\big(|V|\big)\) time to flip the matching. Improving the labeling takes \(O\big(|V|\big)\) time to find \(\delta_l\) and to update the labelling accordingly. We might have to improve the labeling up to \(O\big(|V|\big)\) times if there is no augmenting path. This makes for a total of \(O\big(|V|^2\big)\) time. In all, there are \(O\big(|V|\big)\) iterations each taking \(O\big(|V|\big)\) work, leading to a total running time of \(O\big(|V|^3\big)\).

• Matching Algorithms
• Bruff, D. The Assignment Problem and the Hungarian Method . Retrieved June 26, 2016, from http://www.math.harvard.edu/archive/20_spring_05/handouts/assignment_overheads.pdf
• Golin, M. Bipartite Matching & the Hungarian Method . Retrieved Retrieved June 26th, 2016, from http://www.cse.ust.hk/~golin/COMP572/Notes/Matching.pdf
• Grinman, A. The Hungarian Algorithm for Weighted Bipartite Graphs . Retrieved June 26, 2016, from http://math.mit.edu/~rpeng/18434/hungarianAlgorithm.pdf
• Golin, M. Bipartite Matching & the Hungarian Method . Retrieved June 26, 2016, from http://www.cse.ust.hk/~golin/COMP572/Notes/Matching.pdf

Problem Loading...

Note Loading...

Set Loading...

A new algorithm for the assignment problem

• Published: December 1981
• Volume 21 , pages 152–171, ( 1981 )

Cite this article

• Dimitri P. Bertsekas 1  

949 Accesses

199 Citations

Explore all metrics

We propose a new algorithm for the classical assignment problem. The algorithm resembles in some ways the Hungarian method but differs substantially in other respects. The average computational complexity of an efficient implementation of the algorithm seems to be considerably better than the one of the Hungarian method. In a large number of randomly generated problems the algorithm has consistently outperformed an efficiently coded version of the Hungarian method by a broad margin. The factor of improvement increases with the problem dimension N and reaches an order of magnitude for N equal to several hundreds.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Similar content being viewed by others

Microsoft COCO: Common Objects in Context

A Comprehensive Survey of Clustering Algorithms

Density-Based Clustering Based on Hierarchical Density Estimates

E. Lawler, Combinatorial optimization: networks and matroids (Holt, Rinehart and Winston, 1976).

Google Scholar  

H.W. Kuhn, “The Hungarian method for the assignment problem”, Naval Research Logistics Quarterly 2 (1955) 83–97.

R.S. Barr, F. Glover and D. Klingman, “The alternating basis algorithm for assignment problems”, Mathematical Programming 13 (1977) 1.

G.H. Bradley, G.G. Brown and G.W. Graves, ‘Design and implementation of large scale primal transhipment algorithms”, Management Science 24 (1977) 1.

R.V. Helgason and J.L. Kennigton, “NETFLOW program documentation”, technical report IEOR 76011, Department of Industrial Engineering and Operations Research, Southern Methodist University (1976).

R.S. Hatch, “Bench marks comparing transportation codes based on primal simplex and primal—dual algorithms”, Operations Research 23 (1975) 1167.

L.F. McGinnis, “Implementation and testing of a primal—dual algorithm for the assignment problem”, Industrial and Systems Engineering report series No. J-78-31, Georgia Institute of Technology (November 1978).

A. Weintraub, and F. Barahona, “A dual algorithm for the assignment problem”, Departmento de Industrias Report No. 2, Universidad de Chile-Sede Occidente (April 1979).

F. Glover and D. Klingman, “Comment on a note by Hatch on network algorithms” Operations Research 26 (1978) 370.

J. Edmonds and R. Karp, “Theoretical improvements in algorithmic efficiency for network flow problems”, Journal of the Association for Computing Machinery 19 (1972) 248–264.

D.P. Bertsekas, “An algorithm for the Hitchcock transportation problem”, Proceedings of the 18 th Allerton conference on communication, control and computing , Allerton Park, 11 Oct. 1979.

M.D. Grigoriadis, Talk at Mathematical Programming Symposium, Montreal, August 1979 (also private communication).

Download references

Author information

Authors and affiliations.

Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 02139, Cambridge, MA, USA

Dimitri P. Bertsekas

You can also search for this author in PubMed   Google Scholar

Additional information

Work supported by Grant NSF ENG-7906332.

Rights and permissions

Reprints and permissions

About this article

Bertsekas, D.P. A new algorithm for the assignment problem. Mathematical Programming 21 , 152–171 (1981). https://doi.org/10.1007/BF01584237

Download citation

Received : 15 August 1979

Revised : 06 October 1980

Issue Date : December 1981

DOI : https://doi.org/10.1007/BF01584237

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Assignment Problems
• Network Flows
• Hungarian Method
• Computational Complexity
• Find a journal
• Publish with us
• Track your research

• Branch and Bound Tutorial
• Backtracking Vs Branch-N-Bound
• 0/1 Knapsack
• 8 Puzzle Problem
• Job Assignment Problem
• N-Queen Problem
• Travelling Salesman Problem
• Branch and Bound Algorithm
• Introduction to Branch and Bound - Data Structures and Algorithms Tutorial
• 0/1 Knapsack using Branch and Bound
• Implementation of 0/1 Knapsack using Branch and Bound
• 8 puzzle Problem using Branch And Bound

Job Assignment Problem using Branch And Bound

• N Queen Problem using Branch And Bound
• Traveling Salesman Problem using Branch And Bound

Let there be N workers and N jobs. Any worker can be assigned to perform any job, incurring some cost that may vary depending on the work-job assignment. It is required to perform all jobs by assigning exactly one worker to each job and exactly one job to each agent in such a way that the total cost of the assignment is minimized.

Let us explore all approaches for this problem.

Solution 1: Brute Force  

We generate n! possible job assignments and for each such assignment, we compute its total cost and return the less expensive assignment. Since the solution is a permutation of the n jobs, its complexity is O(n!).

Solution 2: Hungarian Algorithm  

The optimal assignment can be found using the Hungarian algorithm. The Hungarian algorithm has worst case run-time complexity of O(n^3).

Solution 3: DFS/BFS on state space tree  

A state space tree is a N-ary tree with property that any path from root to leaf node holds one of many solutions to given problem. We can perform depth-first search on state space tree and but successive moves can take us away from the goal rather than bringing closer. The search of state space tree follows leftmost path from the root regardless of initial state. An answer node may never be found in this approach. We can also perform a Breadth-first search on state space tree. But no matter what the initial state is, the algorithm attempts the same sequence of moves like DFS.

Solution 4: Finding Optimal Solution using Branch and Bound  

The selection rule for the next node in BFS and DFS is “blind”. i.e. the selection rule does not give any preference to a node that has a very good chance of getting the search to an answer node quickly. The search for an optimal solution can often be speeded by using an “intelligent” ranking function, also called an approximate cost function to avoid searching in sub-trees that do not contain an optimal solution. It is similar to BFS-like search but with one major optimization. Instead of following FIFO order, we choose a live node with least cost. We may not get optimal solution by following node with least promising cost, but it will provide very good chance of getting the search to an answer node quickly.

There are two approaches to calculate the cost function:  

• For each worker, we choose job with minimum cost from list of unassigned jobs (take minimum entry from each row).
• For each job, we choose a worker with lowest cost for that job from list of unassigned workers (take minimum entry from each column).

In this article, the first approach is followed.

Let’s take below example and try to calculate promising cost when Job 2 is assigned to worker A. 

Since Job 2 is assigned to worker A (marked in green), cost becomes 2 and Job 2 and worker A becomes unavailable (marked in red). 

Now we assign job 3 to worker B as it has minimum cost from list of unassigned jobs. Cost becomes 2 + 3 = 5 and Job 3 and worker B also becomes unavailable. 

Finally, job 1 gets assigned to worker C as it has minimum cost among unassigned jobs and job 4 gets assigned to worker D as it is only Job left. Total cost becomes 2 + 3 + 5 + 4 = 14. 

Below diagram shows complete search space diagram showing optimal solution path in green. 

Complete Algorithm:  

Below is the implementation of the above approach:

Time Complexity: O(M*N). This is because the algorithm uses a double for loop to iterate through the M x N matrix.  Auxiliary Space: O(M+N). This is because it uses two arrays of size M and N to track the applicants and jobs.

Please Login to comment...

Similar reads.

• Branch and Bound

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Help Center Help Center

• Help Center
• Trial Software
• Product Updates
• Documentation

Introduction to Assignment Methods in Tracking Systems

In a multiple target tracking (MTT) system, one or more sensors generate multiple detections from multiple targets in a scan. To track these targets, one essential step is to assign these detections correctly to the targets or tracks maintained in the tracker so that these detections can be used to update these tracks. If the number of targets or detections is large, or there are conflicts between different assignment hypotheses, assigning detections is challenging.

Depending on the dimension of the assignment, assignment problems can be categorized into:

2-D assignment problem – assigns n targets to m observations. For example, assign 5 tracks to 6 detections generated from one sensor at one time step.

S-D assignment problem – assigns n targets to a set ( m 1 , m 2 , m 3 , …) of observations. For example, assign 5 tracks to 6 detections from one sensor, and 4 detections from another sensor at the same time. This example is a typical 3-D assignment problem.

To illustrate the basic idea of an assignment problem, consider a simple 2-D assignment example. One company tries to assign 3 jobs to 3 workers. Because of the different experience levels of the workers, not all workers are able to complete each job with the same effectiveness. The cost (in hours) of each worker to finish each job is given by the cost matrix shown in the table. An assignment rule is that each worker can only take one job, and one job can only be taken by one worker. To guarantee efficiency, the object of this assignment is to minimize the total cost.

Since the numbers of workers and jobs are both small in this example, all the possible assignments can be obtained by enumeration, and the minimal cost solution is highlighted in the table with assignment pairs (1, 3), (2, 2) and (3, 1). In practice, as the size of the assignment becomes larger, the optimal solution is difficult to obtain for 2-D assignment. For an S-D assignment problem, the optimal solution may not be obtainable in practice.

2-D Assignment in Multiple Target Tracking

In the 2-D MTT assignment problem, a tracker tries to assign multiple tracks to multiple detections. Other than the dimensionality challenge mentioned above, a few other factors can significantly change the complexity of the assignment:

Target or detection distribution — If targets are sparsely distributed, associating a target to its corresponding detection is relatively easy. However, if targets or detections are densely distributed, assignments become ambiguous because assigning a target to a detection or another nearby detection rarely makes any differences on the cost.

Probability of detection ( P d ) of the sensor — P d describes the probability that a target is detected by the sensor if the target is within the field of view of the sensor. If the P d of a sensor is small, then the true target may not give rise to any detection during a sensor scan. As a result, the track represented by the true target may steal detections from other tracks.

Sensor resolution — Sensor resolution determines the sensor’s ability to distinguish the detections from two targets. If the sensor resolution is low, then two targets in proximity may only give rise to one detection. This violates the common assumption that each detection can only be assigned to one track and results in unresolvable assignment conflicts between tracks.

Clutter or false alarm rate of the sensor — False alarms introduce additional possible assignments and therefore increase the complexity of data assignment.

The complexity of the assignment task can determine which assignment methods to apply. In Sensor Fusion and Tracking Toolbox™ toolbox, three 2-D assignment approaches are employed corresponding to three different trackers:

trackerGNN — adopts a global nearest data assignment approach

trackerJPDA — adopts a joint probability data association approach

trackerTOMHT — adopts a tracker-oriented multiple hypothesis tracking approach

Note that each tracker processes the data from sensors sequentially, meaning that each tracker only deals with the assignment problem with the detections of one sensor at a time. Even with this treatment, there may still be too many assignment pairs. To reduce the number of track and detection pairs considered for assignment, the gating technique is frequently used.

Gating is a screening mechanism to determine which observations are valid candidates to update existing tracks and eliminate unlikely detection-to-track pairs using the distribution information of the predicted tracks. To establish the validation gate for a track at the current scan, the estimated track for the current step is predicted from the previous step.

For example, a tracker confirms a track at time t k and receives several detections at time t k +1 . To form a validation gate at time t k +1 , the tracker first needs to obtain the predicted measurement as:

y ^ k + 1 = h ( x ^ k + 1 | k )

where x ^ k + 1 | k is the track estimate predicted from time t k and h ( x ^ k + 1 | k ) is the measurement model that outputs the expected measurement given the track state. The observation residual vector is

y ˜ = y k + 1 − y ^ k + 1

where y k +1 is the actual measurement. To establish the boundary of the gate, the detection residual covariance S is used to form an ellipsoidal validation gate. The ellipsoidal gate that establishes a spatial ellipsoidal region in the measurement space is defined in Mahalanobis distance as:

d 2 ( y k + 1 ) = y ˜ T S − 1 y ˜ ≤ G

where G is the gating threshold which you can specify based on the assignment requirement. Increasing the threshold can incorporate more detections into the gate.

After the assignment gate is established for each track, the gating status of each detection y i ( i = 1,…, n ) can be determined by comparing its Mahalanobis distance d 2 ( y i ) with the gating threshold G . If d 2 ( y i ) < G , then detection y i is inside the gate of the track and will be considered for association. Otherwise, the possibility of the detection associated with the track is removed. In Figure 1, T 1 represents a predicted track estimate, and O 1 – O 6 are six detections. Based on the gating result, O 1 , O 2 , and O 3 are within the validation gate in the figure.

Global Nearest Neighbor (GNN) Method

The GNN method is a single hypothesis assignment method. For each new data set, the goal is to assign the global nearest observations to existing tracks and to create new track hypotheses for unassigned detections.

The GNN assignment problem can be easily solved if there are no conflicts of association between tracks. The tracker only needs to assign a track to its nearest neighbor. However, conflict situations (see Figure 2) occur when there is more than one observation within a track’s validation gate or an observation is in the gates of more than one track. To resolve these conflicts, the tracker must evaluate a cost matrix.

The elements of a cost matrix for the GNN method includes the distance from tracks to detections and other factors you might want to consider. For example, one approach is to define a generalized statistical distance between observation j to track i as:

C i j = d i j + ln ( | S i j | )

where d ij is the Mahalanobis distance and ln(| S ij |), the logarithm of the determinant of the residual covariance matrix, is used to penalize tracks with greater prediction uncertainty.

For the assignment problem given in Figure 2, the following table shows a hypothetical cost matrix. The nonallowed assignments, which failed the gating test, are denoted by X. (In practice, the costs of nonallowed assignments can be denoted by large values, such as 1000.)

For this problem, the highlighted optimal solution can be found by enumeration. Detection O 3 is unassigned, so the tracker will use it to create a new tentative track. For more complicated GNN assignment problems, more accurate formulations and more efficient algorithms to obtain the optimal or suboptimal solution are required.

A general 2-D assignment problem can be formed as following. Given the cost matrix element C ij , find an assignment Z = { z ij } that minimizes

J = ∑ i = 0 n ∑ j = 0 m C i j z i j

subject to two constraints:

∑ i = 0 m z i j = 1 , ∀ j ∑ j = 0 n z i j = 1 , ∀ i

If track i is assigned to observation j , then z ij = 1. Otherwise, z ij = 0. z i 0 = 1 represents the hypothesis that track i is not assigned to any detection. Similarly, z 0 j = 1 represents the hypothesis that observation j is not assigned to any track. The first constraint means each detection can be assigned to no more than one track. The second constraint means each track can be assigned to no more than one detection.

Sensor Fusion and Tracking Toolbox provides multiple functions to solve 2-D GNN assignment problems:

assignmunkres – Uses the Munkres algorithm, which guarantees an optimal solution but may require more calculation operations.

assignauction – Uses the auction algorithm, which requires fewer operations but can possibly converge on an optimal or suboptimal solution.

assignjv – Uses the Jonker-Volgenant algorithm, which also converges on an optimal or suboptimal solution but usually with a faster converging speed.

In trackerGNN , you can select the assignment algorithm by specifying the Assignment property.

K Best Solutions to the 2-D Assignment Problem

Because of the uncertainty nature of assignment problems, only obtaining a solution (optimal or suboptimal) may not be sufficient. To account for multiple hypotheses about the assignment between tracks and detections, multiple suboptimal solutions are required. These suboptimal solutions are called K best solutions to the assignment problem.

The K best solutions are usually obtained by varying the solution obtained by any of the previously mentioned assignment functions. Then, at the next step, the K best solution algorithm removes one track-to-detection pair in the original solution and finds the next best solution. For example, for this cost matrix:

[ 10 5 8 9 7 × 20 × × × 21 1 5 × 17 × × × × 1 6 22 ]

each row represents the cost associated with a track, and each column represents the cost associated with a detection. As highlighted, the optimal solution is (7,15,16, 9) with a cost of 47. In the next step, remove the first pair (corresponding to 7), and the next best solution is (10,15, 20, 22) with a cost of 67. After that, remove the second pair (corresponding to 15), and the next best solution is (7, 5,16, 9) with a cost of 51. After a few steps, the five best solutions are:

See the Find Five Best Solutions Using Assignkbest example, which uses the assignkbest function to find the K best solutions.

Joint Probability Data Association (JPDA) Method

While the GNN method makes a rigid assignment of a detection to a track, the JPDA method applies a soft assignment so that detections within the validation gate of a track can all make weighted contributions to the track based on their probability of association.

For example, for the gating results shown in Figure 1, a JPDA tracker calculates the possibility of association between track T 1 and observations O 1 , O 2 , and O 3 . Assume the association probability of these three observations are p 11 , p 12 , and p 13 , and their residuals relative to track T 1 are y ˜ 11 , y ˜ 12 , and y ˜ 13 , respectively. Then the weighted sum of the residuals associated with track T 1 is:

y ˜ 1 = ∑ j = 1 3 p 1 j y ˜ 1 j

In the tracker, the weighted residual is used to update track T 1 in the correction step of the tracking filter. In the filter, the probability of unassignment, p 10 , is also required to update track T 1 . For more details, see JPDA Correction Algorithm for Discrete Extended Kalman Filter .

The JPDA method requires one more step when there are conflicts between assignments in different tracks. For example, in the following figure, track T 2 conflicts with T 1 on the assignment of observation O 3 . Therefore, to calculate the association probability p 13 , the joint probability that T 2 is not assigned to O 3 (that is T 2 is assigned to O 6 or unassigned) must be accounted for.

Track-Oriented Multiple Hypothesis Tracking (TOMHT) Method

Unlike the JPDA method, which combines all detections within the validation gate using a weighted sum, the TOMHT method generates multiple hypotheses or branches of the tracks based on the detections within the gate and propagates high-likelihood branches between scan steps. After propagation, these hypotheses can be tested and pruned based on the new set of detections.

For example, for the gating scenario shown in Figure 1, a TOMHT tracker considers the following four hypotheses:

Assign no detection to T 1 resulting in hypothesis T 10

Assign O 1 to T 1 resulting in hypothesis T 11

Assign O 2 to T 1 resulting in hypothesis T 12

Assign O 3 to T 1 resulting in hypothesis T 13

Given the assignment threshold, the tracker will calculate the possibility of each hypothesis and discard hypotheses with probability lower than the threshold. Hypothetically, if only p 10 and p 11 are larger than the threshold, then only T 10 and T 11 are propagated to the next step for detection update.

S-D Assignment in Multiple Target Tracking

In an S-D assignment problem, the dimension of assignment S is larger than 2. Note that all three trackers ( trackerGNN , trackerJPDA , and trackerTOMHT ) process detections from each sensor sequentially, which results in a 2-D assignment problem. However, some applications require a tracker that processes simultaneous observations from multiple sensor scans all at once, which requires solving an S-D assignment problem. Meanwhile, the S-D assignment is widely used in tracking applications such as static data fusion, which preprocesses the detection data before fed to a tracker.

An S-D assignment problem for static data fusion has S scans of a surveillance region from multiple sensors simultaneously, and each scan consists of multiple detections. The detection sources can be real targets or false alarms. The object is to detect an unknown number of targets and estimate their states. For example, as shown in the Figure 4, three sensor scans produce six detections. The detections in the same color belong to the same scan. Since each scan generates two detections, there are probably two targets in the region of surveillance. To choose between different assignment or association possibilities, evaluate the cost matrix.

The calculation of the cost can depend on many factors, such as the distance between detections and the covariance distribution of each detection. To illustrate the basic concept, the assignment costs for a few hypotheses are hypothetically given in the table [1] .

In the table, 0 denotes a track is associated with no detection in that scan. Assume the hypotheses not shown in the table are truncated by gating or neglected because of high costs. To concisely represent each track, use c ijk to represent the cost for association of observation i in scan 1, j in scan 2, and k in scan 3. For example, for the assignment hypothesis 1, c 011 = -10.2. Several track hypotheses conflict with other in the table. For instance, the two most likely assignments, c 111 and c 121 are incompatible because they share the same observation in scans 1 and 3.

The goal of solving an S-D assignment problem is to find the most likely compatible assignment hypothesis accounting for all the detections. When S ≥ 3, however, the problem is known to scale with the number of tracks and detections at an exponential rate (NP-hard). The Lagrangian relaxation method is commonly used to obtain the optimal or sub-optimal solution for an S-D assignment problem efficiently.

Brief Introduce to the Lagrangian Relaxation Method for 3-D Assignment

Three scans of data have a number of M 1 , M 2 , and M 3 observations, respectively. Denote an observation of scan 1, 2, and 3 as i , j , and k , respectively. For example, i = 1, 2, …, M 1 . Use z ijk to represent the track formation hypothesis of O 1 i , O 2 j , and O 3 k . If the hypothesis is valid, then z ijk = 1; otherwise, z ijk = 0. As mentioned, c ijk is used to represent the cost of z ijk association. c ijk is 0 for false alarms and negative for possible associations. The S-D optimization problem can be formulated as:

J ( z ) = min i , j , k ∑ i = 0 M 1 ∑ j = 0 M 2 ∑ k = 0 M 3 c i j k z i j k

subject to three constraints:

∑ i = 0 M 1 ∑ j = 0 M 2 z i j k = 1 , ∀ k = 1 , 2 , … , M 3 ∑ i = 0 M 1 ∑ k = 0 M 3 z i j k = 1 , ∀ j = 1 , 2 , … , M 2 ∑ j = 0 M 2 ∑ k = 0 M 3 z i j k = 1 , ∀ i = 1 , 2 , … , M 1

The optimization function chooses associations to minimize the total cost. The three constraints ensure that each detection is accounted for (either included in an assignment or treated as false alarm).

The Lagrangian relaxation method approaches this 3-D assignment problem by relaxing the first constraint using Lagrange multipliers. Define a new function L ( λ ) :

L ( λ ) = ∑ k = 0 M 3 λ k [ ∑ i = 0 M 1 ∑ j = 0 M 2 z i j k − 1 ]

where λ k , k = 1, 2, …, M 3 are Lagrange multipliers. Subtract L from the original object function J ( z ) to get a new object function, and the first constraint in k is relaxed. Therefore, the 3-D assignment problem reduces to a 2-D assignment problem, which can be solved by any of the 2-D assignment method. For more details, see [1] .

The Lagrangian relaxation method allows the first constraint to be mildly violated, and therefore can only guarantee a suboptimal solution. For most applications, however, this is sufficient. To specify the solution accuracy, the method uses the solution gap, which defines the difference between the current solution and the potentially optimistic solution. The gap is nonnegative, and a smaller solution gap corresponds to a solution closer to the optimal solution.

Sensor Fusion and Tracking Toolbox provides assignsd to solve for S-D assignment using the Lagrangian relaxation method. Similar to the K best 2-D assignment solver assignkbest , the toolbox also provides a K best S-D assignment solver, assignkbestsd , which is used to provide multiple suboptimal solutions for an S-D assignment problem.

See Tracking Using Distributed Synchronous Passive Sensors for the application of S-D assignment in static detection fusion.

assignTOMHT | assignauction | assignjv | assignkbest | assignkbestsd | assignmunkres | assignsd | trackerGNN | trackerJPDA | trackerTOMHT

[1] Blackman, S., and R. Popoli. Design and Analysis of Modern Tracking Systems. Artech House Radar Library, Boston, 1999.

[2] Musicki, D., and R. Evans. "Joint Integrated Probabilistic Data Association: JIPDA." IEEE Transactions on Aerospace and Electronic Systems. Vol. 40, Number 3, 2004, pp 1093 –1099.

MATLAB Command

You clicked a link that corresponds to this MATLAB command:

Run the command by entering it in the MATLAB Command Window. Web browsers do not support MATLAB commands.

Select a Web Site

Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .

• Switzerland (English)
• Switzerland (Deutsch)
• Switzerland (Français)
• 中国 (English)

You can also select a web site from the following list:

How to Get Best Site Performance

Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.

• América Latina (Español)
• Canada (English)
• United States (English)
• Belgium (English)
• Denmark (English)
• Deutschland (Deutsch)
• España (Español)
• Finland (English)
• France (Français)
• Ireland (English)
• Italia (Italiano)
• Luxembourg (English)
• Netherlands (English)
• Norway (English)
• Österreich (Deutsch)
• Portugal (English)
• Sweden (English)
• United Kingdom (English)

Asia Pacific

• Australia (English)
• India (English)
• New Zealand (English)

Contact your local office

Browse Course Material

Course info.

• Prof. Michel Goemans

Departments

• Electrical Engineering and Computer Science
• Mathematics

As Taught In

• Algorithms and Data Structures
• Theory of Computation

Learning Resource Types

Advanced algorithms, assignments, problems sets from 2008.

The problem sets are due in the sessions listed in the table.

Problems Sets with Solution from 2001

You are leaving MIT OpenCourseWare

Navigation Menu

Search code, repositories, users, issues, pull requests..., provide feedback.

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

• Notifications

Solutions to the Assignments for the Algorithmic Toolbox course offered by UCSanDiego on Coursera.

prantosky/coursera-algorithmic-toolbox

Folders and files, repository files navigation, algorithmic toolbox.

• Sum of Two Digits
• Maximum Pairwise Product
• Fibonacci Number
• Last Digit of a Large Fibonacci Number
• Greatest Common Divisor
• Least Common Multiple
• Fibonacci Number Again
• Last Digit of the Sum of Fibonacci Numbers
• Last Digit of the Sum of Fibonacci Numbers Again
• Last Digit of the Sum of Squares of Fibonacci Numbers
• Money Change
• Maximum Value of the Loot
• Car Fueling
• Maximum Advertisement Revenue
• Collecting Signatures
• Maximum Number of Prizes
• Maximum Salary
• Binary Search
• Majority Element
• Improving Quick Sort
• Number of Inversions
• Organizing a Lottery
• Closest Points
• Money Change Again
• Primitive Calculator
• Edit Distance
• Longest Common Subsequence of Two Sequences
• Longest Common Subsequence of Three Sequences
• Maximum Amount of Gold
• Approach 1 (Brute Force)
• Approach 2 (Dynamic Programming)
• Maximum Value of an Arithmetic Expression

Contributors 2