Question

I have a collection of unsorted stamps. Describe two algorithms to find those that belong together,...

I have a collection of unsorted stamps. Describe two algorithms to find those that belong together, coupled to two simple sorting algortihms. Do a time complexity analysis for both and determine which is the best during these circumstances. It is enough to just describe in text so no pseudocode and programs. Also it is enoguh to reason about the time complexities.

0 0
Add a comment Improve this question Transcribed image text
Answer #1

Two Algorithms that can be used are Counting sort and by using an approach similar to insertion sort.

Counting sort Approach-> Assuming that the different type of stamps are limited i.e. there are a limited number of different types of stamps, counting sort can be used to first count the occurrence of each type of stamp and then arranging the stamps by selecting all the similar type of stamps together by referring to their count values.  This is a very effective way of sorting an input that contains a limited number of different entities with each entity having multiple duplicate values. This algorithm runs with O(n) time complexity.

Insertion Sort Approach-> In this approach the collection of stamps can be assumed as an array containing duplicate values. Each different type of stamp can be assigned a number i.e. 0,1,2....,n. This helps in finding the location where the stamp belongs to. For example, if we start sorting from the first stamp, we can go through the whole collection of stamps and put all similar stamps that match the first stamp before that stamp. Then we choose the second stamp and repeat the procedure. Thus the type of stamp with number 0 assigned to them appears first followed by the type of stamps assigned the number 1 and so on. This algorithm takes in the worst case scenario O() as time complexity and O(n) as the best case complexity. Best case occurs when the stamps are nearly sorted.

Add a comment
Know the answer?
Add Answer to:
I have a collection of unsorted stamps. Describe two algorithms to find those that belong together,...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
  • Hello I need help with this program. Should programmed in C! Program 2: Sorting with Pointers...

    Hello I need help with this program. Should programmed in C! Program 2: Sorting with Pointers Sometimes we're given an array of data that we need to be able to view in sorted order while leaving the original order unchanged. In such cases we could sort the data set, but then we would lose the information contained in the original order. We need a better solution. One solution might be to create a duplicate of the data set, perhaps make...

  • Python program This assignment requires you to write a single large program. I have broken it...

    Python program This assignment requires you to write a single large program. I have broken it into two parts below as a suggestion for how to approach writing the code. Please turn in one program file. Sentiment Analysis is a Big Data problem which seeks to determine the general attitude of a writer given some text they have written. For instance, we would like to have a program that could look at the text "The film was a breath of...

  • Read this article. Then write a 250 word response on two of the programs you like...

    Read this article. Then write a 250 word response on two of the programs you like the most. Open source business intelligence software 1. BIRT BIRT is an open source BI program that CloudTweaks says is often viewed as the industry standard. BIRT boasts “over 12 million downloads and over 2.5 million developers across 157 countries.” Its users include heavyweights such as Cisco, S1, and IBM (which is also a BIRT sponsor). They also have maturity going for them, as...

  • C++. Need some help getting started. We will also have the following two functions: 1. A...

    C++. Need some help getting started. We will also have the following two functions: 1. A mutate function that randomly modifies a chromosome. 2. A crossover function that takes two chromosomes and splits each one at the same spot, then combines them together. Our genetic algorithm works by iterating over generations of chromosomes via the following process: 1. Generate random population. 2. Until we get an answer that is good enough, do the next steps in a loop: (a) Do...

  • PART 3 ORGANIZATIONAL LEADERSHIP 396 OPENING CASE Application As chief executive officer, Larry Page is responsible...

    PART 3 ORGANIZATIONAL LEADERSHIP 396 OPENING CASE Application As chief executive officer, Larry Page is responsible for Google's product development and technology strat- egy Sergey Brin co-founded Google Inc. with Larry Page in 1998. Today, he directs special projects. Eric Schmidt. In other words, Googe is a change-driven, not a status-quo, organization Google certainly strives for a strategy-culture fit. As Google's leadership sees it, great, creative things are more likely to happen with the right company culture.At Google, there is...

  • Read the articles provided (Riggio, 2008) and Javidan & Walker (2012). Perform a self-assessm...

    Read the articles provided (Riggio, 2008) and Javidan & Walker (2012). Perform a self-assessment of the global mindset competencies. What competencies do you feel are your strengths? Your areas for improvement? What next learning steps could you take to address your areas for improvement? LEADERSHIP DEVELOPMENT: THE CURRENT STATE AND FUTURE EXPECTATIONS Ronald E. Riggio Claremont McKenna College This article discusses the common themes in this special issue of Consulting Psychology Journal on "Leadership Development" and summarizes some of the...

  • Here is the data analysis project, please I need an excellent project, it is due 4 hours! Statist...

    here is the data analysis project, please I need an excellent project, it is due 4 hours! Statistics course. GENERAL DESCRIPTION For the data analysis project, you address some questions that interest you with the statistical methodology we learn in MAT 235.   You choose the question; you decide how to collect data; you do the analyses. The questions can address almost any topic (although I have veto power), including topics in economics, psychology, sociology, natural science, medicine, public policy, sports,...

  • In Java(using BlueJ) Purpose Purpose is to practice using file input and output, and array list of objects. Also, this lab specification tells you only what to do, you now have more responsibility to...

    In Java(using BlueJ) Purpose Purpose is to practice using file input and output, and array list of objects. Also, this lab specification tells you only what to do, you now have more responsibility to design how to do it. Problem description You are given a text file called 'Students.txt' that contains information on many students. Your program reads the file, creating many Student objects, all of which will be stored into an array list of Student objects, in the Students...

  • Help I have taken this test so many times : These tests are intended for master's...

    Help I have taken this test so many times : These tests are intended for master's and doctoral students. Read these directions carefully! The below test includes 10 questions, randomly selected from a large inventory. Most questions will be different each time you take the test, You must answer at least 9 out of 10 questions correctly to receive your Certificate. You have 40 minutes to complete each test, and you must answer all 10 questions in order to to...

  • I have this case study to solve. i want to ask which type of case study...

    I have this case study to solve. i want to ask which type of case study in this like problem, evaluation or decision? if its decision then what are the criterias and all? Stardust Petroleum Sendirian Berhad: how to inculcate the pro-active safety culture? Farzana Quoquab, Nomahaza Mahadi, Taram Satiraksa Wan Abdullah and Jihad Mohammad Coming together is a beginning; keeping together is progress; working together is success. - Henry Ford The beginning Stardust was established in 2013 as a...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT