Dr. Marek Suchenek's CSC 311 Course


California State University Dominguez Hills - Department of Computer Science

CSC 311- 01 Data Structures Spring 2015

THE URL OF THIS PAGE IS http://csc.csudh.edu/suchenek/CSC311/homework.htm

Last revised April 27, 2015

The contents of this website, the links contained therein directly and indirectly, and the contents of the said links, are copyrighted. They are provided exclusively for non-profit educational use by the students currently enrolled in this course and for the duration of this semester. No other use or any use by others is allowed without authorization of the professor in this course and copyright holder or holders. No videotaping or recording without professor's prior permission is allowed in class.

Homework

All assignments turned in for credit must be 100% your own work (except that you may be allowed to use and modify the programs linked in the instructions) with no collaboration/help of any kind with others.

All submitted program must be complete running projects under NetBeans in the lab in NSM B-208 SAC 2102.

You will need 2 (two) USB memory sticks for completion of programming assignments in this class.

Go to the latest homework.

Go to the latest programming assignment.

"No credit" exercises for Appendix B (make sure to do them ALL before the 3rd week):
Questions 1, 2, 3 p. 457, 1, 2, 3, 4 p. 465, 1, 2, 3, 4, 5, 6 p. 470, 1, 2, 3, 4, p. 471-472.
Exercises 1, 2 p. 465, 1, 2, 3, p. 470, 1, 2, p. 472.

"No credit" exercises for Chapter 4:
Questions 1, 2, 3, 4, 5 p. 113.
Exercises 1, 10, 11 p. 113, 115.- re-use them appropriately from previous projects.

"No credit" exercises for Chapter 5:
Questions 1, 2, 3 p. 131 and 1, 2, 3, 4 p. 139.
Exercise 1 p. 139.

"No credit" exercises for Chapter 6:
Questions 3, 4 p. 156, and 1 p. 167, and 1, 2, 3, 4 p. 173, and 1, 2 p. 190.
Exercises 2 p. 157, and 1 p. 167, and 1, 2 p. 173, and 2, 3, 5 p. 190 - 191.

Warm-up Programming Project # 0 (Credit 0 - 10 pts)
Binary Representation of int

Write a complete (and running) java program that performs these functions (implemented as methods):

Function 1: Reads a positive integer number and counts the number of bits in its binary representation (as an unsigned integer), not including the leading zeros.

Example: the number of bits in binary representation of 27 is 5.

(Credit 0 - 4 pts)

Function 2: Reads positive interger numbers n and m and quickly computes the value of the remainder 2^n (2 to power n) mod m.

Examples: 11 mod 3 = 2; (2^10) mod 125 = 24.

Hint. Use this property: (a^n) mod m = (a * a * a *...* a) mod m =
= (...(((((a mod m) * a) mod m) * a) mod m) *...* a) mod m.
For instance,
(2^4) mod 7 = (2 * 2 * 2 * 2) mod 7 =
= ((((((2 mod 7) * 2) mod 7) * 2) mod 7) * 2) mod 7 =
= (((((2 * 2) mod 7) * 2) mod 7) * 2) mod 7 =
= ((((4 mod 7) * 2) mod 7) * 2) mod 7 =
= (((4 * 2) mod 7) * 2) mod 7 =
= (1 * 2) mod 7 =
= 2 mod 7 = 2.
In order to avoid overflow, you may use this property:
(a * 2) mod m = a * 2 if a < m/2,
(a * 2) mod m = a * 2 - m = (a - m) + a if a >= m/2.
This way you compute
(((4 * 2) mod 7) * 2) mod 7 = (((4 - 7) + 4) * 2) mod 7 = (1 * 2) mod 7 without use of numbers greater than 7.

(Credit 0 - 6 pts; depends on how quickly your code computes its result)

Requirements:

1. The resulting program must be 100% your own work with no collaboration/help of any kind with others.

2. The program must not crash because of overflow for any input.

3. The only methods that your program is allowed to use are those that you have coded yourself. It must not use Math methods, % operator, or anything similar to that.

You should also resolve any technical/implementational issues that arise while completing this project.

What to turn in:

A USB memory stick with the complete running program in the form of runnable NetBeans 8 project, and

A text file with instructions how to enter data to the program, and

Printout of the program's source codes with its author's name printed, and

Printouts of the computed results by your program:

for Function 1 and input 1,234,567
for Function 2 and n = 63, m = 1023

ALL THE ABOVE MUST BE SUBMITTED IN A SIGNED 9" X 12" ENVELOPE.

Past due Due date: January 29, 2015, by 1 4 PM.

Programming Project # 1 (Credit 0 - 10 pts)
Experimenting with running time

Here is a link http://csc.csudh.edu/suchenek/CSC311/HWProgs/FibbonaciHW.java to a program that for each integer n ranging from 1 to 1024 computes the value of this recursive function F(n):

    public static int F(int n)
    {
        count++;
        if (n == 0) return 1;
                if (n%10 == 0) return (F(n/2) + F(n/5));
                    else
                        if (n%6 == 0) return(F(n/2) + F(n/3));
                                else return(F(n/3) + F(n/5));
    }

where k/m denotes the integer division (for example, 11/2 = 5, 10/2 = 5, 10/3 = 3, 9/3 = 3, etc.), and k%m is the remainder of integer division k/m (for example, 11%2 = 1, 10%2 = 0, 11%3 = 2, 10%3 = 1, etc.),

and counts its own worst-case running time measured by the number of calls to function F.

Your assignment is to convert the said program onto a complete and running (under NetBeans 8) program that for every size of integer n ranging from 1 to 10 computes and outputs the worst-case running time T(n) (measured by the number of calls to function F) of F.

Requirements:

1. The resulting program must be 100% your own work (given the program linked above) with no collaboration/help of any kind with others.

2. The size of input n is the number of bits needed for representation of the value of n, excluding any leading zeros. (Hint: the size of n =

(int)Math.floor(Math.log(n)/Math.log(2))+1

3. The actual running time of the program is measured by counter count that counts the number of times that the function F is called.

4. The program must print its own worst-case running time T(size) as a function of the size of input (NOT of the input n itself) together with the actual numeric value of T(size). (Hint: If different inputs n of the same size result in different number of calls to method F then the maximum of the number of said calls yields the value of T(size).)

5. The only methods that your program is allowed to use are those that you have coded yourself and those in java.lang.Math.

You should also resolve any technical/implementational issues that arise while completing this project.

What to turn in:

A USB memory stick with the complete running program in the form of runnable NetBeans 7.1 project, and

Printout of the program's source codes, and

Printouts of the computed results by your program.

An example of one line (out of several) of output should be:

ALL THE ABOVE MUST BE SUBMITTED IN A 9" X 12" ENVELOPE.

Past due Due date: February 17, 2015, by 4 PM.

Programming Project # 2 (Credit 0 - 10 pts)
Unsorted Insert List implementation of Priority Queue

Rewrite implementation of priority queue given in class PriorityQueueL.java with List defined as

    private int count;
    private List itemList;

(see List.java), so that it uses this unsorted, non-recursive metod insert (it is mandatory thet you use this code with no modifications)

    public void insert(int newItem)
    {
        cnt.incr();
        List N = new List();
        N.head=newItem;
        N.tail=itemList;
        itemList=N;
        count++;
    }

and appropriately modified remove() method (you are supposed to write it by yourself) that removes the largest element from the priority queue passed to it as the implicit argument.

You may need to implement a method that finds the largest element in a List defined above, first.

After the above modifications, your class PriorityQueueL.java must work as needed when invoked by the sorting method included in class PriorityQueueTestL.java.

In particular, both the sorting and the values of T(n) must be correct.

You are supposed to add to your program any other classes (for instance, cnt.java) that might be necessary; you may re-use them from previous projects if appropriate.

You may use and modify source code posted on class website on page Programs, but you must not use any source code from any other source (e.g., from the Internet, discussion groups, libraries, repositories, etc.).

Bonus: If you think you are really good at programming then you may try to implement the method remove() by means of recursion. Although it is a bit more challenging task, it leads to a simpler code that is easier to troubleshoot. If you do it right then I will add 50% to your score for this assignment. Since in such a case there is no need for any while- or for-loops in class PriorityQueueL.java, class cnt.java must just count the number of calls to methods in PriorityQueueL.java class and not the number of times the bodies of the innermost loops were traversed.

Requirements:

1. The resulting program must be 100% your own work (given the source code linked above) with no collaboration (or help) of any kind with (or from) others.

2. The size of input is the number N of elements of the sorted array.

3. The actual running time of the program is measured by class cnt.java that counts the number of times that the body of the innermost loop in each method (if given method has a loop) is executed plus the number of times that each method in class PriorityQueueL.java is called.

4. The only methods that your program is allowed to use are those that you have coded yourself, those posted ahere and on page Programs, and those in java.lang.Math.

You should also resolve any technical/implementational issues that arise while completing this project.

What to turn in:

A USB memory stick with the complete running program in the form of runnable NetBeans 9.1 project, and

Printout of the program's source codes, and

Printouts of the computed results by your program for arrays (to be sorted) of sizes from 1 to 20, each of which including increasigly sorted, decreasingly sorted, and pseudo-random array, just like the code in class PriorityQueueTestL.java is designed to do.

So, your printouts must contain complete outputs for 60 different arrays.

ALL THE ABOVE MUST BE SUBMITTED IN A 9" X 12" ENVELOPE.

Due date: March 12, 2015, by 4 PM.

Programming Project # 3 (Credit 0 - 10 pts)
Doubly-linked implementation of QUEUE

1. Modify project Split (posted at class website) by replacing the array implementation O_QUEUE.java of ADT QUEUE posted here:
http://csc.csudh.edu/suchenek/CSC311/O_QUEUE.java
with a doubly linked implementatiomn of ADT QUEUE. (Note: It will require modification of class Split, too. )

2. Determine experimentally the average costs of enqueue per insertion and dequeue per deletion while running Split.

Requirements:

1. The resulting program must be 100% your own work (given the program linked above) with no collaboration/help of any kind with others.

2. The size of input is the number N of elements of the queue.

3. The actual running time of the program is measured by class cnt.java that counts the number of times that the body of the innermost loop in each method (if given method has a loop) is executed plus the number of times that each method in class that implements ADT QUEUE is called.

4. The only methods that your program is allowed to use are those that you have coded yourself, those posted on page Programs, and those in java.lang.Math.

You should also resolve any technical/implementational issues that arise while completing this project.

What to turn in:

A USB memory stick with the complete running program in the form of runnable NetBeans 9.1 project, and

Printout of the programs' codes, and

File SplitOutput.txt with the complete output of running Split (needs to be similar to the output http://csc.csudh.edu/suchenek/CSC311/output.txt of program Split discussed in class).

A statement with the big-theta characterizations of the average cost of Enqueue and Dequeue.

ALL THE ABOVE MUST BE SUBMITTED IN A LETTER-SIZE 9" X 12" ENVELOPE.

Due date: April 2 7 , 2015, by 4 PM.

Programming Project # 4 (Credit 0 - 20 pts)
LIST Selection Sort

1. Class ListSelectionSort.java posted at http://csc.csudh.edu/suchenek/CSC311/HWProgs/ListSelectionSort.java is supposed to sort objects of ADT LIST consisting of finitely many elements of Java type Integer (similary to class posted at http://csc.csudh.edu/suchenek/CSC311/SelectionSort/Main.java and discussed in class earlier this semester). Your task is to write a missing code of the method SelectionSort(LIST A) that actually performs the said sorting. Other than that, you are not allowed to modify class ListSelectionSort.java (what exactly are you allowed to change is indicated in a comment above that class in the file).

Your program must work seamlessly with all three implementations of ADT LIST covered in this course:

a. array implementation:

http://csc.csudh.edu/suchenek/CSC311/LIST_AR.java

http://csc.csudh.edu/suchenek/CSC311/POSITION_AR.java

b. singly-linked list implementation

http://csc.csudh.edu/suchenek/CSC311/LIST.java

http://csc.csudh.edu/suchenek/CSC311/POSITION.java

c. doubly-linked list implementation

http://csc.csudh.edu/suchenek/CSC311/LIST_DLL.java

http://csc.csudh.edu/suchenek/CSC311/POSITION_DLL.java

You will need to incorporate all the above in your program(s), without any modifications, as well as appropriate cnt and Bcnt classes (if needed).

Requirements:

1. The resulting program must be 100% your own work (given the program linked above) with no collaboration/help of any kind with others.

2. Your method SelectionSort(LIST A) and any other method that it calls (directly or indirectly) must not copy, clone, or duplicate any list, and it must not move elements between any two different lists.

3. The only methods that your program is allowed to use are those that you have coded yourself, those contained in the above links, those posted on page Programs, and those in java.lang.Math.

You should also resolve any technical/implementational issues that arise while completing this project.

What to turn in:

A USB memory stick with the complete running program in the form of runnable NetBeans 9.1 project, and

Printout of the programs' codes, and

Nine (9) printouts of outputs of your programs:

three (3) for each implementation of ADT LIST

array,
SLL, and
DLL

for each of the following three (3) LISTS:

an increasingly sorted LIST,
decreasingly sorted LIST, and
pseudo-randomly sorted LIST

for N = 12.

ALL THE ABOVE MUST BE SUBMITTED IN A LETTER-SIZE 9" X 12" ENVELOPE.

Due date: April 23, 2015, by 4 PM.

Programming Project # 5 (Credit 0 - 30 pts)
3-heap implementation of PRIORITY QUEUE

1. Following exactly the instructions posted at
http://csc.csudh.edu/suchenek/CSC311/HWProgs/Assignment5.pdf
modify the heap implementation of priority queue onto 3-heap implementation.

2. Run your program on 3 arrays of 40 integers each:

an increasingly ordered array,
a decreasingly ordered array, and
a semi-random array.

What to turn in:

A USB memory stick with the complete running NetBeans project with the modified programs, and

Printout of the programs' codes, and

The complete outputs of running of your programs, 1 for each of mentioned above arrays.

ALL THE ABOVE MUST BE SUBMITTED IN A LETTER-SIZE 9" X 12" ENVELOPE.

The resulting program must be 100% your own work (except that you shall use and modify the programs linked in the istructions posted above) with no collaboration/help of any kind with others.

Due date: May 7, 2015, by 4 PM.

Please, contact me right away if you have any questions.