FHTW Berlin Fachbereich 4 Internationale Medieninformatik PROG2: Programmierung II Sommersemester 2003

Finger exercises:
 

1. Write a method that generates an array of random integers. The method should return a label to this new array, and have parameters that determine how many elements are to be generated and which give upper and lower bounds for the values to be generated.
   
   
2. How could you make sure that no duplicates are generated for such an array? What is the complexity of this?
   
   
3. Given an array of integers, write a method to generate a random permutation of this array.
   
   
4. How can you test if an array of integers is sorted? What is the complexity of this? Write a method that returns true if its array parameter is sorted.
   
   
5. Given two arrays of integers. How can you determine if they contain the same numbers, i.e. they are permuations? What is the complexity of this?

 

6. Check the complexities of some of the sort algorithms discussed in class! Implement at least Selection Sort, Insertion Sort, Bubble Sort and Quicksort. Count the number of comparisons and the number of exchanges needed for each. Your program should do 5000 sorts for each algorithm. Each sort should be on an array of size 1000 with randomly generated integers. Let each sorting algorithm sort a copy of the array, so that you can compare the results better. Output your results to a file. Discuss whether the results fit your expectations!

 
7. (For the adventuresome) Prepare the results so that they can be input into Excel and plotted.
   
   
8. (For the bored) Animate the tests with 4 frames displaying the sorting as it is happening. Use positive integers only and display the array values as lines that are proportionate to the values. Start the sorts at the same time, and see which one wins every time!
   
9. (For the summer break) Now that you can compute random permutations, make a representation for a deck of cards, and write a method to shuffle the cards and output them to the screen - plain or fancy, doesn't matter. If the summer gets real long and rainy, you can try to write a program to play a card game! Crazy Eights (Mau-Mau in German) is easy, Skat or Bridge a tad more difficult. Have a nice vacation!