Assignments for COM 1390
Summer 1996

[ Problem Set 1
| Problem Set 2
| Program 1
| Problem Set 3
| Problem Set 4
| Problem Set 5
| Program 2 ]

Problem Set 1

Assigned Wednesday, 19 June
Due Wednesday, 26 June

  Exercise 1.1-3 (p 5)
           1.2-2 (p 11)
           1.2-4 (p 11)
           1.3-3 (p 15)
  Problem  1.1   (p 17)

Problem Set 2

Assigned Wednesday, 26 June
Due Wednesday, 3 July

  Exercise 2.1-4 (p 31)
           3.2-2 (p 52)
           4.1-1 (p 57) (use induction, not the master method)
  Problem  2.2   (p 38)

  Prove:  If P is a computational problem that has only a finite
  number of instances, and A is a correct algorithm for P, then
  the running time of A is Theta(1).

Program 1 Assigned: 3 July
Due: 15 July

Part 1: Implement the insertion sort and merge sort algorithms. You may use any language or system you like, but you must use the same language and system for both algorithms. (See Notes 1 and 2 below.)

Part 2: Design a set of experiments that will illustrate the best, worst, and average case behavior of the insertion sort algorithm.

Part 3: Write a program that will collect the data for the experiments you designed. This program should call your insertion sort with different kinds and sizes of data, and collect the timing data for each call.

Part 4: Collect timing data for both insertion sort and for merge sort.

Part 5: Plot the data collected in Part 4, using four separate curves for:

• the best-case behavior of insertion sort
• the average-case behavior of insertion sort
• the worst-case behavior of insertion sort
• the behavior of merge sort

Hand in:

1. a listing of your implementation of the algorithms.
2. a list of the tests to be performed during the experiments designed in Part 2.
3. a listing of the program you wrote for Part 3.
4. a table showing the timings collected in Part 4.
5. the graphs plotted in Part 5.

Note 1: The point of this assignment is to compare the performance of algorithms, not to practice your programming skills, so you are allowed to use implementations of these algorithms that were written by other people, such as library routines, provided you and I are authorized to copy and to use the source code. If you use code that was written by someone else, then you must acknowledge its author(s) and describe the circumstances under which you and I may lawfully use it.

Note 2: You may work in teams of no more than three people. If you work as a team, please turn in only one copy of your team's work with all of the names at the top.

Problem Set 3

Assigned Wednesday, 17 July
Due Wednesday, 24 July

  Exercise 7.3-2 (p 147)
           7.4-2 (p 149)
           8.1-2 (p 155)
           8.2-1 (p 160)
  Problem  8-3   (p 169)

Problem Set 4

Assigned Monday, 29 July
Due Monday, 5 August

  Exercise 12.2-2 (p 226)
           12.2-6 (p 226)
           12.3-1 (p 231)
           13.1-2 (p 246)
           13.1-5 (p 246)

Problem Set 5

Assigned Monday, 5 August
Due Monday, 12 August

  Exercise 13.2-2 (p 250)
           13.3-3 (p 254)
  Problem  14-1 parts b, c, d (p 278)

Program 2

Assigned Monday, 12 August
Due Wednesday, 21 August

To avoid any conflict with studying for final exams, the standard late policy will not be used for this assignment. Late assignments will be accepted until the end of class on Thursday, 23 August. NO ASSIGNMENTS WILL BE ACCEPTED AFTER 10:20 AM THURSDAY, 23 AUGUST.

No teamwork is allowed for this assignment. You must work on it by yourself.

Your assignment is to do Problem 16-2 on page 325 of the book. Instead of expressing your algorithm as pseudocode, however, you must express your algorithm as a Pascal, C, or C++ procedure named ChooseLineBreaks.

C and Pascal code for a crude text formatter is available by clicking here. This text formatter includes two implementations of the ChooseLineBreaks procedure. One implementation uses an optimal but inefficient algorithm. Another implementation uses a greedy but suboptimal algorithm. Your job is to write an implementation of ChooseLineBreaks that is both optimal and efficient.

The arguments to ChooseLineBreaks are as follows:

  n     is the number of words in the paragraph to be printed.
  L     is an array of the word lengths.  (In the Pascal version,
        L[1] is the length of the first word.  In the C version,
        L[0] is the length of the first word.)
  M     is the maximum length of a line.
  B     is an array of n booleans.  Its contents are undefined
        when ChooseLineBreaks is called.  ChooseLineBreaks returns
        the optimal set of line breaks by setting B[i] to true if
        word i is the last word of a line but is not the last word
        of the entire paragraph.  Otherwise ChooseLineBreaks sets
        B[i] to false.  (In the Pascal version, B[1] indicates
        whether a newline should follow the first word.  In the
        C version, B[0] indicates whether a newline should follow
        the first word.)

Hand in:

1. a paper listing of your implementation of ChooseLineBreaks and any other procedures or global variables that you used to implement ChooseLineBreaks.
2. an analysis of the asymptotic running time and space requirements of your implementation of ChooseLineBreaks.

Please do not waste paper by turning in a listing of the entire text formatter.