Home   Courses   CSC330: Data Structures

Assignments

Solutions to Class Work
  • Class Work 1
  • Class Work 2

 

Homework assignments:

Project assignments:

You can develop your program under Windows using Microsoft Visual C++. If you've never used MSVC before, please refer to How to create a simple program with MSVC++. Before you submit anything, make sure that you've read the requirement about programming styles.

 

HW #1

  • Download the life program, run it with input of each configuration shown in Figure 1.1 in the textbook (page 11) over the course of five generations, and record the results. 
  • P1(a) on page 43. For the P1(a) the class Square and main function are provided as follows.

const int max_size = 9;

class Square {

   public:

      void read();     //the square data is read

      bool is_magic();     // determin if the given square is a magic square

   private:

      int sum_row(int i);     // returns the row sum of the ith row

      int sum_col(int i);      // returns the col sum of the ith row

      int sum_maindiag();   // returns the main the main diagonal sum

      int sum_other();     // returns the non-main diagonal sum

      int size;

      int grid[max_size][max_size];

};

 

void main()

{

      cout << "Magic Square Program" << endl << endl;

      cout << "Enter a square of integers:" << endl;

      Square s;

      s.read();

      if (s.is_magic()) cout << "That square is magic!" << endl;

      else cout << "That square is not magic." << endl;

}

 

 

HW #2

  • Ex2.2 -- E1 on page 64, and P2 and P3 on page 69

For Ex2.2 -- E1, you need to complete all class methods' definition. You can reference the example of section 2.2.3. Finally, you use the following driver to test your methods.


typedef int Stack_entry;
const int maxstack = 10;

 int main()
{
      Extended_stack e;
      int x;
      e.push(1);
      e.push(2);
      e.push(3);
      e.top(x);
      cout << "Expect output of 33" << endl;
      cout << e.size();
      cout << x << endl;
      e.pop();
      cout << "Expect output of 001" << endl;
      cout << e.empty();
      cout << e.full();
      e.clear();
      cout << e.empty()<< endl;

}

 

or if you use template to define the class, you may use  Extended_stack <int> e instead of Extended_stack e in the first statement in int main().

 

For Programming Project 2.3 -- P2 and P3, I provide two functions' prototypes:

 

void swap_stack(Stack &numbers);
Stack_entry sum_stack(Stack &numbers);

 

You need to code the two functions.

 

For Ex2.2 -- E1, you have to submit a softcopy, while for P2 and P3, a hardcopy is OK.

 

 

HW #3

  • Ex3.1 -- E1, E2, E3 (b) (c) (e) on page 84, and Ex3.3 -- E10 and E13 on page 92

For Ex3.1 -- E3, the prototypes of the functions are given

(b) Error_code queue_to_stack(Stack &s, Queue &q);

(c) Error_code move_stack(Stack &s, Stack &t);

(e) Error_code reverse_queue(Queue &q);

For Ex3.3 -- E10, the prototype of the class Deque is given as follows

class Queue {

public:

     Queue();

     bool empty() const;

     Error_code serve();

     Error_code append(const Queue_entry &item);

     Error_code retrieve(Queue_entry &item) const;

    

private:

     int count;

    int front, rear;

    Queue_entry entry[size];

};

class Deque: public Queue {

public:

     Deque();

     Error_code serve_front();

     Error_code serve_rear();

     Error_code append_front(const Queue_entry &item);

     Error_code append_rear(const Queue_entry &item);

     Error_code retrieve_front(Queue_entry &item) const;

     Error_code retrieve_rear(Queue_entry &item) const;

};

And the test driver is given as follows

int main()

{

      cout << "Enter lines of text and the program doubly duplicates  them."<< endl;

      cout << "Use Ctrl-Z (EOF) to terminate the program." << endl;

     

      while (cin.peek() != EOF) {

     

            Deque q;

            char c;

     

               while ((c = cin.get()) != '\n') {

                  q.append_front(c);

                  q.append_rear(c);

            }

     

               while (!q.empty()) {

                  q.retrieve_front(c);

                  cout << c;

                  q.retrieve_rear(c);

                  cout << c;

                  q.serve_front();

                  q.serve_rear();

            }

    

             cout << endl;

      }

}

HW #4

  • Ex4.2 -- E1 on page 130 , Ex4.3 -- E1, E2 on pages 136,137, and Ex4.4 -- E1on page 140

 

 

HW #5 

  • Ex 5.2 - E3 on page 182
  • Trace the following recursive function that solves the “Towers of Hanoi” problem

void move (int count, int start, int finish, int temp)

{

    if (count >0)

   {

         move(count-1, start, temp, finish);

         cout << "Move disk"<< count<< “from”<< start<< "to"<< finish;

         move(count-1, temp, finish, start);

   }

 

}

 

1.Draw the recursion tree for the function call move(4, 1, 3, 2). Please include every call to function move in the diagram, and for each call, give the value of every parameter.

2.Give the output of the above function call.

 

HW #6

 

  • Ex 6.1 - E1, E2, E6 and E10 on page 217
  • Ex 6.3 - E3 and E4 on page 241
  • Implement the doubly linked list (submit softcopy only). The class declaration is given as follows:

 

template <class Node_entry>

struct Node {

// data members

     Node_entry entry;

     Node<Node_entry> *next;

     Node<Node_entry> *back;

// constructors

     Node();

     Node(Node_entry, Node<Node_entry> *link_back = NULL,

     Node<Node_entry> *link_next = NULL);

};

 

 

template <class List_entry>

class List {

public:

    List();

     int size() const;

     bool full() const;

    bool empty() const;

     void clear();

     void traverse(void (*visit)(List_entry &));

    Error_code retrieve(int position, List_entry &x) const;

    Error_code replace(int position, const List_entry &x);

    Error_code remove(int position, List_entry &x);

    Error_code insert(int position, const List_entry &x);

    ~List();

    List(const List<List_entry> &copy);

     void operator =(const List<List_entry> &copy);

// Add specifications for methods of the list ADT.

// Add methods to replace compiler generated defaults.

protected:

// Data members for the doubly-linked list implementation follow:

     int count;

     mutable int current_position;

     mutable Node<List_entry> *current;

// The auxiliary function to locate list positions follows:

     void set_position(int position) const;

};

You must use the following test driver "main.cpp" to test your program.

 

HW #7 

  • Submitting Homework: Ex 7.3 - E1 on page 285, Ex 7.6 - E2, E4 (a) (b) and E5 (a) (c) (e) (g) on page 312

 

HW #8

  • Submitting Homework: Ex 10.1 - E2 on page 441, E14 on page 443, E10.2- E1(d) (e) (f), E2 (a) (c) (e), E3 (b) (d) (f) and E4

 

 

Project 0    (Due 2/11/1010)

Question 1

Create a class called Complex for performing arithmetic with complex numbers. Write a driver program to test your class.

Complex numbers have the form

realPart + imaginaryPart * i

where i is (-1)^(1/2)

Use integer (or floating-point) to represent the private data of the class. Provide a constructor function that enables an object of this class to be initialized when it is declared. The constructor should contain default values in case no initilizers are provided. Provide public member functions for each of the following:

a) Addition of two Complex numbers: The real parts are added together and the imaginary parts are added together.

b) Subtraction of two Complex numbers: The real part of right operand is subtracted from the real part of left operand and the imaginary parts of right operand is subtracted from the imaginary part of left operand.

c) Printing Complex numbers in the form (a, b) where a is the real part and b is the imaginary part.

Hints:

 

Question 2 

Write a grading program for a class with the following grading policies:

1. There are two quizzes, each graded on the basis of 10 points

2. There is one midterm exam and one final exam, each graded on the basis of 100 points.

3. The final exam counts for 50% of the grade, the midterm exam counts for 25%, and the two quizzes together count for a total of 25%.

Any grade of 90 or more is an A, any grade of 80 or more (but less than 90) is a B,  any grade of 70 or more (but less than 80) is a C, any grade of 70 or more (but less than 90) is a D, and any grade below 60 is an F.

The program will read in student’s scores and output the student’s record, which consists of two quiz and two exam scores as well as the student’s average numeric score for the entire course and final letter grade. Define and use a class for the student record. Also, input/output should be done with files.

Hints:

  

Note: Input and output must be done using the with files. An example is given here.

 

Project #1

Polynomial Calculator Program     

This program simulates a polynomial calculator (Addition) that works on a stack and a list of operations. The model is of a reverse Polish calculator where operands are entered before the operators. An example to add two polynomials and print the answer is

 ?P?Q+= 

P and Q are the operands to be entered, + is add, and = is print result. The result is put onto the calculator's stack.

Enter a string of instructions in reverse Polish form. The allowable instructions are:

 ?:Read       +:Add           =:Print      -:Subtract

*:Multiply    q:Quit          /:Divide        h:Help

Enter the coefficients and exponents for the polynomial, one pair per line.  Exponents must be in a descending order. Enter a coefficient of 0 or an exponent of 0 to terminate.

For example take an addition of F(x)=4x²+3x and G(x)=3x³+1

You should input as

Select command and press <Enter>:?

coefficient? 4

exponent? 2

coefficient? 3

exponent? 1

coefficient? 0

Select command and press <Enter>:?

coefficient? 3

exponent? 3

coefficient? 1

exponent? 0

Select command and press <Enter>:+

Select command and press <Enter>:=

3 x^3 + 4 x^2 + 3 x + 1

Grading criteria

Correctness: (50%) Your program must be compilable under Microsoft Visual Studio .Net or Microsoft Visual Studio C++ platform and must accept valid input and produce the correct result in correct format. A program that fails to compile or produces unreasonable results loses all credits for the correctness.

Design: (25%) Your program should include term.h, polynomi.h, polynomi.cpp and a test driver. Of course, if you have more functions or modules, you can include more files. You must add comments at the beginning of your main module, and the description of every module in your project.

Style: (25%) You source code should comply with the programming style requirement listed below.

Bonus assignment (optional)

Subtraction (2%): Besides P(x) = F(x) + G(x), also compute S(x) = F(x) - G(x). When printing out R(x), the negative coefficent must be properly printed. e.g., you must use the format "- 2x^2 -1" instead of " -2x^2 + -1 ".

Multiplication (3%): Also compute and print M(x) = F(x) * G(x).

Division (5%): Also compute and print the quotient Q(x) and remainder R(x) in the division F(x) / G(x), such that F(x) = G(x) * Q(x) + R(x).

You must specify which bonus assignment have you done in the head comments of your main module, in order to get the bonus points.

Reference  

Section 4.5 on the textbook page 141-151

Hints

Project #2 

Sorting Program

Create a Sortlist that implements 6 different sorting methods

  • Insertion sort
  • Selection sort
  • Shell sort  (optional)
  • Quick sort
  • Heap sort
  • Bubble sort

and calculate and print

  • The CPU time

  • The number of comparison of keys

  • The number of assignments of list entries during the sorting list.

Requirements

1. The following source files are given through SortList.zip

Key.h and Key.cpp implement the Key class to conduct and count Key comparisons and assignments. 

Record.h and Record.cpp implement the Record class which is used as List entry. Also, it provides operator Key to conduct and count comparisons and assignments.

List.h is the template based array implementation of List class

Random.h and Random.cpp implement the Random class to set random seed and generate random integers.

Timer.h and Timer.cpp implement the Timer class to calculate time interval.

Utility.h provides definition of Error_code.

Main.cpp is the test driver to test the Sortlist class. It contains user interface, filling the list with random integers, calling Sortlist sorting functions and calculate the CPU time, the number of comparison of keys, and the number of assignments of list entries during the sorting list.

Sortlist.h is the derived class of the List class. You MUST follow the public functions I provide, but you can add more member functions if necessary.  

2. Implement the following member functions

  • void insertion_sort(); // todo: implement insertion sort
  • void selection_sort(); // todo: implement selection sort
  • void shell_sort();   // todo; implement shell sort (optional)
  • void quick_sort();  // todo; implement quick sort
  • void heap_sort();  // todo; implement heap sort
  • void bubble_sort(); // todo; implement bubble sort

3 Submit Sortlist.h (Sortlist.cpp) only by

 

Project #3

The purpose of the project is to compare several different kinds of binary search trees used for the information retrieval problem.

As to the project description, please refer to P5 on page 461 in textbook or click here . P3 on page 490 is an option.

 

 

 


Changed: 09/08/10

Hosted by CS/ECSU 

composed by Kehan Gao