CIS-3333 Assignments

Due Date: Task

Coding Standards will be enforced on all assignments after September.

Dec.9: Using appropriate technology, write a program in C++ to build a concordance (aka Key Word In Context) to a document the size of the Bible. Zip up a folder with your source files and makefile and email it to me before class; turn in a paper document describing your design decisions.
<Dec.1: (Before you start coding) Turn in corrected Data Structures Design. Hint: The properly commented ".h" files for your finished program should probably have everything I want to see here.
Nov.18:  [40%] Turn in for the concordance program two copies of your complete data structures design (aka Class Diagrams) including pre-/post-conditions and task statements for the public methods. Late submission will be penalized 10% of the total (25% of this part). Conformance of the code to this design will be 30% of the total grade, so I will keep one copy to compare it to.

Nov.13: p.173, #4.21; alternatively, rewrite the whole AVL algorithm without templates. Show that your algorithm works.

Nov.11:  (10 points extra credit) Turn in a one-page critique of the Wal-Mart software design methodology as described in their presentation Nov.6.

Nov.11: p.171, #4.5, 4.7, 4.11, 4.14. Do it right.

Oct.9: p.116, #3.2, 3.17, (optional) 3.4

A simple list node type we can use for both singly and doubly linked lists, with a function to display either kind:

struct Node {int datum; Node * link; Node * prev;};
typedef Node * List;

// Pre: lnk is valid Node, or else NULL
// Post: returns new Node linked to lnk
List NewN(int val, List lnk) { // create new single-linked node
  List here = new Node;
  here->datum = val;
  here->link = lnk;
  return here;}

// Pre: lnk and bak valid Nodes, or else NULL
// Post: returns new Node double-linked to both lnk and bak (if not NULL)
List New2(int val, List lnk, List bak) { // create new double-linked node
  List here = new Node; // note: this can and will insert in middle
  here->datum = val;
  here->link = lnk;
  here->prev = bak;
  if (bak != NULL) bak->link = here;
  if (lnk != NULL) lnk->prev = here;
  return here;}

void Show(List list) {
  while (list != NULL) {cout << " " << list->datum; list = list->link;}
  cout << endl;}

A function to swap the nodes after the parameter, in a singly-linked list:
// Pre: here is valid List, or else NULL
// Post: still a valid list, but with elements swapped
void SwapAfter(List here) {
  List fust, scnd;
  if (here == NULL) return;
  fust = here->link;
  if (fust == NULL) return;
  scnd = fust->link;
  if (scnd == NULL) return;
  here->link = scnd;
  fust->link = scnd->link;
  scnd->link = fust;}
A function to swap the parameter node with its successor, in a doubly-linked list:
// Pre: here is valid (double-linked) List, or else NULL
// Post: still a valid list, but with elements swapped
void Swap2(List here) { // doesn't do first in list
  List succ, prio;
  if (here == NULL) return;
  succ = here->link;
  if (succ == NULL) return;
  prio = here->prev;
  if (prio == NULL) return;
  if (succ->link != NULL) succ->link->prev = here;
  here->prev = succ;
  succ->prev = prio;
  here->link = succ->link;
  prio->link = succ;
  succ->link = here;}
A non-recursive function to reverse the nodes in a list, using constant extra space:
// Pre: here is valid List, or else NULL
// Post: returns the same list (former tail) with elements reversed
List Reverse(List here) {
  List temp, head = NULL;
  while (here != NULL) {
    temp = here->link;
    here->link = head;
    head = here;
    here = temp;}
  return head;}
A simple test procedure:
int main() {
  List dub, tmp, sing = NewN(1,NewN(2,NewN(3,NewN(4,NewN(5,NULL)))));
  cout << "sing="; Show(sing);
  SwapAfter(sing->link); // swaps 3/4
  cout << "swapped="; Show(sing);
  cout << "rev'd="; Show(Reverse(sing)); // leaves them undeleted
  dub = New2(11, New2(55, NULL, NULL), NULL);
  tmp = New2(22, New2(33, New2(44, dub->link, dub), dub), dub);
  // note insertion at any point in list
  cout << "doubly="; Show(dub);
  Swap2(tmp); // tmp still points to 22, swap it with 33
  cout << "swapped="; Show(dub);}


Sep.30: p.63, #2.10, 2.11, 2.12, 2.13, 2.23, 2.24

Sep.23: (Part A) p.38, #1.4

B. Write and run a C++ program with the following properties; turn in a listing with evidence that you succeeded:

a. Read from the console three lines of text (string) input, first, second, and third;
b. Concatenate the second and third lines into a single string, and determine if the first line contains this composite;
c. If the two strings are not identical, repeat step (b), but with the third and second lines concatenated in the reverse order.
d. Print out the length of the first string, and the offset for each step (b) and if applicable, (c). Print -1 whenever the string is not there.
For example, with these three lines:
Sample xyzabcxyz line
abc
xyz
you would print out:
'Sample xyzabcxyz line' is length 21, abc+xyz is at offset 10, and xyz+abc is at 7
For
Double dada
da
da
you would print out:
'Double dada' is length 11, da+da is at offset 7
and for
Nothingness
x
z
you would print out:
'Nothingness' is length 11, x+z is at offset -1
Note that reading a whole line from the console (including spaces) requires using getline() (see Schildt p.551).

Sep.16: Write and run a C++ program with the following properties; turn in a listing with evidence that you succeeded:

a. Declare a local array of 35 integers, and fill it with squares of the numbers from 1 to 35 in reverse order.
b. Declare a pointer to another, dynamic array of 35 integers, and allocate space for it.
c. Copy the first array into the second using a single assignment statement.
d. Write a subroutine that takes a reference to an integer, and if it's odd, replaces it with its negative.
e. Call this subroutine repeatedly, passing it every third element of the first array.
f. Call this same subroutine passing it every fifth element of the second (dynamic) array.
g. Print out a numbered list of the resulting array values in three columns (line number, 1st array, 2nd array).
h. Properly dispose the dynamic array.
Note that success in part (c) depends on how you do part (a) and (b). My solutions

Sept.2: Write and run a C++ program that repetitively reads a number and outputs its square; turn in a listing with evidence that you succeeded in Linux.
 

Rev. 2003 November 21