Labs
[ Home ] [ Handouts ] [ Schedule ] [ Labs ]

 

Lab 1

TO DO

  • Design a set of classes to implement a linked list that store strings in the information field.
  • Design a set of member functions (methods). Part of this lab is choosing which methods to design. Be sure to have enough to adequately manipulate the list when implemented.
  • The design should be done in pseudocode, but some thought must be give to the information that goes into and out of the methods.

Lab 2

Use your design from last week to implement a linked list. Your list should be as follows:

  1. The information in a node should be of type Address, which is a class you need to write with four data members, first name, last name, address, and telephone number. You can make all of the data members type String.
  2. The AddressList class should include the following methods:
    • add to the beginning, the end, and at a specified place (like 4th in the list)
    • delete from a specified position
    • a toString method
  3. You can hard code the data in the driver to test your list.

Lab 3

Purpose of this Lab: Become familiar with the Comparable interface

Writing a sorted list class for Objects:  For this lab, you will modify code to make it generic, so it will work with all classes, not just integers. You will find great help in your text on pages 167-174.

What to do:  Modify two files, then writing a driver to test.

  1. The OurList.java class
    • Download the OurList.java class and check to make sure it is working.
    • You will need to add a method to add sorted to the class. One way to do this would be to start with the addSorted method for integers we wrote in class.
    • Change the addSorted method so it will handle Objects. You do this by using the compareTo method instead a the < (less than) symbol.
    • The class will have to take as an argument an object of type Comparable.
  2. The TeleNum.java class
    • Download the TeleNum.java class, put it in the same package as the OurList class, then take a look at it. This class will need some modification.
    • It's purpose is to hold the name, address and phone number for each person in an address book. Your driver will put objects of this type in your sorted list.
    • You will need to make the TeleNum class implement the Comparable interface so it can be sorted.
    • Any class that implements the Comparable interface must have a compareTo method.
    • The compareTo method must be implemented so that it returns an int. The integer it returns should be:
      • zero if the two objects are equal
      • positive if the object that calls the method is greater than the argument
      • negative if the object that calls the method is less than the argument
  3. The driver
    • The driver should instantiate the list by calling its constructor, then call methods to put names, addresses, and phones numbers in the list.

Lab 4

Make your address book serializable

What is Object Serialization?

  • Object serialization is a way to make your data persistent after you exit the program.
  • It lets the system take care of all the details of saving to a file when the data you want saved is in a form more complex than a simple text file.
  • References to learn more about Object Serialization
    • Carrano/Prichard pages 199-200
    • Carrano/Prichard pages 736-739

What to do:  Modify the In-Lab program for an Address Book

  • Add a menu to the driver for your Address Book to ask the user if they want to enter names and phone numbers, save the address book to a file, or restore the address book so they can work on it.
  • Add the phrase implements Serializable to all the classes. (Don't forget the inner class, OurNode, nested inside the OurList class.
  • Write the code necessary to implement the save and restore options of your menu. Don't make this more difficult than it is. All the code you need is given to you in the references above. Just adapt it to your program. It goes in the driver.
  • Add a find option to the menu. The find method will be implemented in the OurList class.
    • The design of the find method is up to you. Most people want to find the address and/or phone number if they supply a name. You may want to implement it so that the user does not have to supply the complete name, spelled correctly. It is up to you. Extra credit will be given for bells and whistles.

What to turn in:

This program will be demonstrated in the lab on Thursday January 30. There is nothing to turn in. Your entire grade will be on showing that your program can save and restore data, and that it can find and return the phone number and address when given a name, or respond appropriately if the data does not exist.

Lab 5

The Inventory Program

In your text pages 194-200 is a description of an application program to maintain an inventory for a store that sells videos. You should read these pages thoroughly, but here is a brief overview of the problem.

You are to write an interactive program that will maintain the store's inventory of videos that are for sale. The inventory consists of a list of movie titles and the following information associated with each title:

  • have value: this is the number of videos the store has in stock
  • want value: this is the number of videos that should be in stock. (When the have value is less than the want value, more videos are ordered.)
  • waitList: this is a list of names of people waiting for the title if it is sold out.

Your book describes the input and output to this program as well as the the menu commands that the owner of the store would like the user to be able to execute.

First: Design, NOT code.

This is a complex problem. You must understand what the store owner wants in the program before you start to design a solution. The order of what you should do is as follows

  1. Understand the problem
  2. Design a solution
  3. Implement or code the solution

Understand the problem:
 

    Even the first part, understanding the problem is not trivial. If you have not already done so, read the pages in your book several times to be sure you understand what is to be done. If, on the first reading it seems hopelessly complex, you must just read through it again and again, taking notes to help you remember and understand the problem, and the partial solution your book is proposing.

The Classes you will need

    In addition to the Exception and Interface classes written by Carrano/Prichard, you will need these classes:

    1. ListReferenceBased and SortedList; furnished by Carrano/Prichard. Make sure you know what methods are available and what their arguments and return types are.
    2. StockItem class. The data structure for this class is given in your text. You will have to decide what methods will be needed in it.
    3. Inventory class. The data structure for this class will be a linked list of type SortedList. You will have to decide on what methods are needed.

Design the solution:

  • When you design a solution remember you have two basic strategies to use:
     
    • Top Down Design used when you are designing methods;
       
    • Object Oriented Design used when you are designing the classes and data structures you want to use. You book helps you a great deal in this part of the design for this problem.
  • You should probably design the StockItem class first.
    • You will need constructors and get and set methods. As you proceed with your design, you may discover other methods that you need.
    • To implement the waitList:
      • You will need a Person class to hold the names of people in the wait list.
      • Make sure all the methods that deal with the wait list go in the WaitList class. This includes adding to the wait list, changing it, or deleting items from the wait list
      • The Stock Item class is a client of the WaitList class. It creates an object of type WaitList then manipulates it.
    • Your text gives you quite a bit of help designing both the StockItem class and the Person class on page 197-199
  • The Inventory class will contain all the methods that deal with the LIST of StockItems.   To deal with the list, you will call methods from SortedList and ListReferenceBased, as well as methods from the StockItem class.

For your design you should have:
 

  1. The design of the StockItem and Inventory classes. For each class this should include:
    • the attributes (i.e. the data members or instance variables)
    • the first line of each method along with the pre and post conditions
  2. Pseudocode of how you intend to handle each of the menu items. This should include (but not necessarily be limited to) the methods you will need to call to carry out the menu choices.

Implement the solution

Java code you can download

Hand in

 Because there is so much code, the best way to turn your code in is to put it on a floppy disk. Make sure your name is on the disk.

Lab 6

The Eight Queens Problem

Do programming problem #1, page 239 of Carrano.
Carrano/Prichard code

Hand in: A complete set of Java code for all the classes and member functions to implement the Eight Queens Problem as described in the text and a sample run demonstrating that the program works.

Lab 7

A Simulation Problem

    Do problem # 8 on page 331 of the Carrano/Prichard book. Omit the detail given on page 332 that begins "As ridiculous as it may seem". Otherwise, do the problem exactly as it is given.

    You will probably want to use a short data file to test your program, but use this data file for the run whose output you turn in.

Lab 8

Background
This is a lab that was presented at the SIGCSE conference I attended last February. It was developed by David Levine at St. Bonaventure University.  As you no doubt know, if you double the size of the data set that you give to a quadratic algorithm O(n2), it will do four times the work; by contrast, an O(n log n) algorithm will do a bit more than twice as much; and, a linear algorithm will do only twice as much work. As you also know, the characteristics of the input data set can affect the expected performance of many of our sorting algorithms.

Objective
The object of this lab is for you to be familiar enough with the behavior of the different sorting algorithms to match an unknown algorithm's performance with the algorithm name.
The sorting algorithms you will be working with this week include (in alphabetical order): bubbleSort, insertionSort, mergeSort, quickSort, selectionSort, and shellSort.

Copy, then unzip the file

  • Copy the file sortdetective.zip to a location on your account.
  • Unzip the file. (It contains subdirectories, as well as dozens of files)
  • You will have to run this GUI program from the commnad line. So open a window with the DOS command line.
  • Change your current directory to the sortdetective folder that was created by unzipping.
  • Type:     java SortDetective at the shell prompt or on the Windows DOS command line.
  • If you have problems getting it to run, it is probably because the operating system cannot find either the the java.exe program in the JKD1.3.1/bin directory, or because it cannot find the path to wherever you have stored the SortDetective.

Become familiar with the program

    Play with the program a bit. Notice:

    • The button names do not give any indication which sort they will execute.
    • When you want to create a different size list, or a list that is sorted differently you must click the "Create The List" button
    • If the amount of time it takes to sort your list is zero, the list is too small for the time to be measured.

What to do

  1. Make a chart that summarizes the information you have about the characteristics of each of the sorting algorithms you will be working with. This chart should be a summary, but it should contain all pertinent facts.
  2. Devise a plan which will enable you to match the particular algorithms to the button names.
  3. Execute your plan, taking careful notes as you go.
  4. Be aware that some of the slower sorts we looked at can take ten or fifteen minutes or more to sort very large lists; also, that some of the faster sorts will not show their true characteristics unless the list is large. Plan accordingly.

Hand in

  1. Hand in your summary chart.
  2. Show how you matched the sorting algorithms with the Greek names.
  3. Give the rationalization that justifies your matching. A correct "guess" will earn you no credit. You must justify why alpha was WhateverSort.
  4. Since there is no coding in this, you should expect that a significant portion of the lab grade for this lab will be determined by the quality of the writing of the report. This includes the completeness of the report, the clarity (and grammar) of the writing, and general presentation.
  5. You should strive to make your report brief and concise but also complete. Do not confuse length with completeness.
  6. Your report needn't detail every experiment you ran. Rather, it should give sufficient information to justify your conclusions. It is possible to write a very short report that is completely correct if your experiments are well-chosen.

 

Lab 9 - C++ Problems

Problem 1

 No Nickels Problem:  Find a dynamic programming solution for the following problem of making change with pennies, dimes and quarters only (no nickels):  For a given amount of change needed, calculate the fewest number of coins needed, e.g. 6 cents = 6 pennies, 27 cents = 1 quarter + 2 pennies, 30 cents = 3 dimes, etc.  Write a C++ program that prompts the user for an amount of change and returns the solution involving the fewest number of coins.

Problem 2

Minimum Spanning Trees: Implement a MST algorithm in C++, following the pseudocode supplied in Chapter 23 of the textbook.  You may use either Prim’s or Kruskal’s algorithm.  The input to the program will be an undirected weighted graph in adjacency list form.  The vertices are labeled 1 through n.  Your program should prompt for an input text file that contains the graph in the following form:

 20        - this is the number of vertices
4         - this is the number of edges
1 3 10    - indicates an edge between vertex 1 and vertex 3 of weight 10
2 9 5     - indicates an edge between vertex 2 and vertex 9 of weight 5
...

 The output should be a list of edges that make up the MST as well as the total weight of the MST.  You need only find one MST for the input graph.