## CSci 3501 Algorithms and Computability: Assignments and Labs

[Home] [Syllabus] [Assignments and Labs] [Resources]

### Assignments

Will be added as the course progresses.

### Labs

• Lab 1. August 29, due Sept. 4 at 10pm. Work in pairs.
Design and implement an algorithm for finding all combinations of the first n integers. Input: n. Output: all possible combinations of numbers from 1 to n written one combination per line without repetitions (in any order).
Time your program using Java time function (time in milliseconds):
``` long time = System.currentTimeMillis(); ```
You need to submit the following:
1. Description of your algorithm and explanation of why it is correct
3. The result of timing the program for at least two values of n
4. Estimate (based on your timing) of how long this program will run for n = 15 and n = 20. Show how you computed the estimate.
• Lab 2. Sept. 5, due Sept. 11 at 10pm. Work in pairs.
You are given 3 bins of the same capacity B and n items of different sizes. Design and implement an algorithm to pack the items into the bins maximally utilizing the bins capacity. For instance, given B=20 and items of sizes
12, 4, 8, 15, 9, 3, 1, 10
you can pack the bins as [12, 8], [1, 4, 15], and [9, 10], with the leftover item of size 3. The data may include several elements of the same size.
• Your algorithm must not check all possibilities.
• Your algorithm does not have to find the optimal solution for all cases but it should find a good solution for most cases.
• The input includes the capacity of the bins followed by the number of items n followed by the items themselves separated by spaces. For instance, the input for the above problem is
``` 20 8 12 4 8 15 9 3 1 10 ``` Check out the resources page on description of the Scanner class which allows you to read data from Java console (standard input) easily.
Your output should be the list of elements
• You may use any of the algorithms implemented in Java Collections class. See this tutorial for details.
You need to submit the following:
• The results
• A brief explanation of your algorithm in English.
• A brief explanation of whether your algorithm always finds the optimal solution. If it does not, give an example of data for which your algorithm finds a solution that is not optimal. As an extra credit, estimate the maximum difference between your solution and the optimal one.
• Compute the complexity of your algorithm in terms of Big-O (i.e. Big-Theta of the worst case).
• Lab 3. Sept. 12, due Sept. 18 at 10pm. In this lab you will study the running time of mergesort and quicksort for various conditions. Your program will sort an array of objects of a class TestInteger. TestInteger is a class that implements Comparable (or Comparable<TestInteger> if you are using generics), has one int field and one static counter of type long. Its compareTo method that does two things:
• increments the static counter by 1
• compares the int fields of the two TestIntegers returning a positive int if `this` TestInteger is larger than the parameter, a negative int if it is smaller, and 0 if it is equal to the parameter.
You also need static methods to print and reset the counter.

You can use a predefined method sort that implements mergesort.

You need to write your own implementation of quicksort according to the algorithm in the book.

Measuring the running time of your algorithms:

1. Generate 10,000 random Integers and put them (in the same order) into two arrays. Use Java random number generator Random . The range of the integers does not matter. Make sure to use only one Random object in your program - create it in the very beginning outside of any loops.
2. Sort one using the mergesort and the other one using a quicksort.
3. Run the program 5 times measuring the time to sort the two arrays (separately) in terms of the number of comparisons (as measured by the static counter in TestInteger class). Record your results. Make sure to include only the sorting time, not the time to generate the arrays.
• Repeat the sorting, but instead of random elements use the arrays where elements are stored in increasing order. Again measure the times 5 times and record the results.
• Repeat the measurements for arrays that consist of 10 sorted sequences of 1,000 elements each (randomly choose the starting number in each sequence).
• Repeat the measurements for arrays that consist of 100 sorted sequences of 100 elements each (randomly choose the starting number in each sequence).
• Modify the quicksort so that for arrays larger than 3 elements it chooses the pivot as the middle one among the last three numbers in the array at every level of the quicksort. Repeat the 4 kinds of measurements for quicksort only.

Submit your program and the results of measurements. Also submit the answers to the questions below: what can you say about performance of mergesort and quicksort on the 4 kinds of input? Does the modification in the last part change the running time of quicksort? Why?

• Lab 4. Sept. 19. We continue studying QuickSort. Use your implementation from the previous lab to experiment with the modifications listed below. Compare your modifications to the original QuickSort, to the predefined MergeSort, and to each other. The goal is to find the most efficient implementation.

For this lab test your programs with arrays of different lengths (at least between a 100 and 10000 elements; you may also increase the upper bound, but don't worry about sorting arrays with fewer than a 100 elements - sorting for them is very fast regardless of the algorithm). Run at least 5 tests for each array size and each version of the algorithm. You need to test your program for a random array, a sorted array, and a close-to-sorted array (groups of sorted subarrays).

Important: make sure that the array is sorted correctly by each of your implementations: write a method to check the array in the end. Make sure that you don't include these comparisons in the totals that you collect for sorting.

I will post the results for the best algorithms.

Here is the list of modifications that you need to implement and test:
1. Randomized QuickSort: choose the pivot at random.
2. Optimize the middle-of-the-three modification from the previous lab:
• make sure that you are using the minimum number of comparisons to correctly choose the middle element. Note: you must use compareTo method for these comparisons so that they are included in your total.
• instead of using this approach all the way down to a 3-element array, switch to a normal partition algorithm at some size of the array k. Experiment with different values of k to find the optimal one.
3. Switch to a different sorting method (such as insertion sort or a selection sort) for smaller arrays. Again, experiment with different thresholds for the length of the "smaller" arrays. Make sure to use compareTo for all the sorting.
4. Combine the middle of the three method with the optimization in the previous task.
5. Extra credit: try other modifications of QuickSort. Explain why they should produce a more efficient algorithm. Compare them to the ones you already tried.
Make sure to record all your results in a clear and understandable way. Explain your results (i.e. if a modification speeds up the sorting, explain why; if it does not, explain why not, etc.).
• Sept. 26: Matching problem. Your task is to design and implement an algorithm that finds a solution to the following problem:

n programmers are looking for a job; n companies are looking to hire a programmer. Each programmer has a ranking of the companies based on his/her preferences for a workplace. Likewise, each company has a ranking of the n programmers based on whom they would like to hire.

Given a set of rankings, it may be impossible to find a pairing of programmers with companies when everyone gets their first choice (what would be an example of such ranking, say, among 3 programmers and companies?). However, it is possible to a satisfactory pairing. A pairing of programmers with companies is called satisfactory if there is no pair of assignments (P1, C1), (P2, C2) (denoting programmers as P and companies as C) such that P1 ranks C2 higher than C1 AND C2 ranks P1 higher than P2.

Below is an example of preferences of five companies A, B, C, D, E and five programmers 1, 2, 3, 4, 5:
A B C D E 1 2 3 4 5
2 1 5 1 2 E D D C A
5 2 3 3 3 A E B B D
1 3 2 2 5 D B C D B
3 4 1 4 4 B A E A C
4 5 4 5 1 C C A E E
The pairing A1 B3 C2 D4 E5 is unsatisfactory since A prefers programmer 2 to programmer 1 AND programmer 2 prefers company A to company C. Find a satisfactory pairing.

1. Develop an algorithm that, given preferences for n programmers and n companies, find a satisfactory pairing. If there is more than one satisfactory pairing you need to find just one.
2. Implement your algorithm and test is on several cases of preferences. It does not matter how your algorithm takes data, but you should clearly explain this in the documentation so that I know how to test it. Also make sure to document all your test cases and results. Check that the pairings found by your program are satisfactory (write a method to do this to save yourself time).
3. Prove that your algorithm is correct (i.e. it always stops and outputs a satisfactory pairing). You don't need to go into low-level details of your program, but your prove must be precise enough to convince someone who has not seen your program before that it is indeed correct.
4. Find the efficiency of your algorithm (or at least it's upper bound). Again, justify your answer.
• Oct. 3.
• Continue working on the matching problem.
• We will be using a program that was developed and used at UND for experimenting with finite automata. To use the program:
1. Create a directory for the program.
2. Copy the file `~elenam/3501_download/langlab.jar` into that directory; unpack it with
`jar -xf langlab.jar`
3. Make a subdirectory `dfa` in the directory where you unpacked the jar file.
4. You can start the program as ` java LanguageLab`
5. The main window allows you to test if a string is in the given language. You can define new finite automata by choosing "Build DFA" in Acceptors menu. You need to define the alphabet and the rules and select the starting state and final states. You can test an automaton on a string by typing the string in the text area at the bottom of the window; use the "Start" and "step" to walk through the string..
"Store" stores automata in the program cache, "Save" stores them in the dfa directory. "Apply" loads them into the main window where you can generate the language accepted by the automaton. Don't worry about the "union" and "intersection" yet.
Using the DFA Builder, construct finite automata that accept the following languages over the alphabet 0, 1:
1. Strings with even number of zeros
2. Strings with odd number of ones
3. Strings with no more than 2 consecutive zeros.
Submit a copy of the files for your automata in the dfa directory.
• Oct. 24 Lab 6: Java Regular Expressions
Tutorial on Regular Expressions at java.sun.com is a comprehensive source of information.
Write a program to do the following tasks using regular expressions. Make sure to test thoroughly and submit all your test examples.
1. Find all occurrences of letter combinations "dfa" and "nfa" in a text.
2. Same as the previous exercise, but in any combination of upper case and lower case letters.
3. Find all numbers (i.e. sequences of digits with no other characters) in a text.
4. Find all negative numbers, i.e. numbers preceded by a - sign
5. Find all floating point numbers, both positive and negative (i.e. numbers of the form <digits>.<digits>, possibly preceded by a - sign). Careful: a negative number must be matched only once.
6. Find all words in a text that have letters t and i in the them (in either case). Words are separated by spaces characters.
8. Find all 'for' loops in a program with a condition ```variable < number```