Content for some questions:
From 
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)
classwork:
Write a program, ArrayBasics_YI.java to do the following:
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
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.
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
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.
Looking at the printf method
A printf format reference page (cheat sheet)
// This class shows how to initialize an array
// How to use the printf output formatting method
public class InitPrintfArray
{
public static void main( String[] args )
{
// initializing the array when it is created
int[] arrayA = { 87,56,78,99,102 };
System.out.printf( "%s%7s\n", "Index", "Value" ); // column headings
// output each array element's value
for ( int i = 0; i < arrayA.length; i++ )
System.out.printf( "%5d%5d\n", i, arrayA[ i ] );
} // end main
} // end class InitPrintfArray
A "simplified" version of a bar chart by using the elements of an array as counters
// Bar graph printing program.
public class BarGraph
{
public static void main( String[] args )
{
int[] arrayA = { 0, 0, 0, 0, 0, 0, 1, 2, 4, 2, 1 };
System.out.println( "Grade distribution:" );
// for each array element, output a bar of the chart
for ( int i = 0; i < arrayA.length; i++ )
{
// output bar label ( "00-09: ", ..., "90-99: ", "100: " )
if ( i == 10 )
System.out.printf( "%5d: ", 100 );
else
System.out.printf( "%02d-%02d: ",
i * 10, i * 10 + 9 );
// print bar of asterisks
for ( int stars = 0; stars < arrayA[ i ]; stars++ )
System.out.print( "*" );
System.out.println(); // start a new line of output
} // end outer for
} // end main
} // end class BarGraph
Grade distribution:
00-09:
10-19:
20-29:
30-39:
40-49:
50-59:
60-69: *
70-79: **
80-89: ****
90-99: **
100: *
Claswork/Homework:
Tracing 101: Trace the i, arrayA[i], and the output as the inner and outer loops traverse arrayA.
A school has 100 lockers and 100 students. All lockers are closed on the first day of school. As the students enter, the first student, denoted S1, opens every locker. Then the second student, S2, begins with the second locker, denoted L2, and closes every other locker. Student S3 begins with the third locker and changes every third locker (closes it if it was open, and opens it if it was closed). Student S4 begins with locker L4 and changes every fourth locker. Student S5 starts with L5 and changes every fifth locker, and so on until student S100 changes L100.
After all the students have passed through the building and changed the lockers, which lockers are open?
Write a program, WhichLockers_YI.java to find your answer and display all open locker numbers separated by exactly one space.
Hint: Use an array of 100 Boolean elements, each of which indicates whether a locker is open (true) or closed (false). Initially, all lockers are closed.
Classwork/Homework:
Magic squares. A n × n matrix that is filled with the numbers 1,2,3,…,n^2 is a magic square if the sum of the elements in each row, in each column, and in the two diagonals is the same value.
Write a program that reads in 16 values from the keyboard and tests whether they form a magic square when put into a 4 × 4 array. This is only an example of a 4 x 4 square.
You need to test two features:
1. Does each of the numbers 1, 2, …, 16 occur in the user input?
2. When the numbers are put into a square, are the sums of the rows, columns, and diagonals equal to each other?
Testing and output:
1. Display the given magic square and the value rows, columns and diagonals add up to.
2. Find one more magic square online, display it and show the value all the columns, rows and diagonals are equal to.
3. Display a square that it is not magic but it follows the rules of being filled 1 through n^2.
NOTE: print the input numbers in matrix format, rows by columns.
Strong Recommendation:
Follow the rules by tracing them on paper first. Then, find a pattern!
Animations using java
Classwork:
Simple harmonic motion. Create an animation like the one below from Wikipedia of simple harmonic motion. This is not an OOP.
Classwork/Homework:
Write a program, YI_ErathosPrimes.java to find the all the prime numbers less than or equal to 120 using the Sieve of Eratosthenes algorithm.
