CS 201: Data Structures Homework 7

CS 201: Data Structures
Homework 7

1 Goals
The goal of this assignment is to get some practice thinking about how the complexity or efficiency
of different implementations of an ADT can affect our choices of which implementation to use. You
will also get some more practice thinking about how to use an implementation of the Stack ADT.
2 Setup and Requirements
This is a solo assignment. You may certainly discuss the assignment and how to get to your
final solutions with your classmates, but you must write your own solution. Also, make sure to
cite any sources used or classmates consulted! This is a written assignment, so no coding is required.
Your work should be typed, and must be a PDF. The easiest way to produce a PDF is to write
your text in a text editor or a word processing program, then export or print it to PDF. On a Mac
(such as the Macs in the lab), you can choose “Print” and then in the lower left corner there will
be a “PDF” button. Click on that button and choose “Save as PDF”. No format other than PDF
is acceptable. If you are familiar with LATEX, the PDF created from that is also a good option.
3 Your Assignment
1. Suppose you are creating a software application that allows prospective college students to
review and retrieve information about a group of colleges. You are going to use some implementation of the List ADT to store the list of colleges. In particular, you expect that your
users will often want to retrieve information about a schools with a particular ranking or
range of rankings (say they want to see information about the schools ranked in the range
15-30). It’s not often that a new school will need to be added to the list of rankings or that
a school will need to be removed from the list of rankings. Which implementation of the List
ADT should your program use and why? (1-2 sentences).
2. The registrar’s office has decided that it is time for a new software package to help manage
the registration process and they have asked you for help. In particular, they want you to
write an application that keeps track of the students on the waitlist for different classes. You
need to be able to add students to the waitlist and remove students from the waitlist. In
particular, you want to keep students in order on the waitlist so that the student who has
been on the waitlist the longest will be the first to be removed from the waitlist when a space
opens up in the class. You plan to use some implementation of the List ADT to complete
your task. Which implementation of the List ADT should your program use and why? (1-2
sentences).
3. Why might a developer choose to implement a particular program using a singly linked-list
over a doubly linked list? (1-2 sentences).
4. Suppose you have some mystery implementation of the Stack ADT that allows you to create
new Stack objects using the following line of code. Stack s = new MysteryStackImp().
CS 201: Data Structures
Homework 7
Layla Oesper
Fall 2017
This mystery implementation of the Stack ADT gives you access to all the standard Stack
methods including: peak(), pop(), push() which function as described in the Stack ADT
in your book. Suppose that I create a new Stack s using the following lines of code.
Stack s = new MysteryStackImp();
s.push("Schiller");
s.push("is");
s.push("Awesome);
Your job is to write some lines of code that will reverse the order of the items stored in s.
Hint: You may want to create one or more new Stacks to complete this task.
4 Submission and Grading
You’ll submit a single PDF to Moodle. Please name your PDF [your last name] HW7.pdf. So for
example, I would submit the fileOesper HW7.pdf.
This assignment is worth 8 points. Each question is worth 2 points and your responses will be
graded on both correctness and clarity. You may also not receive full credit if you do not submit a
PDF.