Continuing on binary input and output alphabets
Wait for a short while. In support of these steps, the StdDraw has several methods: The "Hello, World" program for animation is to produce a black ball that appears to move around on the canvas, bouncing off the boundary according to the laws of elastic collision. We do so in four steps: Clear the offscreen canvas to white. Draw a black ball at the new position on the offscreen canvas. Copy the offscreen canvas to the onscreen canvas.
To create the illusion of movement, BouncingBall. Our standard draw library supports drawing pictures as well as geometric shapes. Our standard draw library also includes methods so that the user can interact with the window using the mouse. It draws a blue ball, centered on the location of the mouse. When the user holds down the mouse button, the ball changes color from blue to cyan.
It also accounts for a drag force. When the user clicks, the balls disperse randomly. StdAudio is a library that you can use to play and manipulate sound files.
It allows you to play, manipulate and synthesize sound. We introduce some some basic concepts behind one of the oldest and most important areas of computer science and scientific computing: Concert A is a sine wave, scaled to oscillate at a frequency of times per second. The amplitude y -value corresponds to the volume. A simple mathematical formula characterizes the other notes on the chromatic scale.
They are divided equally on a logarithmic base 2 scale: When you double or halve the frequency, you move up or down an octave on the scale. For example hertz is one octave above concert A and hertz is two octaves below concert A. For digital sound, we represent a curve by sampling it at regular intervals, in precisely the same manner as when we plot function graphs.
We sample sufficiently often that we have an accurate representation of the curve—a widely used sampling rate is 44, samples per second. It is that simple: For example, the following code fragment plays concert A for 10 seconds. It takes notes from standard input, indexed on the chromatic scale from concert A, and plays them on standard audio. Exercises Write a program MaxMin.
Write a program Stats. Write a program LongestRun. For example, if the input is 1 2 2 1 5 1 1 7 7 7 7 1 1 , then your program should print Longest run: Write a program WordCount.
For the purpose of this exercise, a word is a sequence of non-whitespace characters that is surrounded by whitespace. Write a program Closest. For efficiency, do not use Math. Given the positions and masses of a sequence of objects, write a program to compute their center-of-mass or centroid.
The centroid is the average position of the n objects, weighted by mass. If the positions and masses are given by x i , y i , m i , then the centroid x , y , m is given by: Write a program Checkerboard. Color the lower-left square red. Write a program Rose. Write a program Banner. Add a second command-line argument to control the speed. Write a program Circles. Your program should take four command-line arguments: Write a program Spirograph.
A spirograph technically, an epicycloid is a curve formed by rolling a circle of radius r around a larger fixed circle or radius R.
For a dramatic 3d effect, draw a circular image, e. Write a program Clock. Use the method StdDraw. Write a program Oscilloscope. These patterns are named after the French physicist, Jules A. Lissajous, who studied the patterns that arise when two mutually perpendicular periodic disturbances occur simultaneously.
Assume that the inputs are sinusoidal, so tha the following parametric equations describe the curve: The other has parameters 1, 1, 5, 3, 30, 45 Web Exercises Word and line count. Write a program Rainfall.
Write a program Duplicates. Write a program RunLengthEncoder. Write a program RunLengthDecoder. Print the whole file if it consists of Print a random word. Read a list of N words from standard input, where N is unknown ahead of time, and print out one of the N words uniformly at random.
Do not store the word list. Instead, use Knuth's method: Print out the word that survives after reading in all of the data. Julius Caesar sent secret messages to Cicero using a scheme that is now known as a Caesar cipher. Each letter is replaced by the letter k positions ahead of it in the alphabet and you wrap around if needed. Write a program Caesar. If a letter is not an uppercase letter, simply print it back out.
How would you decode a message encrypted using a Caesar cipher? A Boolean matrix has the parity property when each row and each column has an even sum. This is a simple type of error-correcting code because if one bit is corrupted in transmission bit is flipped from 0 to 1 or from 1 to 0 it can be detected and repaired. Here's a 4 x 4 input file which has the parity property: Use as little internal storage as possible. You are interviewing N candidates for the sole position of American Idol.
Every minute you get to see a new candidate, and you have one minute to decide whether or not to declare that person the American Idol. You may not change your mind once you finish interviewing the candidate. Suppose that you can immediately rate each candidate with a single real number between 0 and 1, but of course, you don't know the rating of the candidates not yet seen.
Write a program Diamonds. Create a function to plot an N-gon, centered on x, y of size length s. Use the function to draws nested polygons like the picture below. Write a program BulgingSquares. Suppose that N mice that start on the vertices of a regular polygon with N sides, and they each head toward the nearest other mouse in counterclockwise direction until they all meet. Write a program to draw the logarithmic spiral paths that they trace out by drawing nested N-gons, rotated and shrunk as in this animation.
Write a program to draw a spiral like the one below. Write a program Globe. Write a program RandomText. Write a program RandomWalk. Start at the center of a 2N-by-2N grid. The current location is displayed in blue; the trail in white. You are seated at a rotating square table like a lazy Susan , and there are four coins placed in the four corners of the table. Your goal is to flip the coins so that they are either all heads or all tails, at which point a bell rings to notify you that you are done.
You may select any two of them, determine their orientation, and optionally flip either or both of them over. To make things challenging, you are blindfolded, and the table is spun after each time you select two coins. Write a program RotatingTable. Then, it prompts the user to select two positions , and identifies the orientation of each coin. Next, the user can specify which, if any of the two coins to flip. The process repeats until the user solves the puzzle. Write another program RotatingTableSolver.
One effective strategy is to choose two coins at random and flip them to heads. However, if you get really unlucky, this could take an arbitrary number of steps. Hex is a two-player board game popularized by John Nash while a graduate student at Princeton University, and later commercialized by Parker Brothers.
It is played on a hexagonal grid in the shape of an by diamond. Write a program Hex. Projectile motion with drag. Write a program BallisticMotion. Account for gravitational and drag forces. Assume that the drag force is proportional to the square of the velocity. Using Newton's equations of motions and the Euler-Cromer method, update the position, velocity, and acceleration according to the following equations: Write a program Heart. Draw a diamond, then draw two circles to the upper left and upper right sides.
Write a program that draws a square and changes its color each second. Repeat the previous exercise, but animate the Lissajous patterns as in this applet.
Bresenham's line drawing algorithm. To plot a line segment from x1, y1 to x2, y2 on a monitor, say by, you need to make a discrete approximation to the continuous line and determine exactly which pixels to turn on. Write a program Madness. You should get the following complex picture. Experiment by changing the parameters and produce original pictures.
Write a program Butterfly. You should get an image like the following butterfly-like figure. The first line contains an integer N that specifies the number of students in the database. Each of the next N lines consists of four pieces of information, separated by whitespace: Then, the program prints out a list of students in section 4 and 5.
In the October 7, California state runoff election for governor, there were official candidates. To avoid the natural prejudice against candidates whose names appear at the end of the alphabet Jon W. Zellhoefer , California election officials sought to order the candidates in random order.
Write a program program Shuffle. California decided to randomize the alphabet instead of shuffling the candidates. Using this strategy, not all N! For example, two candidates with very similar last names will always end up next to each other.
Write a program Reverse. This problem investigates two methods for forecasting in time series analysis. Moving average or exponential smoothing. Create any of these polar plots.
Consider the following program. Shuffle a deck of cards, and deal one to the player. Prompt the player to guess whether the next card is higher or lower than the current card. Repeat until player guesses it wrong. Write a program CollidingBalls.
Assume all the balls have the same mass. An NFA accepts a string if there is any sequence of transitions that can take the machine from the start state to an accept state. In the NFA at left, when in state 0 and reading an a , it can choose to stay in state 0 or make the transition to state 1. It recognizes binary strings whose second-to-last symbol is a.
In the NFA at right, when it state 0, it can follow the null transition to state 1, without consuming an input symbol. It recognizes binary strings that do not contain the substring bba. There is a striking connection among regular expressions, DFAs, and NFAs that has dramatic practical and theoretical consequences.
Kleene's theorem serves as the basis for a solution to the recognition problem for REs. Simulate the operation of the NFA on the given input string. That is the approach taken by Java to implement its matches method that we considered earlier.
Limits on the power of DFAs. For example, the language containing all binary strings with an equal number of a and b symbols is not regular. Machines with more power.
One simple way to define a machine that can recognize more languages is to add a pushdown stack to the DFA, yielding a machine known as a pushdown automaton PDA.
It is not difficult to develop a PDA that can recognize binary strings with an equal number of a and b symbols. In the next section, we will consider Turing machines , which is the abstract machine that lies at the heart of computer science.
Exercises Give an RE that specifies each of the following languages over the binary alphabet. All strings except empty string Contains at least three consecutive b s Starts with a and has odd length, or starts with b and has even length No consecutive b s Any string except bb or bbb Starts and ends with the same symbol Contains at least two a s and at most one b Solutions: Write a Pattern and Matcher client Harvester.
Develop a program WebCrawler. Write a filter SearchAndReplace. Write a regular expression for each of the following sets of binary strings.
Use only the basic operations. The last one is by far the trickiest. Write a regular expression for binary strings with at least two 0s but not consecutive 0s. For each of the following, indicate how many bit strings of length exactly are matched by the regular expression: Write a Java regular expression to match phone numbers, with or without area codes. The area codes should be of the form or Find all English words that end with nym.
Final all English words that contain the trigraph bze. Find all English words that start with g, contain the trigraph pev and end with e. Find all English words that contain the trigraph spb and have at least two r's. Find the longest English word that can be written with the top row of a standard keyboard. Find all words that contain the four letters a, s, d, and f, not necessarily in that order. Write a Java regular expression, for use with Validate. Modify the previous exercise to make the - optional, so that is considered a legal input.
Write a Java regular expression to match all strings that contain exactly five vowels and the vowels are in alphabetical order. Write a Java regular expression to match valid OS X file names. Such a file name consists of any sequence of characters other than a colon. Additionally, it cannot begin with a period. Given a string s that represents the name of an IP address in dotted quad notation, break it up into its constituent pieces, e.
Make sure that the four fields are numeric. Write a Java regular expression to describe valid IP addresses of the form a. Write a Java regular expression to match license plates that start with 4 digits and end with two uppercase letters. Write a regular expression to extract the coding sequence from a DNA string. Write a regular expression to check whether a sequence contains two or more repeats of the the GATA tetranucleotide.
Write a Java regular expression to match various spellings of Libyan dictator Moammar Gadhafi's last name using the folling template: Here the notation [x] means 0 or 1 copy of the letter x. Write a program Clean. In Java, use Pattern. Write a program Title. Solution has length exponential in n. Each state represents whether the input string read in so far ends with 00, 01, 10, or Draw a 3-state DFA that accomplishes the same task. Draw a DFA for bitstrings with at least one 0 and at least one 1.
Draw an NFA that matches all strings that contain either a multiple of three 0s or a multiple of five 1s. Draw an NFA that recognize the language of all strings that end in aaab. Draw an NFA that recognize the language of all strings whose 4th to the last character is a. Draw an NFA that recognize the language of all strings whose 5th to the last character is a. Give a NFA with 5 accept states. Write an equivalent NFA that has exactly one accept state. Given an DFA that accepts bitstrings with a multiple of three 0s and a multiple of five 1s.
Mealy and Moore machines. DFA with output on each transition edge. DFA with output on each state. Web Exercises Text-to-speech synthesis. Original motivation for grep. Write a program to replace all of the r's with h's to translate a sentence like "Park the car in Harvard yard" into the Bostonian version "Pahk the cah in Hahvahd yahd".
Write a program that takes the name of a file as a command line argument and prints out its file type extension. The extension is the sequence of characters following the last. For example the file sun. For web log analysis, it is convenient to organize web traffic based on subdomains like wayne.
Write a program to read in a domain name and print it out in reverse order like edu. You just witnessed a bank robbery and got a partial license plate of the getaway vehicle.
It started with ZD , had a 3 somewhere in the middle and ended with V. Help the police officer write regular expression for this plate. Read in a text file and print out all quote strings. Given a string s, determine whether it is a subsequence of another string t. For example, abc is a subsequence of achfdbaabgabcaabg.
Use a regular expression.