Analysis of Algorithms

Course Index Return to Dr. Margush's page

Note: Assignments to be emailed MUST use one of the following subject lines (with n set to the assignment number):

• Analysis of Algorithms Assignment n

Assignment list - most recent listed first

Due Apr 23: Assignment 10: Submit a well documented program and brief report for the following problem: 

• Write a program to search for strings in text. Implement all three string search methods. For each search, count and report the number of fundamental operations required to locate the matches. In the Rabin-Karp method, use ASCII codes and do calculations modulo 9973 (a prime number); for preprocessing and matching separately, report number of multiplications and string comparisons. In the KMP and Boyer-Moore algorithms, count the preprocessing work and matching separately, reporting the number of character comparisons. Data file: data.txt and answers.txt (shifts are not shown, but the number of matches is listed and is woefully wrong - there a lot more matches than the answers indicate... sorry. I cannot find the program that generated the data so I am not going to fix it. Feel free to suggest answers or compare. You should do OK if different algorithms report the same results.) The data file has a pattern (one line) followed by text (one line) to be searched. This repeats (pattern/text pairs) to the end of file.

Due Apr 12: Assignment 9: Submit solutions to the following problems: 

• 26.1-9
• 26.2-1,2,3
• 26.3-1

Due Apr 5: Assignment 8: Submit solutions to the following problems: 

• 23.1-1,2
• 24.1-1,4
• 24.2-1
• 24.3-1
• 25.1-1
• 25.2-1
• 25.3-1

Due Mar 31: Assignment 7: Submit solutions to the following problems: 

• 21.3-3
• 22.1-1,6
• 22.2-1,2,3
• 22.3-1,2,11
• 22.4-1,2

Due Mar 12: Assignment 6: Implement a solution to the activity-selection problem using a dynamic programming approach. Input should be from a text file named activity.txt containing lines with 2 integers representing a series of scheduling problems to be solved. Each problem starts with a non-zero pair and ends with a 0 0 entry. Activity times are assumed to be ordered by stop time. The last problem has another line with 0 0 on it. For each scheduling problem, display an optimal set of activities. (Here is a bigger test file)(and answers)

Sample input:

1 4
2 6
1 6
3 8
5 8
6 8
1 8
3 9
10 12
0 0
2 5
3 7
5 8
2 8
1 9
0 0
0 0

Sample output:

Problem 1: {1, 5, 9}
Problem 2: {1, 3}

Due Feb 23: Assignment 5: Dynamic Programming - find a problem solvable using the dynamic programming approach. Be prepared to present the problem and solution in class.

Due Feb 20: Assignment 4: Solve the following problems using a dynamic programming approach. Provide a table to justify your answer and include a narrative explaining the solution process.

1. You must move from the left end of the table to the right by going to the right or up or down, one cell at a time. You enter at A1, B1 or C1 and exit at A6, B6, or C6. The cost of the 'trip' is the sum of the numbers in the cells you pass through. Find the least cost trip from A to B (cost and sequence of cells).

2. Find the best association for the matrix multiplication A₁A₂A₃A₄A₅A₆ where the sizes of the matrices are 3x4, 4x6, 6x2, 2x7, 7x3, and 3x1. Determine the minimum number of scalar multiplications required by your solution.

Due Feb 16: Assignment 3: Program the Randomized-Select algorithm after translating it to an iterative approach. Include a counter in the algorithm to determine the number of comparisons (of array elements) required to complete its task (you will need to update this counter in the partition function). Create a test program that can call Randomized-Select on a variety of arrays and report the number of comparisons required for the selection. This test program should create a randomly ordered array of distinct integers 0..n-1, and then obtain times for selecting the 1st, median, and nth order statistics (be sure the array is unchanged by the selection process). You should also test the selection function on ordered and reverse ordered arrays. Obtain data to produce a graph showing running time for each of the input situations. Provide a written report showing the data and graphs and an analysis of the empirical results (compared to theoretical expectations). For extra credit, include data for a non-random version that illustrates the potential worst case performance. Submit a well documented copy of your program along with your report.

Due Feb 9: Assignment 3a: Answer questions (p189) 9.2-4, (p192) 9.3-6, (p193) 9.3-7.

Due Feb 2: Assignment 2: Submit neatly written solutions for the following exercises/problems from the text:

Exercises 3.1) 3,4
Exercises 4.1) 1,6
Exercises 4.2) 2,4

Due Jan 16: Assignment 1: Submit neatly written solutions for the following exercises/problems from the text:
Exercises 2.2) 1,2,3,4
Exercises 2.3) 4,6,7
Problem 2-3 a,b

Return to Dr. Margush's page