Homework 1

DUE: Tuesday 5/26 (by 11:59pm)

Once fully tested, submit your C++ source file(s) by zipping them up and emailing the ZIP (or tar) file to me.

  1. Your program will read two input files from the command-line arguments. The two input files are a keyword file and a search file. Your program must produce one output file, also specified as a command-line argument. The format of the command line is as follows: 
    2. keyword_search keywords.txt search-file.txt results.txt
  2. Both input files will contain sequences of words, separated by whitespace. You may assume there will be no characters in the files other than whitespace and lowercase alphabetic characters. You may also assume the keyword file contains no repeated words.
  3. As an example, here's a sample keywords file: 
    4. apple pear banana cherry orange grapefruit
  4. Your program must determine the number of times each keyword exists as an exact match in the search file. Your program must output the keyword strings in alphabetical order, with one keyword and its number of occurrences on each line of output.
  5. So, consider the following search file: 
    6. once upon an orange morning the grapefruit went to buy an apple but
only found a pear actually several pears and an orange
the grapefruit
bought a pear and another pear but then the grapefruit wanted an apple
anyway so the grapefruit went to the banana and orange store
there the grapefruit found
applesauce and once again an orange but again did not find an apple the
grapefruit went to orange lane where the rest of the orange family was
waiting
  6. The output file would show: 
    7. apple 3
banana 1
cherry 0
grapefruit 6
orange 6
pear 3
  7. Following this output, the program should output a blank line followed by the keyword that occurs most often. If there are several such keywords, all must be displayed.
  8. Continuing the output of the above example: 
    9. Max keyword occurrences = 6
Number of max keywords = 2
Max keywords: grapefruit orange

Homework 2

DUE: Monday 6/8 (by 11:59pm)

Once fully tested, submit your C++ source file(s) by zipping them up and emailing the ZIP (or tar) file to me.

  1. A typical Sudoku puzzle is a 9x9 grid with nine 3x3 subgrids. Each row of a Sudoku puzzle has each digit 1-9 exactly once. Likewise, each column has each digit 1-9 exactly once. Further, each 3x3 subgrid within the 9x9 grid has each digit 1-9 exactly once.
  2. More generally, we're given a positive integer, n, which is usually 3. This integer is used to form an n2xn2 grid. Some of these grid locations have initial numbers in them, each number in the set {1, 2, ... , n2}.
  3. Here's an example puzzle: 
    4. +---+---+---+
|.45|...|.7.|
|8..|.29|6.3|
|.6.|15.|..8|
+---+---+---+
|.2.|6.5|9..|
|.57|...|84.|
|..3|7.4|.1.|
+---+---+---+
|9..|.38|.6.|
|7.2|54.|..1|
|.3.|...|28.|
+---+---+---+
  4. The key requirement is that each row, each column, and each of the n×n non-overlapping subgrids (starting with the upper left corner), must have no repeated values.
  5. Thus, in the sample puzzle above, the upper left-hand square (row 0, column 0) cannot be a 4, 5, or 7 because those numbers already exist in the given row; similarly, the square cannot be a 7, 8, or 9 because those numbers already exist in the given column; finally, the square cannot be a 4, 5, 6, or 8 based on the subgrid. Given these constraints, the possibilities for the square are 1, 2, or 3.
  6. While you don't need to solve the Sudoku puzzle, your job is to design, implement, and test a class to represent a Sudoku puzzle and to validate the placing of certain numbers in the grid based on the row, column, and subgrid tests noted above.
  7. You must download and use this Sudoku.h file, which is the start of a class declaration. You may not change the declarations of the public member functions in this class, although you may add more functions. You must provide private member variable(s).
  8. Further, you must implement the member functions (in Sudoku.cpp) to meet the design requirements specified in the file.
  9. Write a main function that tests your class implementation. You may use this sudoku_main.cpp file and expand it to include other tests. Be sure you do not change the prototypes of the class member functions provided!
  10. Here are a few required conventions of Sudoku.h:
    1. Row numbering will run from 0 to n2-1 (e.g. from 0 to 8 when n is 3).
    2. Column numbering will also run from 0 to n2-1.
    3. The nxn subgrids will be indexed as well, with subgrid rows running from 0 to n-1 and subgrid columns running from 0 to n-1. For example, when n is 3, subgrid (1,2) is the middle block on the right-hand side (with its upper left-hand corner being grid entry (3,6) and its lower right-hand corner being grid entry (5,8)).

Homework 3

DUE: Wednesday 6/17 (by 11:59pm)

Once fully tested, submit your C++ source file(s) by zipping them up and emailing the ZIP (or tar) file to me.

Similar to what we've done in class, your job for this assignment is to implement a series of templated functions for the templated Node<T> class shown below: 

template <class T>
class Node {   // each Node object is part of only one list
public:
  T value;
  int position;   // numeric index (0..n-1) of where the Node object is in the list
  Node<T>* next;
  Node<T>* prev;
};

These functions must not be member functions of any class.

  1. Create a file called llist.h with the Node<T> class above. Be sure to add the required include and using directives. Note that you may not change the declaration given above, but you may add constructors if you wish.
  2. Add the following function to llist.h (this function prints the given string, s, then prints the list both forwards and backwards, including the position of each element): 
    3. // prints the list forward and backward (to help test next and prev pointers)
template <class T>
void print_list( string s, Node<T>* head )
{
  cout << s;

  if ( !head ) {
    cout << " <empty>" << '\n';
  }
  else
  {
    Node<T>* p = head;
    Node<T>* q = 0;

    // forwards
    while ( p ) {
      cout << " [" << p->position << ']' << p->value;
      q = p;
      p = p->next;
    }

    cout << " <--->";

    // backwards
    while ( q ) {
      cout << " [" << q->position << ']' << q->value;
      q = q->prev;
    }
  }

  cout << endl;
}
  3. Add a templated add_to_front() function with the following prototype that adds an element to the front of the list: 
    4. template <class T>
void add_to_front( Node<T>* & head, const T& value )
  4. Add a templated add_to_back() function with the following prototype that adds an element to the back of the list: 
    5. template <class T>
void add_to_back( Node<T>* & head, const T& value )
  5. Add a templated remove_each() function with the following prototype that removes each node in the list that has the specified value (and returns the number of elements removed): 
    6. template <class T>
int remove_each( Node<T>* & head, const T& value )
  6. Add a templated ordered_merge() function with the following prototype that creates (and returns) a list that contains all values from the original two sorted lists in merged sorted order (you can assume that the two lists given by head_of_list1 and head_of_list2 are already in sorted order): 
    7. template <class T>
Node<T>* ordered_merge( Node<T>* head_of_list1, Node<T>* head_of_list2 )
  7. Create a file called llist_main.cpp that has your main() function in which you'll test your linked list functions. Some initial code is given below, but please add code (to the end) to fully test your functions. 
    8. #include <iostream>
using namespace std;

#include "llist.h"

int main()
{
  Node<int> * head1 = 0;   // list is initially empty
  print_list( "LIST (should be empty):", head1 );

  add_to_front( head1, 300 );
  add_to_front( head1, 200 );
  add_to_front( head1, 100 );
  add_to_back( head1, 300 );
  add_to_back( head1, 400 );
  add_to_back( head1, 500 );
  print_list( "LIST 1 (should be in sorted order):", head1 );

  int n = remove_each( head1, 300 );
  cout << "Removed " << n << " elements (should be 2)" << '\n';
  print_list( "LIST 1 (should be 4 elements in sorted order):", head1 );

  Node<int> * head2 = 0;
  add_to_front( head2, 350 );
  add_to_front( head2, 250 );
  add_to_back( head2, 400 );
  add_to_back( head2, 450 );
  print_list( "LIST 2 (should be 4 elements in sorted order):", head2 );

  Node<int> * head_sorted = ordered_merge( head1, head2 );
  print_list( "LIST 3 (combined sorted order):", head_sorted );

  remove_each( head1, 100 );
  remove_each( head1, 200 );
  remove_each( head1, 400 );
  remove_each( head2, 250 );
  remove_each( head2, 350 );
  remove_each( head2, 450 );

  print_list( "LIST 3 (should be same as above):", head_sorted );

  return 0;
}

Homework 4

DUE: Tuesday 6/23 (by 11:59pm)

Once fully tested, submit your C++ source file(s) by zipping them up and emailing the ZIP (or tar) file to me.

Write an interactive hangman game with rules and specifications as described below.

  1. Your hangman program (called hangman.cpp) begins by reading a file specified on the command-line. This file contains words or phrases. For example: 
    2. computer
giraffe
CSCI-1200: data structures
Sarah Palin for president!
David Letterman for president!
R2-D2 for president?
  2. Read each line from the file. Convert all letters to lowercase. Keep whitespace and punctuation.
  3. Store each line (i.e. each potential puzzle) in a vector.
  4. Start the game by randomly selecting a puzzle from the vector. Show the puzzle by replacing each letter with an underscore character, leaving all other characters unchanged, as in: 
    5. Here's the puzzle:
_ _ _ _ - 1 2 0 0 :   _ _ _ _   _ _ _ _ _ _ _ _ _ _
  5. Allow users to repeatedly guess letters (HINT: use getline() and ignore everything but the first letter). If a guessed letter is in the puzzle, fill in all occurrences and show the puzzle again. If not, the player is that much closer to being hanged! Here's an example of how your program should operate: 
    6. Here's the puzzle:
_ _ _ _ - 1 2 0 0 :   _ _ _ _   _ _ _ _ _ _ _ _ _ _

Guess a letter: t
Good guess!
_ _ _ _ - 1 2 0 0 :   _ _ t _   _ t _ _ _ t _ _ _ _
guessed letters: t

Guess a letter: k
Sorry, no 'k'
_ _ _ _ - 1 2 0 0 :   _ _ t _   _ t _ _ _ t _ _ _ _
guessed letters: k t

Guess a letter: c
Good guess!
c _ c _ - 1 2 0 0 :   _ _ t _   _ t _ _ c t _ _ _ _
guessed letters: c k t

...
  6. Use a set to store the individual letters that have been guessed. Show the guessed letters (regardless of whether they're in the puzzle or not) in alphabetical order.
  7. When a user guesses six incorrect letters, the player is hanged and the game is over! Implement this logic.
  8. If a player guesses all the correct letters without being hanged, the player wins (so also implement this logic). 
    9.  -------
 |     |
 |     O
 |   --|--
 |     |
 |    / \
 |
 |
=============