CS230 Assignment 6

Assignment 6

 

DUE: See Schedule

 

LOGISTICS

  • Shared Google Doc for finding/recording partners.
  • For both Tasks you are required to work with a partner as part of a two-person team. You are required to work with a partner you have not worked with in a previous assignment! Please consult the course collaboration policy for futher details.
  • How to turn in your assignment without losing 20% of the grade:
  • First, submit the Cover page
  • To your account on the CS Server (in your public_html/cs230-assignments/ps06) folder upload a zip file of all materials.
  • To Gradescope, submit the files LinkedQueue.java, CircularArrayQueue.java and a text file bigO.txt with your answers to Task 2.
 

Learning Goals

  • Gaining experience of multiple implementations of the same interface
  • Debugging programs that require understanding of pointers
  • Understanding the Big-O complexity at the level of individual statements and methods
  • Work with the javafoundations package
 

Task 1: Two Implementations of Queue Interface (Work in Pairs)

Before starting this task make sure you review the handout on Queues and read section 15.1-15.5 of the textbook.

  • Design your solutions on paper before you start programming on a computer. Take a photo of a sketch/diagram of this task and uploaded to the assignments/ps06 folder on cs account (do not email). Do that 3 days before the assignment is due.

In class we discussed one full implementation of the Queue interface (ArrayQueue) and two partial implementations. For this task, you are asked to complete and test the partial implementations: LinkedQueue, CircularArrayQueue.

For your convenience we have started a QueueImplementations.zip template. It includes the beginning of a driver aimed to show that your implementation works correctly. You need to complete it and also provide javadoc documentation for the classes you will edit.

 

Task 2: Find the running time of statements in a method (Work in Pairs)

Before starting this task make sure you review the handout on Efficiency of Algorithms and read Chapter 12 of the textbook.

Consider the following method that removes a CD from a linear collection (e.g. array).

Assume that the collection has n CDs to start with. Answer each of the questions below. Provide your answer by writing a sentence for each Question, and then explaining the Big-O notation associated with the relevant statement. Note: If you find any of the Questions ambiguous (that is, it may mean two different things and you are not sure which one is the correct interpretation), explain why and give your answer for each alternative.

Write your answer on a text .txt file (not a Word .doc or other special format, just plain text) and submit it in the proper assignment folder.

code to remove a CD from an array

Good luck!