(5/5)

Hire Me
(5/5)

Hire Me
(5/5)

Hire Me
(5/5)

Hire Me

# For small input instances, n 30, you may output your results to the command window. Larger input instances must be written to a file. In either case, you may need to produce an output file for trace runs or asymptotic performance analysis.

INSTRUCTIONS TO CANDIDATES
###### ANSWER ALL QUESTIONS

For small input instances, n 30, you may output your results to the command window. Larger input instances must be written to a file. In either case, you may need to produce an output file for trace runs or asymptotic performance analysis.

1. Closest Pairs [30 points]

There are several practical applications of this algorithm, such as, moving objects in a game, classification algorithms, computational biology, computational finance, genetic algorithms, and N -body simulations.

• [5 points] Construct a brute-force algorithm for finding the closest pair of points in a set of n points in a two-dimensional plane and show the worst-case big-O estimate for the number of operations used by the algorithm. Hint: First determine the distance between every pair of points and then find the points with the closest

• [5 points] Implement the brute-force algorithm from part (a).

• [10 points] Given a set of n points (x1, y1), ..., (xn, yn) in a two dimensional plan, where the distance be- tween two points (xi, yi) and (xj, yj) is measured by using the Euclidean distance (xi xj)2  + (yi      yj)2, design an algorithm to find the closest pair of points that can be found in an efficient way and the worst- case big-O

• [10 points] Implement the algorithm from part (c) with the following methods:
1. [5 points] The distance of the closest pair of points. Return the distance between closest single pair
• [5 points] The distance of the closest m pairs of points, where m (n-1). Return the distances between the closest m pairs of points.
1. Deterministic Turing Machine (DTM) [70 points/10 available extra credit points]

In this problem you will implement four variants of a DTM. A DTM consists of the following:

• A finite state control,
• A infinitely long tape divided into tape squares, and
• [30 points] Design and code software implementing a generic DTM. Your generic DTM should have a finite state control mechanism that can be tailored for each parts (b) - (e). Your implementation must address each of the DTM components: a finite state control, an infinitely long tape divided into tape squares, and a read-write
• [10 points] Tailor your DTM from (a) to implement
1. [5 points] Using the input  tape contents produce trace runs for your
2. [5 points] Define at least four other input tapes and produce trace runs for your
• [15 points] Tailor your DTM from (a) to implement binary addition - The tape will need to handle variable length binary inputs, g., tape values of 101100101 add 101 or add 101101101.

Table 2: Binary Addition Rules

 Operation x + xt Result Carry 0 + 0 0 0 0 + 1 1 0 1 + 0 1 0 1 + 1 0 1

• [15 points] Tailor your DTM from (a) to implement binary subtraction - The tape will need to handle variable length binary inputs, g., tape values of 101100101 subtract 101 or subtract 101101.

Table 3: Binary Subtraction Rules

 Operation x − xt Result Borrow 0 − 0 0 0 0 − 1 1 1 1 − 0 1 0 1 − 1 0 0

• Extra Credit [10 points] Tailor your DTM from (a) to implement binary multiplication - The tape will need to handle variable length binary inputs, g., tape values of 101100101 multiply 101 or multiply 1011.

Table 4: Binary Multiplication Rules

 Operation x × xt Result 0 × 0 0 0 × 1 0 1 × 0 0 1 × 1 1

## Related Questions

##### . The fundamental operations of create, read, update, and delete (CRUD) in either Python or Java

CS 340 Milestone One Guidelines and Rubric  Overview: For this assignment, you will implement the fundamental operations of create, read, update,

##### . Develop a program to emulate a purchase transaction at a retail store. This  program will have two classes, a LineItem class and a Transaction class

Retail Transaction Programming Project  Project Requirements:  Develop a program to emulate a purchase transaction at a retail store. This

##### . The following program contains five errors. Identify the errors and fix them

7COM1028   Secure Systems Programming   Referral Coursework: Secure

##### . Accepts the following from a user: Item Name Item Quantity Item Price Allows the user to create a file to store the sales receipt contents

Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip

##### . The final project will encompass developing a web service using a software stack and implementing an industry-standard interface. Regardless of whether you choose to pursue application development goals as a pure developer or as a software engineer

CS 340 Final Project Guidelines and Rubric  Overview The final project will encompass developing a web service using a software stack and impleme

Get Free Quote!

414 Experts Online