(2 pts) A music playing application stores a sequence of 1000 four-minute music
ID: 3591342 • Letter: #
Question
(2 pts) A music playing application stores a sequence of 1000 four-minute music files for playback. (All songs are the same length of time for this problem.) The music files can be stored in one of two ways: 2. Algorithm 1: Songs are stored in the computer's memory in arbitrary order. Each song has a code that indicates the location in memory of the song that plays next. The player keeps track of the location of the first song in the playback sequence only. Algorithm 2: Songs are stored in the computer's memory as a whole in the order of playback starting at a specific fixed location in computer memory, which cannot be changed. (a) If the application user wants to insert a new song at the beginning of the playlist, which algorithm will allow the user to complete this operation faster? Briefly explain your answer by describing what each algorithm would do to accomplish this taskExplanation / Answer
Here basically the difference between two algorithms is that Algorithm 1 uses Linked List and Algorithm 2 uses arrays to store the songs.
In algorithm 1, every song will be stored as a node of linked list and every node will have a Next pointer which will point to the address of next song node and so on. So there is no predefined order. Songs will be stored in an arbitrary order. We just need to maintain the Next pointers of all the song nodes to move from one song node to the next song node.
Whereas in Algorithm 2, songs will be stored in a predefined specific order in the form of an array. Since an array is stored in a contiguous memory block, we don't need to maintain pointers to next song.
(a) For inserting a new song at the beginning of the list, in Algorithm 1, Let Head be a pointer to the current starting node. Then we just need to set the Next pointer of new song to the current Head pointer and then set the Head pointer point to the new song. This way Head pointer (which indicates the beginning of the songs list) will be pointing to new song and thus new song can be added in just two operations. So, constant time is required.
While in Algorithm 2, since we are storing the list of songs in an array, if we want to add a song at the beginning of the list, then all the other songs will have to be shifted forward by 1 position. Thus 1000 songs will need to be shifted. Thus this will be more time expensive as compared to Algorithm 1.
Thus, for adding a song at the beginning of the list, Algorithm 1 is better than Algorithm 2.
(b) If user wants to skip first 499 songs and wants to directly reach to 500th song, in Algorithm 1, there is no way to reach to 500th song directly, because there is no predefined order. We will have to traverse through every song node to reach the next song. Because Next pointer of song 1 has the address of song 2, then Next pointer of song 2 has the address of song 3 and so on. So we will have to go through all the 499 songs to reach to 500th song.
However, in Algorithm 2, songs are stored in form of an array. We know that array has Randon Access property due to its nature of contiguous memory storage. So we can directly reach 500th song. So in this case, Algorithm 2 is better.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.