-->

 


    

 

 California State University Dominguez Hills - Department of Computer Science

  Home  |  Syllabus  |  Course Outline  |  Homework  |  Lecture Notes  |  Tests  |  Programs  |  Contact  | 

 CSC 311- 01                                     Data Structures                                             Spring 2015

 

 

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

Last revised March 20, 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. Some of the Java source code programs linked from this page have been adopted for this course and its students based on the original programs, copyrighted by the publisher, that are part of the textbook for this course. All the corrections and modifications to the original programs are subject to the copyright by the professor for this course, whether indicated as such or not. No videotaping or recording without professor's prior permission is allowed in class.

Programs

All students in this class are supposed to download all the Java programs linked from this page to their NetBeans IDEs, make them run (this may require some minor modifications), and experiment with these programs.

Not doing so may prove detrimental to actual credit earned during the midterm and final.


Click here for the current set of programs.



Appendix B

Primality Test

http://csc.csudh.edu/suchenek/CSC311/NetBeansPrograms/BigOh_NB/
PrimTestTime/src/primtesttime/PrimalityTest.java

http://csc.csudh.edu/suchenek/CSC311/NetBeansPrograms/BigOh_NB/
PrimTestTime/src/primtesttime/PrimalityTestDemo.java

http://csc.csudh.edu/suchenek/CSC311/NetBeansPrograms/BigOh_NB/
PrimTestTime/src/primtesttime/PrimalityTestGUI.java

Selection Sort

http://csc.csudh.edu/suchenek/CSC311/SelectionSort/Main.java

http://csc.csudh.edu/suchenek/CSC311/SelectionSort/cnt.java

Chapter 4 review

 Optional material: Fibonacci sequence:

 Fibonacci sequence - recursive, plain

http://csc.csudh.edu/suchenek/CSC311/Fibonacci/Fibonacci_plain.java

Fibonacci sequence - recursive, plain (slow), called in a loop so that you can see how slow it is

http://csc.csudh.edu/suchenek/CSC311/Fibonacci/Fibonacci_MS.java

Fibonacci sequence - iterative, called in a loop so that you can see how fast it is

http://csc.csudh.edu/suchenek/CSC311/Fibonacci/Fibonacci_iterative.java

Fibonacci sequence - recursive, dynamic (fast), called in a loop 

http://csc.csudh.edu/suchenek/CSC311/Fibonacci/Fibonacci_MS_dynamic.java

Fibonacci sequence - recursive, dynamic (as fast as the iterative one), called in a loop 

http://csc.csudh.edu/suchenek/CSC311/Fibonacci/Fibonacci_MS_dynamic_plus.java

Modified fast Fibonacci for which there is no "easy" iterative version:

http://csc.csudh.edu/suchenek/CSC311/Fibonacci/Fibonacci_MSvar.java

The running time for slow resursive computation is double-exponential!

T(n) = 2*fib(n) - 1,

where fib(n) is a Fibonacci function that is known to grow exponentially. More specifically, the formula for fib(n) is:



Check the file http://csc.csudh.edu/suchenek/CSC311/Fibonacci/Fibonacci_MS.java
for experimental verification of that fact.

So,

T(n) = approx. a^n

for some a > 1.

But

size(n) = Floor(lg n) + 1 = approx. lg n,
 or

n = approx. 2^size(n).

So,

T(size(n))  = approx. a^n = approx. a^(2^size(n)) .


The running time for fast resursive computation and for iterative computation is exponential!

T(n) = n or T(n) = n - 1.

Check the files http://csc.csudh.edu/suchenek/CSC311/Fibonacci/Fibonacci_MS_dynamic_plus.java
and http://csc.csudh.edu/suchenek/CSC311/Fibonacci/Fibonacci_iterative.java for experimental verification of that fact.

But

size(n) = Floor(lg n) + 1 = approx. lg n,
 or

n = approx. 2^size(n).

So,

T(size(n)) = n - 1 = approx 2^size(n) - 1.



However, the size of the output is n.

So, the mentioned above fast resursive computation and for iterative computation are linear in the size of output.

End of optional part.


Hanoi towers

http://csc.csudh.edu/suchenek/CSC311/Hanoi/Main.java


Priority Queue

Project  PriorityQueueTest

Array sorted implementation

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

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


Array unsorted implementation

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

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

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

Linked sorted implementation

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

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


List

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


Counters

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

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

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


  Samples of outputs with clocked performance:

http://csc.csudh.edu/suchenek/CSC311/Performance_of_PQ_linear_implementations



Optional: Experimantal evaluation of resizing

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

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

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

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



End of Priority Queue section


Stack and Paren Matcher

1. Array implementation

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

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

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

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

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

http://csc.csudh.edu/suchenek/CSC311/ScreenshotParenMatch.png



2. List (linked) implementation

http://csc.csudh.edu/suchenek/CSC311/NetBeansPrograms/STACK/Stack.java

http://csc.csudh.edu/suchenek/CSC311/NetBeansPrograms/STACK/ParenMatcher.java

http://csc.csudh.edu/suchenek/CSC311/NetBeansPrograms/STACK/PMapplet.java
Pronunciation of Java data type name char in American English is a subject of controversy. This doesn't come as a surprise as the same English words may have different pronunciations depending on their meanings. (For instance, verb read is pronounced differently when it appears in present tense then when it appears as past participle.)

Most of native speakers pronounce Java's char like the first part of charm. This is sometimes referred to as a naïve pronunciation. It seems to be a result of meaning confusion.

There is a verb char in English (meaning: to burn slightly) that correctly pronounces just like the first part of charm. But char in Java has a different meaning so there is no good reason to insist that it should be pronounced the same way as the verb char. Since char in Java is an abbreviation of noun character, we have a good reason to pronounce it similarly to the first part of character.

Here is a link to an audio from a popular pronunciation dictionary with American pronunciation of data type name char:

http://www.forvo.com/word/char_(data)/#en

Here is a link to an audio with American pronunciation of noun character:

http://www.forvo.com/word/character/#en

(The situation with char (data type) versus char (verb) is a bit similar to pronunciation of doc that varies with its meaning. If doc means an abbreviation of noun document then it is pronounced differently than an abbreviation of noun doctor. Another inspiring, although a bit dissimilar, example is pronunciation of gif in an extension of a graphics file name sounding like the first part of gift, while a naïve pronunciation of it is similar to the first part of Jiffy.)

Many pronunciation dictionaries tend to steer clear form that controversy and do not provide any audio or phonetic transcription for the data type char or provide two transcriptions.

The problem appears slightly less controversial when it comes to pronunciation of varchar that is an abbreviation of phrase variable character in C. Here is an audio that suggests to pronounce it similarly to the first part of variable followed by the first part of character:

http://www.forvo.com/word/varchar/#en

At the date of this writing, this was uncontested pronounciation; therefore, it was probably as close to a definite answer to the question of how to pronounce Java's char as one could get.


Queue

Array implementation
http://csc.csudh.edu/suchenek/CSC311/Split.java

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

http://csc.csudh.edu/suchenek/CSC311/output.txt

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

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

(re-use cnt.java and cnt2.java appropriately)

Object version of the above

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


List implementation

 http://csc.csudh.edu/suchenek/CSC311/NetBeansPrograms/QUEUE_NB/Split/src/split/Split1.java
http://csc.csudh.edu/suchenek/CSC311/NetBeansPrograms/QUEUE_NB/Split/src/split/QUEUE1.java

http://csc.csudh.edu/suchenek/CSC311/NetBeansPrograms/QUEUE_NB/Split/src/split/List.java

http://csc.csudh.edu/suchenek/CSC311/NetBeansPrograms/QUEUE_NB/Split/src/split/output1.txt
(re-use cnt.java appropriately)

Two notes on Standish implementation (Program 6.23 ftom your textbook).

1. Standish uses name link that is confusing in Java programs since Java does not allow links. This confusion is easy to fix by using name tail (as I did) in place of his link, and name List (as I did) in place of his QueueNode.

A tested (by MS) Java code, modified (by MS) that way, is posted below:

 http://csc.csudh.edu/suchenek/CSC311/NetBeansPrograms/QUEUE_NB/Split/src/split/QUEUE3.java

Using the driver Split3 posted below:

http://csc.csudh.edu/suchenek/CSC311/NetBeansPrograms/QUEUE_NB/Split/src/split/Split3.java

it produces the identical output (posted below) to the implementation discussed in class:

http://csc.csudh.edu/suchenek/CSC311/NetBeansPrograms/QUEUE_NB/Split/src/split/output3.txt

2. Standish's interpretation of front and rear is a bit complicated. This is a result of the fact that he does not use the "dummy" header that I showed you in class.

So, his instance variable front points to the beginning of List that implemets queue (not one position ahead), except that it has a null value when the queue is empty.

Unlike front, his instance variable rear points one position ahead of the actual rear of the queue (very much the same as I did inclass; for otherwise his enqueue would have to contain a loop an would require "Big Theta"(n) running time), except that it has a null value when the queue is empty.

This is not just an unnecessarily complicated imterpretation of front and rear, but it also leads to a more convoluted code of enqueue, as the pictures below show.

Here is (a transcription of) Standhsh's enqueue (an excerpt from the Java program QUEUE3 posted above):



Here is my (M.S.) enqueue (an excerpt from the Java program QUEUE1 posted above and discussed in class):





ADT LIST

Array implementation

Note: Change file names to remove "_AR" before you run these programs.

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

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

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


Requires classes cnt, cnt2, cnt3, cnt4, and Bcnt - re-use them appropriately from previous projects.

Performance:

http://csc.csudh.edu/suchenek/CSC311/list_ar_purge_runs.txt

First list implementation (so-called "singly-linked")

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

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

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

Requires classes cnt, cnt2, and Bcnt - re-use them appropriately from previous projects.

Performance:

http://csc.csudh.edu/suchenek/CSC311/list_purge_runs.txt

 The cost of backward traversal:

http://csc.csudh.edu/suchenek/CSC311/Backward_print_performance_SLL_DLL.txt



Second list implementation (so-called "doubly-linked")

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

The 2 links below have been temporarily disabled.

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

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

http://csc.csudh.edu/suchenek/CSC311/initialization_insert.txt

Requires classes cnt, cnt2, and Bcnt - re-use them appropriately from previous projects.

Performance:

http://csc.csudh.edu/suchenek/CSC311/list_DDL_purge_runs.txt

The cost of backward traversal:

http://csc.csudh.edu/suchenek/CSC311/Backward_print_performance_SLL_DLL.txt


Heaps (fast implementation of ADT PRIORITY QUEUE)

Requires cnt, cnt2. (Make sure you download cnt3 via link below.)

http://csc.csudh.edu/suchenek/CSC311/Tree/PriorityQueueTest.java

http://csc.csudh.edu/suchenek/CSC311/Tree/PriorityQueue.java

http://csc.csudh.edu/suchenek/CSC311/Tree/cnt3.java

Sample outputs

http://csc.csudh.edu/suchenek/CSC311/Tree/311output1random

http://csc.csudh.edu/suchenek/CSC311/Tree/311output1increasing

http://csc.csudh.edu/suchenek/CSC311/Tree/311output1decreasing

http://csc.csudh.edu/suchenek/CSC311/Tree/311output1constant

http://csc.csudh.edu/suchenek/CSC311/Tree/311output2random

http://csc.csudh.edu/suchenek/CSC311/Tree/311output2increasing

http://csc.csudh.edu/suchenek/CSC311/Tree/311output2decreasing

http://csc.csudh.edu/suchenek/CSC311/Tree/311output2constant


Simplified and sped-up

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

Here ia a link to a published version of HeapSort:

http://csc.csudh.edu/suchenek/MakeHeap.html


Binary Search Tree

A simple test of BS methods:
http://csc.csudh.edu/suchenek/CSC311/Tree/Main.java

and its output:
http://csc.csudh.edu/suchenek/CSC311/Tree/Main_output.txt

Implementation of BS Tree:
http://csc.csudh.edu/suchenek/CSC311/Tree/BStree.java

Counters:
http://csc.csudh.edu/suchenek/CSC311/Tree/cnt.java

http://csc.csudh.edu/suchenek/CSC311/Tree/cnt2.java

http://csc.csudh.edu/suchenek/CSC311/Tree/cnt3.java

http://csc.csudh.edu/suchenek/CSC311/Tree/cnt4.java

A flag that determines if insertion/deletion was made:
http://csc.csudh.edu/suchenek/CSC311/Tree/flag.java

BS-sort with the best-case, average-case and worst-case arrays of sizes 1 to N automatically generated:
http://csc.csudh.edu/suchenek/CSC311/Tree/BS_sort_plus.java

and its outputs (best case, average case, worst case):
http://csc.csudh.edu/suchenek/CSC311/Tree/BS_sort_plus_output_best.txt

http://csc.csudh.edu/suchenek/CSC311/Tree/BS_sort_plus_output_avg.txt

http://csc.csudh.edu/suchenek/CSC311/Tree/BS_sort_plus_output_worst.txt

Application of BS Tree to purge given array:
http://csc.csudh.edu/suchenek/CSC311/Tree/BS_purge.java

and its output:
http://csc.csudh.edu/suchenek/CSC311/Tree/BS_purge_output.txt

Auxiliary methods useful in calculating theoretic formulas for the numbers of comparisons:
http://csc.csudh.edu/suchenek/CSC311/Tree/MyMath.java

 

 

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

 

 


 

Copyright © 2015 Suchenek - All rights reserved