FHTW Berlin Fachbereich 4 Internationale Medieninformatik Info2: Informatik II Sommersemester 2006

Finger exercises (write in sentences, not code):
 

1. Given an array of integers, how could you generate a random permutation of the array?
2. How could you generate an array of random integer? What signature would such an array have?
3. How could you make sure that no duplicates are generated for such an array? What is the complexity of this?
4. How can you test to see if an array of integers is sorted? What is the complexity of this?
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?

 

1. Write a class that generates Arrays of random numbers. Make sure you have a way of saying that there are to be no duplicates. Hint: use multiple constructors and a boolean parameter noduplicates.
2. Start a class Sort. Write a static method that returns true if its array parameter is sorted.
3. Check out the complexities of some of the sort algorithms discussed in class! Implement at least Selection Sort, Insertion Sort, Bubble Sort and Quicksort. The bored should do Heap Sort and Shell Sort as well. The extremely bored can try Bogosort. 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 in your report whether the results fit your expectations!
4. (For the adventuresome) Prepare the results so that they can be input into Excel and plotted.
5. (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 proportional to the values. Start the sorts at the same time on different threads, and see which one wins every time!
6. (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!