# PROGRAMMING PROBLEMS

THESE ARE THE FOLLOWING PROBLEMS

** Homework assignment**

1. Write a program to sort a list of social security numbers using heapsort.

2. Write a program to sort a list of social security numbers using radix sort. You can assume that there are about 10 million numbers to be sorted. Choose the radix carefully to make your program fast.

3. Compare the running times of your two sorting programs.

**Homework assignment**

1. Write a program to solve the *maximum subsequence problem* discussed in class on September 29. Your program should run in linear time. Your program should prompt for a file name from which to read the input, which will consist of a sequence of integers separated by blank space, e.g., **1 -2 4 -3 2 4 -5 1 3**. Unlike the solution given in class, your program should output the actual *subsequence* with maximum sum. For the example given here, the correct output would be **4 -3 2 4**.

2. Write a program to solve the one-one subfunction problem discussed in class on September 29. Your program should use the algorithm given in class and run in linear time. Your program should prompt for a file name from which to read the input, which will consist of the values *f(1) f(2) ... f(n)* separated by blank space, e.g., **3 1 1 5 5 4 6**. The output from your program should be a sequence of numbers, in increasing order, separated by spaces. For the example given here the correct output would be **1 3 5**.

**Homework assignment

** Write programs to solve the longest common subsequence problem. You should implement all three algorithms discussed in class

* divide and conquer (exponential time)

* memoization

* dynamic programming

and compare their running times in practice.

Modify your dynamic programming solution to assignment above so that it creates a table of lengths only, but not a table of strings. Then use the traceback technique presented in class to construct the common subsequence. (See also pages 354-355 for a slightly different method. Note the use of tail recursion, which reverses the order of characters.)

Compare the running time of this program to the running time of your old program that used table of strings.

## Deliverables

1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done.

## Platform

unix, c ,c ++ MS Visual C++, MS Visual Basic.

but preferablly c or c++ ONLY.

( 5 comentários ) United States

ID do Projeto: #2660484

## Concedido a:

ovhyvw

See private message.

\$10 USD em 2 dias
(1 Comentário)
0.0

## 7 freelancers estão ofertando em média \$7 para esse trabalho

Gr8Coders

See private message.

\$6.8 USD in 2 dias
(52 Comentários)
4.9
dcrs

See private message.

\$4.25 USD in 2 dias
(11 Comentários)
4.6
shashikhanvw

See private message.

\$8.5 USD in 2 dias
(15 Comentários)
3.8
thanasisk

See private message.

\$8.5 USD in 2 dias
(5 Comentários)
0.9
aoacoder

See private message.

\$6.8 USD in 2 dias
(4 Comentários)
0.4
laurrl

See private message.

\$4.25 USD in 2 dias
(1 Comentário)
0.0