Nothing like good pseudocode!!
Arrays: Students Show and Tell
Welcome back!!
Class activity:
Discussions and students’ presentations about the following assignments:
StdIn/StdOut – Hwk 12/3 -YI_Duplicates.java
StdDraw – Hwk 12/4 – YI_TriangleTess.java
StdDraw – Clwk 12/4 – YI_MyGraphPaper.java
StdDraw – Hwk 12/7 – YI_SongLyrics.java
StdDraw – Clwk 12/8 – YI_Histogram.java
Homework:
1 Question on edmodo.com
Work on missing assignments.
Arrays: Preparing for assessments
Preparing for assessments
Your notes should include:
- All loops syntax: while, do while, and for.
- The Scanner class: how to create an object of it and use it’s methods.
- The Math.random() function.
- Typical array-processing code highlights:
- 1D and 2D arrays: how to declare and initialize them.
- Code snippets to print all the elements, to add columns, rows.
- Programs designed to create frequency arrays.
- The code needed to swap elements of an array, to find the max and the min.
- A short program to simulate rolling dice.
- StdIn, StdOut and StdDraw short API’s with few examples.
- The rules to print formatted output, printf.
- Simple drawings programs.
Arrays: Students’ Programs Show and Tell
Students sharing code:
Random class:
Magic Numbers:
Closest Pair:
Average:
Print Array:
Dot Product:
Arrays: Test Review Arrays
Arrays Test Review
- One Dimensional arrays:
- Create arrays and initialize them with a loop.
- Initialize an array when created.
- Find the number of elements in an array.
- Check an array’s bounds.
- Swapping elements of an array – permutations (sampling without replacement)
- Given an array of N elements, write the code to shuffle them using the random feature.
- Find the max – min of the elements.
- Reverse the elements.
- Find the average of the elements.
- Print each element.
- Sieve of Erasthostenes http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
- Arrays as frequency or counters.
- What types must be used as indices for arrays?
Midterm Review Part 1
Content for some questions:
- Overflow
The int data type is a 32-bit signed two’s complement integer. It has a minimum value of -2,147,483,648 (0x80000000) and a maximum value of 2,147,483,647 (0x7FFFFFFF) (inclusive)
So when you add one to an integer’s max value:
0x7FFFFFFF + 0x00000001 = 0x80000000 (-2,147,483,648)
Arrays: Intro
- Typical array-processing code.
- Programming with arrays.
- Zero-based indexing
- Array length
- Memory representation
- Bounds checking
- Setting array values at compile time
- Setting array values at run time
- Shuffling and sampling
- Exchange
- Shuffling
- Hardwired constants
- Sampling without replacement
classwork:
Write a program, ArrayBasics_YI.java to do the following:
- Create an array a[] size 10. Assign a random number between 1 and 30 to each element.
a. Display the first element of the array.
b. Display the last element of the array assuming you do not know the size of the array.
c. Display the messages given when you try to access an element with a negative index and with an index beyond the size of the array. - Create two arrays, suit[] and face_value[].
a. The suit[] array contains the 4 different suits as elements.
b. The face_value array contains “2”, “3”,…,”Jack”,…,”Ace” elements.
c. Use the random function to select five cards and display them. - Create two arrays x[] and y[] with N number of elements both. Prompt the user for N. Assign random integers to each element. Then have another loop to find the product of each element wit the same index and add them all together. This operation is called the “dot product”.
Assignments:
ClosestPair_YI.java
Write a program to create an array of 100 random integers between the values of 1 and 1000 and find the two consecutive integers with the smallest difference between the two of them.
MaxInArray_YI.java
Write a program to create an array of 100 random integers between the values of 1 and 1000 and find the largest value.
AverageArray_YI.java
Write a program to create an array of 100 random integers between the values of 1 and 1000 and find the average of all the elements of the array.
PrintArray_YI.java
Write a program to create an array of 100 random integers between the values of 1 and 1000 and print them separated by 3 spaces. Note: Use printf to keep all your numbers tab properly.
A printf format reference page (cheat sheet)
Pop Quiz Array 1
Pop Quiz 1: Fix the problem
Arrays: Duplicate
Classwork/Homework:
Write a program, Duplicate_YI.java to find a duplicate. Given an array of N elements with each element between 1 and N, write an algorithm to determine whether there are any duplicates. You do not need to preserve the contents of the given array, but do not use an extra array.
- Create an array with 50 random integer numbers between 1 and 50 inclusive.
- Print the array in 10 rows by 5 columns. Use “printf” to keep the columns aligned.
- Print all the duplicate values and their index. Format: value, index 1, index 2 … per line.
- Print the total number of duplicates as the last message in your output.
Arrays: At Least One of Each
Classwork/Homework:
Suppose that you have a shuffled deck of cards and you turn them face up, one by one. How many cards do you need to turn up before you have seen one of each suit?
OneOfEach1_YI.java: this program will allow the user to pick as many cards as needed until all the different values in any deck of cards come up. Your program should generate the number of cards needed to find all the suits. The input should be M, the number of suits.
In general, suppose that a trading card company issues trading cards with M different possible cards: how many do you have to collect before you have all M possibilities, assuming that each possibility is equally likely for each card that you collect and that there is an infinite number of cards?
A good example would be “Collect all ranks in a random sequence of cards (M = 13).” Look at page 23 on the pdf above.
Card collector simulation
• Generate random int values between 0 and M-1
• Count number used to generate each value at least once.
Key to the implementation
• Create a boolean array of length M (Initially all false by default.)
• When r generated, check the rth value in the array.
• If true, ignore it (not new).
• If false, count it as new (and set rth entry to true)
How many cards do you need to turn up before you have seen one of each suit? Sample test runs:
How many different cards in your deck? 13
After randomly drawing 46 cards, the full collection was acquired.
How many different cards in your deck? 13
After randomly drawing 22 cards, the full collection was acquired.
How many different cards in your deck? 13
After randomly drawing 49 cards, the full collection was acquired.
How many different cards in your deck? 13
After randomly drawing 30 cards, the full collection was acquired.
OneOfEach2_YI.java: implement this program to allow the user an additional input, the specific number of trials. Each trial will calculate how many cards (no_of_cards) were drawn until all different (face) value cards were drawn. End the program by displaying the average number of cards needed for all the M cards to come up. Again, assuming there is an infinite number of cards.
A large number of trials will give you a better approximation to the solution to the problem. The idea is to keep track of how many cards were drawn to get all the (face) values at each trial and find the average. The more trials, the closer you get to the actual number. You will also see that as the number of trials keeps on growing the average does not change much. To help you find a pattern, then you increase the number of suits, and repeatedly increase the number of trials.
Show these predicted values by running the program with a high number of trials, from 1000 to 1000000.
Sample runs:
% java OneOfEach2_YI 4 1000000
8
% java OneOfEach2_YI 13 1000000
41
% java OneOfEach2_YI 52 100000
236
% java OneOfEach2_YI 1200 10000
9176
% java OneOfEach2_YI 12534 1000
125920
In theory:
Given n different suits, how many cards do you expect you need to draw with replacement (or in this case, an infinite number of cards of all different suits) before having drawn each suit at least once? The mathematical analysis of the problem reveals that the expected number of trials needed approximates n(log(n)).
For example, when n = 50 it takes about 225 trials to collect all 50 suits.
From Lawerence Chen
Input/Output: Graphics and Arrays: A Bar graph
Classwork:
Standard Drawing
Write a program, BarGraph_YI.java to draw a bar graph like the one in the picture above.
Create an array of 100 random positive integer numbers between 1 and 20 inclusive.
Find the min and max for both scales, x and y so you can determine the Xscale and Yscale for your canvas. Store in two arrays the approximate values for each of the bars in the image. Those values represent the frequency (y axis) and the value for the x coordinate. Make the width of each bar equal to 1.
Example: Bar 1: starts at 2 and the height is 5. This means 5 counts of 2.
Bar 2: starts at 4 and the height is 1. This means 1 count of 4. … and so on.
The idea behind the assignment: Use the x and y values to draw rectangles.
Suggestions: Make the Xscale and Yscale a bit larger than the min and max so the bar graph has a margin.
Tracing the trick for this assignment
Challenge: instead of drawing the bars at 2 or 3 or 4, draw then starting at 1.5, 2.5, 3.5 so the middle of the bar for 2 is on 2.
Labels are extra credit.