CSSE 230
Data Structures and Algorithm Analysis

Homework 3  -  40 points

To Be Turned In

See submission instructions below: one to a special dropbox, and most to the regular dropbox.

[Numbers in brackets] are problem numbers from the third edition of the Weiss textbook.

The following formulas for series sums may be helpful:

1. (20 points) Essay on Professional Code of Ethics The purpose of this question is to familiarize yourself with the Code of Ethics of our discipline and to explain important ethical obligations associated with our discipline.

   The ACM's Code of Ethics states in section 1.5: Honor property rights including copyrights and patent

   1. Skim the Code of Ethics, but read 1.5 more closely.
   2. Write an essay (single-spaced, 12 pt, at most one page) in which you:
      1. State and explain this ethical obligation.
      2. Explain how the obligation applies to professional action.
      3. Use a systematic argument to support your explanation, describing why the actions are ethical or unethical.
      4. Give three or more specific examples of professional activities where the ethical obligation applies and explain how it applies.

      If you prefer, you may select another section of the ACM Code of Ethics as the basis for your essay.  If you do this, be sure to indicate which section you chose to elaborate.

      Grading: If no sys argument, -3. If argument only includes 1 reason why ethical/unethical, -1. If only give 2 examples, -1. If only give 1 example, -3. If examples not developed, -2.

   3. Submit your essay to the Code of Ethics drop box.

You will submit the following to the WA3 dropbox:

2. (10 points) It is useful to have a unique representation of binary trees that can be written compactly. For simplicity, we assume that each node of the tree will contain one Character. We represent a tree by a pair of strings, which I call chars and children. The chars is a pre-order listing of the contents of the nodes. The children string tells about the children of the corresponding node from chars as follows:

   2	The node has two children.
   0	The node has no children.
   L	The node only has a left child.
   R	The node only has a right child.

   For example:

   chars = "+a*-bcd"; children = "2022000";
   represents the tree in Weiss Figure 18.11 (a)

   chars = "7215349"; children = "220LR00";
   represents the tree in Weiss Figure 19.4 (a).

   1. What are the values of chars and children for the tree below?

      

   2. For a different tree we have:

         chars = "THEQUICKBROWN";
      children = "2R220002R0RL0";
      

      Show the order of the nodes in an in-order traversal of the tree.

3. (10 points)

   THEQUICKLAZYFOX is the pre-order traversal of a tree (one character per node).

   QIUCEHLAZKFYTXO is the in-order traversal of the same tree.

   What is the order of the nodes in the level-order traversal of this tree?

For Your Consideration

These problems are for you to think about and convince yourself that you could do them. It would be good practice to actually do them, but you are not required to turn them in.

• Weiss Problem 3.15 [3.12]

• This problem is inspired by Weiss exercise 5.11 [5.8], but is different. That problem examines the efficiency of computing X^N, where X is a double value and N is an integer. That algorithm is O(N). It turns out we can do a lot better; there is an algorithm that is O(log N). Write and test code that does this.

  Hint: Base your algorithm on the binary representation of N. For example, X¹¹ = X¹*X²*X⁸ (Note that 11 has one-bits representing 1, 2, and 8). So you can write N as a sum of powers of 2. Start with power=X, and keep squaring power to get the original X to those powers of 2. Only multiply X⁽²ⁱ⁾ into the product if the ith bit of the binary representation of N is 1. Your program should ask the user for X and N, and print X^N.

  Another hint: It is probably easier to do this recursively.

  You can just write the code out by hand if you wish, but I recommend getting it working in Eclipse.

• Weiss exercise 6.4 [6.4].

• Weiss Exercise 6.33 [6.18]. Your program should read strings (one per line) form standard input, and write Strings (one per line) to standard output. The alphabetical part of the sort should ignore case. Hint: Use a two-argument overloaded version of java.util.Collections.sort().

  Sample Run:

  Enter the strings, one per line (CRTL Z to end):
  Come
  and
  sit
  by
  my
  side,
  if
  you
  love
  me
  Do
  not
  hasten
  to
  bid
  me
  adieu
  Just
  remember
  the
  Red
  River
  Valley
  And
  the
  cowboy
  who
  loved
  you
  so
  true
  
  SORTED LIST OF STRINGS:
  by
  Do
  if
  me
  me
  my
  so
  to
  and
  And
  bid
  not
  Red
  sit
  the
  the
  who
  you
  you
  Come
  Just
  love
  true
  adieu
  loved
  River
  side,
  cowboy
  hasten
  Valley
  Remember