代写data留学生、代做c/c++语言、代写Python，Java程序设计

日期：2020-06-24 10:38

You must choose 2 topics to finish, respectively one

from 1-4, the other from 5-8. Project 1: 24-point game

Problem Description:

The 24-point game is to pick any four cards from 52 cards, as shown in the figure below. Note that two

Jokers are excluded. Each card represents a number. An Ace, King, Queen, and Jack represent 1, 13, 12, and 11, respectively. Enter an expression that uses the four numbers from the four selected cards. Each

number must be used once and only once. You can use the operators (addition, subtraction, multiplication, and division) and parentheses in the expression. The expression must evaluate to 24. After entering the expression, click the Verify button to check whether the numbers in the expression

are currently selected and whether the result of the expression is correct. Display the verification in a

dialog box. Note that such an expression might not exist. In this case, click the Refresh button to get

another set of four cards. Assume that images are stored in files named 1.png, 2.png, ..., 52.png, in the

order of spades, hearts, diamonds, and clubs. So, the first 13 images are for spades 1, 2, 3, ..., and 13.

Figure 1 24-point game

Your program should also enable the computer to display the expression if one exists, as shown in the

figure. Otherwise, report that the expression does not exist. Project 2: Baby name popularity ranking

Problem Description:

The Popularity ranking of baby names from years 2001 to 2010 is downloaded form www.ssa. gov/oact/babynames and stored in files names babynamerankong2001.txt, babynameranking2002.t

xt, ... , babynameranking2010.txt. Write a program that enables the user to select a year, gende

r, and enter a name to display the ranking of the name for the selected year and gender, as s

hown in the following figure. To achieve the best efficiency, create two arrays for boy’s name

s and girl’s names, respectively. Each array has 10 elements for 10 years. Each element is a

map that stores a name and its ranking in a pair with the name as the key.

Figure 2.1 The user selects a year, gender, and enters a year and clicks the Find Ranking button

to display the ranking in a dialog box. Project 3: Convex Hull

Problem Description:

Given a set of points, a convex hull is a smallest convex polygon that encloses all these points, as

shown in Figure 3.1a. A polygon is convex if every line connecting two vertices is inside the polygon. For example, the vertices v0, v1, v2, v3, v4, and v5 in Figure 3.1a form a convex polygon, but not in

Figure 3.1b, because the line that connects v3 and v1 is not inside the polygon.

v5 (a) A convex hull (b) A non-convex polygon (c) convex hull animation Figure 3.1 A convex hull is a smallest convex polygon that contains

a set of points. Convex hull has many applications in game programming, pattern recognition, and image processing. Before we introduce the algorithms, it is helpful to get acquainted with the concept using an interactive

tool from liveexample.pearsoncmg.com/dsanimation/ConvexHull.html, as shown in Figure 3.1c. The

tool allows you to add/remove points and displays the convex hull dynamically. Many algorithms have been developed to find a convex hull. An intuitive approach, called the

gift-wrapping algorithm, works as follows:

Step 1: Given a list of points S, let the points in S be labeled s0, s1, ..., sk. Select the rightmost lowest

point h0 in S. As shown in Figure 3.2a, h0 is such a point. Add h0 to the convex hull H. H is a list

initially being empty. Let t0 be h0. Step 2: Let t1 be s0. For every point p in S

if p is on the right side of the direct line from t0 to t1 then

let t1 be p. (After Step 2, no points lie on the right side of the direct line from t0 to t1, as shown in Figure 3.2b.)

Step 3: If t1 is h0 (see Figure 3.2d), the points in H form a convex hull for S. Otherwise, add t1 to H, let

t0 be t1, and go to Step 2 (see Figure 3.2c).

t0 t1 = h0 (a) Step 1 (b) Step 2 (c) repeat Step 2 (d) H is found

Figure 3.2 (a) h0 is the rightmost lowest point in S. (b) Step 2 finds

point t1. (c) A convex hull is expanded repeatedly. (d) A convex hull

is found when t1 becomes h0. Project 4: Execution time for Sorting

Problem Description:

Write a program that obtains the execution time of selection sort, radix sort, bubble sort, merge

sort, quick sort, and heap sort for input size 50000, 100,000, 150,000, 200,000, 250,000, and

300,000. Your program should create data randomly and print a table like this:

Selection Sort Radix Sort Bubble Sort Merge Sort Quick Sort Heap Sort

50000

In the same program, obtain the execution time of selection sort, radix sort, bubble sort, and heap

sort for input size 2,000,000, 3,000,000, 4,000,000, and 5,000,000. Project 5: Data Compression

Problem Description:

Huffman codng compresses data by using fewer bits to encode characters that occur more

frequently. The codes for the characters are constructed based on the occurrence of the characters

in the text using a binary tree, called the Huffman coding tree. Suppose the text is “Mississipi”, Its Huffman tree is as shown in Figure 5.1a. The left and right

edges of a node are assigned the values 0 and 1, respectively. Each character is a leaf in the tree. The code for character consists of the edge values in the path from the root to the leaf, as shown in

Figure 5.2b.

Figure 5.1 The codes for characters are constructed based on the

occurrence of characters in the text using a coding tree.

(1) Write a program that prompts the user to enter a file name, obtains the Huffman codes for the

characters in the file, and encodes the text into a new file. For example, if the original file is

named abc.txt, the encoded file should be named as abc.txt.new. (2) Write a program that decompresses the file created in (1). The program prompts the user to

enter two file names. The first one is the source and the second one is the target. The program

decompresses the source into the target. Here is a sample run:

<output>

Enter the source file: abc.txt

Enter the target file: temp.txt

<end output>

Project 6：The Nine Tails Problem

Problem Description:

The nine tails problem is as follows. Nine coins are placed in a 3 * 3 matrix, with som

e face up and some face down. A legal move is to take any coin that is face up and r

everse it, together with the coins adjacent to it(this does not include coins thet are diag

onally adjacent). Your task is to find the minimum number of moves that lead to all coins being face do

wn. For example, start with the nine coins as shown in Figure 6.1a. After you flip the s

econd coin in the last row, the nine coins are now as shown in Figure 6.1b. After you f

lip the second coin in the first row, the nine coins are all face down, as shown in Figur

e 6.1c. See liveexample.personcmg.com/dsanimation/NineCoin.html for the interactive dem

o.

Figure 6.1 The problem is solved when all coins are face down. Write a program that prompts the user to enter an initial state of the nine coins and displays the

solution, as shown in the following sample run:

Hints: The nine tails problem can be reduced to the shortest path problem. Project 7: The Connected Circle Problem

Problem Description:

In the connected circles problem, you determine whether all the circle in a two-dimensional

plane are connected. If all the circles are connected, they are pained as filled circle, as shown in

Figure 7.1a. Otherwise, they are not filled, as shown in Figure 7.2b.

Figure 7.1 You can apply DFS to determine whether the circles are connected. Write a program that lets the user create a circle by clicking a mouse in a blank area that is not

currently covered by a cicle. As the circles are added, the circles are repained filled if they are

connected of unfilled otherwise. Hints:This problem can be solved using a depth-first traversal. Project 8: Build Bridges

Problem Description:

There are eight small islands in a lake, and the state wants to build seven bridges to connect

them so that each island can be reached from any other one via one or more bridges. The cost of

constructing a bridge is proportional to its length. The distances between pairs of islands are

given in the following table. 1 2 3 4 5 6 7 8

1 - 240 210 340 280 200 345 120

2 - - 265 175 215 180 185 155

3 - - - 260 115 350 435 195

4 - - - - 160 330 295 230

5 - - - - - 360 400 170

6 - - - - - - 175 205

7 - - - - - - - 305

8 - - - - - - - - Write a program to find which bridges to build to minimize the total construction cost. Hints:MST