CS 301 Labs

Lab 1 August 31 - September 2

Tuesday Lab -- Introduction and Writing your Web page

1. Check to see if your esus account is up and running. You may have to get your username and password from Jeanette or the TA.
2. Become familiar with the class web pages. A class like this has information on several different web pages, all linked together. A lot of the information you will want to read only once, but you will need to read it once, and be able to find it again if need to.
   • On your browser bring up the class homepage. It's URL is
     http://www.cs.montana.edu/courses/301/
   • Follow the links until you are comfortable that you know where to find the following information:
     • how to set up a computer at home so you can receive lectures,
       You have to download the plugins even if you have the disk with the lectures on it.
     • the schedule for
       1. readings you should be doing,
       2. on-line theory lectures,
       3. programming lectures, and
       4. programming homework.
     • how exams will be handled,
     • the required books,
     • how to email your instructors,
     • general information about the labs, and
     • the lab schedule, including the specific lab for this week.
   • Ask Anne if you have any questions about any of the information on the pages.

   2. Writing Your Web Page

   • Click on the on-line lecture Writing a Web Page about writing web pages
   • Read the page, then follow some of the online help and manuals, deciding which is most valuable for yourself.
   • (Do not listen to the lecture now unless you have headphones)
   • Look at the source of a few web pages. (so you are sure you know how)
   • Do as much of the activity under the Getting Started portion as you wish. If you do it now, we can help you if you have trouble.

   ---

For Thursday, September 2

You will not have to turn anything in for this lab.

1. Publish your web page on esus and show it to Anne
   • You will need to transfer your html file to your account in esus using FTP or another file transfer program. The TA will help you do this if you need help
   • If you choose to putlish your page somewhere else, you must email Anne and the TA the URL where it can be found. We will be making a class web page where students can look at each other's web pages.

2. Become familar with theC++ enviroment
   

3. Create a few simple C++ programs
   • Type in the "Hello World" program, compile and run it

Summary of homework for the first week

1. For the Theory part of the course
   • Read the Introduction chapter and Chapter 1 in Brookshear
   • Listen to the Getting Organized and Data Storage lectures on the web or disk.
2. For Lab
   • Finish your web page and get it published
   • Work on getting the computer you are going to use set up to receive the on-line lectures (so if you have problems, we can help)
   • Read Chapter 1 in the Lafore text
   • Get started on the C++ programming from Chapter 2 of Lafore (below).

Week 2: Basic C++ Programs

Due Tuesday, September 7, 2004

• Do Exercises #1 and 3 on page 71 in Lafore. Since these are starred exercises, the answer can be found in Appendix G. It is best not to look at the answer until you have tried to do the program yourself. But, by all means, look at it if you get stuck or frustrated.
• Do Exercise #6 on page 62 in Lafore

Due Thursday, September 9, 2004

Hand in:

Week 3: Loops and Decisions

Do Tuesday September 14

For practice:
This does not need to be turned in, but you should do these problems for practice. Other problems later will build on them. They are coded in the back of the Lafore book if you need help.
1. On page 126 of Lafore, do #3. In this problem, you must use getche( ) to read in a digit and store it in ASCII code in RAM. You should read a character, convert it from ASCII to the binary number system by subtracting '0' or 48. For the second digit, you must multiply the first by ten before adding the second digit. You can tell when you have read the last digit in a number when the character read is a space.
2. Do # 4 on page 127 in Lafore.
To hand in
1. Your history instructor gives three test worth 50 points each. You can drop one of the first two grades. The final grade is the sum of the third grade plus the best of the first two grades. Write a program that inputs three test grades, then calculated the final letter grade using the following cut-off points.

   		>= 90         A
   		< 90, >=80    B
   		< 80, >=70    C
   		< 70, >=60    D
   		< 60          F 

2. Nested Loop Problem: Write a program to print a triangle composed of a symbol. The number of lines in the triangle and the symbol should be entered as input from the keyboard. For example, if the input values are 7 and #, the output is as follows:

   		      #
   		     ###
   		    #####
   		   #######
   		  #########
   		 ###########
   		############# 

Due: These two problems are due on Thursday, February 3. You need to hand in a hard copy of your source code and the result of executing your program.

---

Do Thursday September 14

This will be due Tuesday of next week.

To hand in

1. Write a program to determine if the digits in a three-digit integer are all odd, all even, or mixed. You program should prompt the user to input a three-digit number and echo-print the number. If the digits in the number are all odd, write "This number contains all odd digits". If the digits in the number are all even, write "This number contains all even digits". If the number contains both odd and even digits, write "This number contains both odd and even digits". Use integer division and modulus to access the digits in the number.
2. Do #7 on page 127 in Lafore.
3. Do #12 on page 129 in Lafore.
4. Extra credit: Do #10 on page 128 in Lafore

Week 4:

Do Tuesday September 21

• Do #2 on page 158 in Lafore. The answer to this problem is in the back of the book, so does not have to be turned in.
• Do #4 and #6, page 159 in Lafore.

Do Thursday September 23

• Do #8 and #12 on pages 159-160 of Lafore.These should be turned in by next Tuesday
  

Week 5: Functions

1. Do #3 on page 212 in Lafore. The answer to #3 is in the back of the book, so #3 does not have to be turned in.
2. Do #5 on page 212
3. For practice using functions with structures do #6 on page 212. This will involve doing #9 and #11 from Chapter 4 in Lafore (page 159). After you do #9 and #11 from page 146 then complete #6 on page 212. You will not need to turn #9 and #11 in.
4. Do #8 and on pages 213 of Lafore.
5. Do #12

Week 6--Using Functions

1. Write a program that will read in a length in feet and inches and will output the equivalent length in meters and centimeters. Use at least three functions: one for input, one or more for calculating, and one for output. Include a loop that lets the user repeat this computation for new input values until the user says he or she wants to end the program.

   There are 0.3048 meters in a foot, 100 centimeters in a meter, and 12 inches in a foot.

2. Write a program that plays the game of "guess the number" as follows: Your program chooses the number to be guessed by selecting an integer at random in the range 1 to 1000. The program then types:

   		I have a number between 1 and 1000.
   		Can you guess my number?
   		Please type your first guess.

   the player then types a first guess. The program responds with one of the following:

   		1. Excellent! You guessd the number!
   		   Would you like to play again (y or n)?
   		2. Too low.  Try again.
   		3. Too high.  Try again.

   If the player's guess is incorrect, your program should loop until the player finally gets the number right. Your program should keep telling the player Too high or Too low to help the player "zero in" on the correct answer.

3. In cold weather, meteorologists report an index called the wind chill factor,that takes into account the wind speed and the temperature. The index provides a measure of the chilling effect of wind at a given air temperature. Wind chill may be approximated by the formula

   

   where

   v = wind speed in m/sec
   t = temperature in degrees Celsius: t <= 10
   W = wind chill index (in degrees Celsius)
   

   Note that the temperature must be less than 10 degrees before this formula is valid.

   Write a function that returns the wind chill index. Your code should ensure that the restrictions on tempture is not violated. The function should be restricted to one task, returning the wind chill index. Everything else should be done in the main program, perhaps calling other functions to do the I/O, etc.
   

   
   
   

   Week 7: Objects and classes

   October 12
   This will be due Tuesday, October 19
   • Do #2, 4, 6, 9, 11 on pages 259-262 in Lafore. The answer to #2 is in the back of the book, so it does not have to be turned in.

     For #6 you will need a Date class Here is one simple version of the Date class. It does not have a constructor, which you should write. You can modify it (by writing the constructor), or write your own. An object of type date should be one of the data members of in the Employee class.

     class Date                   //class declaration
        {
        private:
           int month;             //member data
           int day;
           int year;
        public:
           void getdate()         //member functions
              {
              char slash;
              cin >> month >> slash >> day >> slash >> year;
              }
           void showdate()
              {
              cout << month << '/' << day << '/' << year;
              }
        };

Week 8: Using Arrays

• In Lafore, on page 314 , do #3. The answer to this exercise is in the back of your book, so you do not need to hand it in. Be sure to note how to create an array of objects.
• In Lafore, page 314, #6 asks you to modify the cardaray.cpp program so that it deals four hands of bridge. Do this by:
  • Write a constructor for the Card class
  • Write the set function for the Card class that is called in the main( ) in the book
  • Write a class Deck whose data member is an array of Cards and the member functions include a constructor which puts the cards in the deck, a function to shuffle the cards, and a function to output the contents of the Deck.
  • Write a driver to:
    • Instantiate an object of type Deck; this will automatically call Deck's constructor
    • Output the ordered deck
    • Call the function to shuffle the deck
    • Output the shuffled deck
    • Deal, then display the bridge hands

Week 10: 2-D Arrays

• The Knight's Tour is a classic chess problem which was studied (and probably solved) over 1000 years ago. The famous mathematician, Euler, published the first rigid mathematical analysis of the problem in 1759.
• The problem is this: Can the chess peice called the knight move around an empty chessboard and touch each of the 64 squares once and only once?
• The purpose of this problem is not to find a solution (beyond the scope of this course) but to program the problem, and see how many moves the knight makes before he cannot move anymore. You can use random numbers to tell the program the next move, or enter them manually.
• How to begin
  • The kinght makes L-shaped moves; over two in one direction and then over one in a perpendicular direction.
  • Thus, from a square in the middle of an empty chessboard, the knight can make eight different moves (numbered 0 thourgh 7) as shown in the figure
    1. Draw an 8-by-8 chessboard on a sheet of paper and attempt a Knight's Tour by hand. Put a 1 in the first square you move to, a 2 in the second square, a 3 in the third, etc. Before starting the tour, estimate how far you think you will get, remembering that a full tour consists of 64 moves. how far did you get? Was this close to your estimate?
    2. I will give you some help with possible data structures to use. You are free to either use them, to to do it your own way. There are certainly other ways for you to store the data necessary to start this problem.
       • The chessboard Use a 2-D array, 8 X 8.
       • The moves since there are eight possible moves, we can describe them in terms of both their horizontal and vertical components, using a 1-D array for each.
         • For example, a move of type 0 consists of moveing two squares horizontally to the right and one square vertically upward.
         • Move 2 consists of moving one square horizontally to the left and two squares vertically upward.
         • Horizontal moves to the left and vertical moves upward are indicated with negative numbers.
       • The horizontal array stores the horizontal part of the move. The vertical array stores the vertical part of the move The subscript is the move type.
         horizontal[0] = 2         vertical[0]= -1
         horizontal[1] = 1         vertical[1]= -2
         horizontal[2] = -1        vertical[2]= -2
         horizontal[3] = -2        vertical[3]= -1
         horizontal[4] = -2        vertical[4]= 1
         horizontal[5] = -1        vertical[5]= 2
         horizontal[6] = 1         vertical[6]= 2
         horizontal[7] = 2         vertical[7]= 1
         
       • Let the variables currentRow and currentCol indicate the row and column of the knight's current psoition. To make a move of type moveNumber where moveNumber is between 0 and 7, your program uses the statements
         currentRow += vertical[moveNumber];
         currentCol += horizontal[moveNumber];
       • Keep a counter that varies from 1 to 64. Record the lastest count in each square the knight moves to.
       • Remember to test each potential move to see if the knight has already visited that square, and, of course, test every potential move to make sure the knight does not land off the chessboard.
       • You should initialize the 2-D array to zeros, then when the knight lands in a square, change the zero to the count. When the knight can no longer move, print out the 2-D array, showing the board with the moves the knight did make.
    Here is one solution, in case you are interested. I do not expect your program to find solutions and your output will not be graphical like this one. You can start the knight in any square you like.
    

Week 11: Overloading Operators

A machine with 32-bit integers can represent integers in the range of approximately -2 billion to +2 billion. This fixed-size restriction is rarely troullesom. But there are application in which we would like to be able to use a much wider range of integers. For instance crytolopy requires multiplying 200 digit integers. This was what C++ was built to do, namely, create powerful new data types.

Consider class HugeIntfound in the following files.
hugeInt.h
hugeInt.cpp
HugeIntClient.cpp
Study the class carefully then be sure you know the answers to the following questions. If you can't figure out the answer, ask someone in the class, or email me. You cannot do the assignment if you do not understand every bit of the code given.

In the header file
1. How many digits in a number can this HugeInt class handle?
2. There are two constructors (actually three). Two of these are called conversion constructors. (Read about conversion constructors in Lafore p. 345-347). What is the job of each constructor?
3. The plus operator is overloaded three times; what is the purpose of each function?
   In the definition of function file
4. In the second constructor, what is the second for loop doing? What is the -'0' doing?
5. In the second addition function, what are the data types for the + operaot? Remember, operands must be of the same type.

What to do
After you understand the code, have copied it to your system, compiled it to be sure it runs (it did for me),

1. overload the * multiplication operator for the hugeInt class,
   • to do this, you put the prototype(s) in the class header file,
   • the definitions of the functions in the class function definition file.
2. overload the relational and equality operators (==, != >, <)
   • these should return a bool
3. test you code so you are sure it runs correctly.

Week 12: Inheritance

1. From the Lafore book, on pages 424 and 425, do #1,3, and 4. The solutions for # 1 and 3 are in the back of the book, but you should try to do them on your own before looking at the solutions. Number 4 builds on 1 and 3.

   The next part is still under construction...I am trying to add notes to help you understand what is wanted

2. Many programs written with inheritance could be solved with composition instead, and vise versa.
   • Remember that inheritance is characterized by is a relationships, while composition is characterized by has a relationships.
   • With composition, a class may have other classes as data members. For example, we looked at the Room class, which had as data memabers length and width, both of which were of data type Distance.
   Consider the relative merits of these approaches in the context of the Point,   Circle,   Cylinder   class hierarchy given.
   • Rewrite these programs using composition rather than inheritance.
   • After you do this, reassess the relative merits of the two approaches for both the Point, Circle, Cylinder problem and for object-oriented programs in general.

Week 13--Practice Programming and Logic

A guessing game: Bagels

You are to write a program that plays a game known as Bagels. It is a variation of Mastermind. You may want to scroll down for sample output which explains how the game is to be played and explains its rules before reading about the assignment.

The Assignment

• Your program is to ask the user whether or not to display instructions, only showing the instructions if the user responds yes. It also must be able to play the game several times with the user.

• Since the user is to play with many digits at a time, you cannot use a simple integer for storing the correct answer and the user guesses. You will have to store the number as an array of digits to allow it to be as large as 50 digits. You may store the answer either as an array of 50 digit characters (i.e., an array of characters) or as 50 actual digits (i.e., an array of integers).

• Some simple error checking should be done. In reading a user guess, your program must skip any leading spaces and must reject any response that has too few or too many characters.

• You are not required to make sure that the user types digit characters. If the user types other characters, these will simply be considered wrong answers.

• To generate the number to be guessed, you will need a random number generator.

• You may keep or discard the rule about the zeros

• If you want, you may omit or rephrase some of the instructions to the user ( I realize they are long), but you should not change the rules (without asking me), and the interaction with the user should be the same.

The Game

This version of the Bagels game does not have a limit on the number of guesses the user can make.

Here is a sample output from execution.

	Welcome to Bagels.
	Do you want instructions?
	Y or N --> y

	********** you may shorten or rephrase these instructions *****************
	This is the game of Bagels.  You may know it as mastermind,
	but we use digits.  In Bagels, I will think of an n-digit
	number that you will try to guess.  You will specify what
	value of "n" you wish to work with for each game.  
	
	After each guess I will give you some hints as to how close you 
	are to getting the answer right.  If you have a digit right and 
	in the right position, I will say FERMI.  If you have a digit
	right but in the wrong place, I will say PICA.  
	
	So if the number is 123 and you guess 329, I will report FERMI PICA.  
	If the number is 123 and you guess 312, I will report PICA PICA
	PICA.  Each digit will match only once.  So if the answer is
	999 and you guess 912, I will report FERMI.  If the answer is
	912 and you guess 999, I will also report FERMI.  Notice that
	I might report several FERMIs or PICAs in one message.
	I will list all of the FERMIs first and then all of the
	PICAs.  So if the answer is 12345 and you guess 31245, I will
	say FERMI FERMI PICA PICA PICA.  So don't assume anything
	from the order of my clues.

	You will specify the number of digits you want to work with.
	Obviously the game is not worth playing for 1 or 2 digits.  I
	will set the upper limit at 50 digits.  Also, I will not include
	any zeros in my numbers.  It makes for strange situations.
	*********end of instructions you may shorten ************************

	I will require from you that you give me exactly 'n' digits
	each time as a guess.
	
	How many digits do you want to work with this time? 4
	I'm thinking of a number . . .
	Guess --> 12345678
	That guess was too long, try again
	Guess -->           123
	That guess was too short, try again
	Guess --> 1234
	PICA PICA 
	Guess --> 4356
	FERMI PICA 
	Guess --> 4178
	PICA PICA 
	Guess --> 7495
	FERMI FERMI PICA 
	Guess --> 7499
	FERMI FERMI 
	Guess --> 7744
	FERMI PICA 
	Guess --> 7455
	FERMI FERMI FERMI 
	Guess --> 7451
	FERMI FERMI FERMI 
	Guess --> 7452
	You got it in 9 guesses.
	
	Do you want to play again?
	Y or N --> y
	How many digits do you want to work with this time? 4
	I'm thinking of a number . . .
	Guess --> 1234
	PICA 
	Guess --> 4567
	PICA 
	Guess --> 3789
	FERMI PICA PICA 
	Guess --> 2698
	FERMI PICA PICA 
	Guess --> 3968
	FERMI PICA PICA PICA 
	Guess --> 3896
	You got it in 6 guesses.
	
	Do you want to play again?
	Y or N --> n
	OK, your average score was 7.5 tries per game.

Week 14--Linked Lists

Write a clast LList to implement the Linked List Data structure. Your class should:

1. Enable a client of the class to manipulate a list of integers. The client should not be aware of how the list is being stored. (i.e. the implementation details are hidden from the client)
2. Include as much functionality as you can; the important thing is to get it running, test it, then include additional functions. Some suggestions for functions are:
   • insert at the front of the list and/or the end
   • delete at the front and/or the end of the list
   • insert keeping the list in order
   • delete a specific value
   • display the list
   • output the number of items in the list.
   • You may think of others
   • The more functionality, the better the grade
3. You may use any of the code I gave you in class, or any of the code in the book. You should understand how any code you use is working!
   It is always a good idea to reference any code you did not write yourself. Just indicate where the code came from.
4. You must also write a client (driver) to test each function.
5. The I/O might looks something like this:

   		What would you like to do?
   		1) Insert an integer at the front of the list
   		2) Insert an integer at the end of the list
   		3) Delete an integer at the front of the list
   		4) Delete an integer at the end of the list
   		5) Insert an integer into tthe proper place to keep the list in order
   		6) Delete a specific integer
   		7) Output the list  

   For each item in the menu, the driver should prompt the user for input, the do the desired operation.