Assignment 6 – Queues
Objectives
Implement the Queue Data Structure and use it to implement a complex algorithm
Supports Learning Outcomes 1, 2, and 3
1. Describe both complex and simple data structures.
2. Select the correct data structure and algorithm to solve specific problems.
3. Implement data structures and algorithms in computer code.
Lectures
Start by going through Topic – Stacks and Queues if you have not already done so. The Queue is a pretty straightforward concept (everyone has stood in line before).
Assignment
You are going to create a Queue. (alternately, you can create a list and simply implement enqueue and dequeue functions in the List – that will technically make it a queue). You will fill the first list with numbers consecutively numbered from 2 to n, where n is entered by the user (we will call this Q1). When creating your Queue object, use the correct function names for enqueue and dequeue functions. You cannot use a Javascript array in your implementation – you must implement enqueue and dequeue.
Create a second empty Queue Q2.
Once you have the first Queue filled, we will use a technique called Sieve of Eratosthenes, which uses the first queue to fill the second queue. You will need to look at the algorithm for this https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
Here is the algorithm;
1. Dequeue 1st element in Q1 (which will be 2). You will need to remember the value of this element – we will call it X.
2. Enqueue this element into Q2 (Q2 is the list of primes)
3. Iterate and Dequeue each successive element of Q1
If the value is divisible by X, go to the next element
if the value is not divisible by X enqueue back onto Q1, and go to the next element.
4. Print the values of Q1 and Q2 after each time through.
5. When done go back to the beginning of the Q1 and repeat steps 1-3 (the first value will be 3 the second time around)
Sample output with input 10
Iteration 0: Q1 = 2 3 4 5 6 7 8 9 10, Q2 = ,
Iteration 1: Q1 = 3 5 7 9, Q2 = 2
Iteration 2: Q1 = 5 7, Q2 = 2 3
Iteration 3: Q1 = 7, Q2 = 2 3 5
Iteration 4: Q1 = , Q2 = 2 3 5 7
You MUST use your Link/Stack code and extend it to this algorithm. This is by simply adding the function enqueue and dequeue. You may want to note that these may already be written and simply need this new name.
Assignment Grading Criteria – You must implement a working Queue with both enqueue and dequeue functions for grading, this is worth half credit. You must then use your queues in the Erasthones algorithm for the remaining half credit.
Additional Notes
The Sieve of Eratosthenes is one of the methods for creating a prime list. There are many more, and if you plan to do algorithmic programming, these are worth investigating – https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
Versions
An online search will yield a lot of implementations of the Sieve (it is used a lot). You should only use this code as a reference. Most of them use techniques that are more advanced and also use arrays as storage (which is not allowed for this assignment)
Coderbyte soution, simply have 2 embedded loops to perform the sieve – https://coderbyte.com/algorithm/generate-n-primes-sieve-of-eratosthenes-algorithm
Craig Rodrigues blog presents a very code-efficient version of the Sieve using some of the more advanced features of Javascript – https://www.craigrodrigues.com/blog/the-sieve-of-eratosthenes-in-javascript
CP-Algorithms does not present it in Javascript, but they do a great job of discussing the complexity and efficiency of various approaches to the solution – https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html
Even though you cannot use an array (as per instructions of assignment) to solve I thought you might like to see it solved in every possible language – https://rosettacode.org/wiki/Sieve_of_Eratosthenes
Eratosthenes was also one of the great thinkers of all time. The sieve is a simple algorithm, but Eratosthenes is also considered the founder of geography as a discipline and is also credited with a very accurate measurement of the earth’s circumference. Read about this here https://en.wikipedia.org/wiki/Eratosthenes (note: the fact the earth was round was well established in 276 BC and the ancient Greeks were calculating the circumference.)
