- 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:
- Description of your algorithm and explanation of why it is
correct
- Your program code
- The result of timing the program for at least two values of n
- 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.
Read the following carefully:
- 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:
- Your program, appropriately documented.
- 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:
-
- 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.
- Sort one using the mergesort and the other one using
a quicksort.
- 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:
- Randomized QuickSort: choose the pivot at random.
- 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.
- 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.
-
Combine the middle of the three method with the optimization in the
previous task.
-
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.
Your task is to do the following:
- 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.
- 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).
- 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.
-
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:
- Create a directory for the program.
- Copy the file
~elenam/3501_download/langlab.jar into
that directory; unpack it with
jar -xf langlab.jar
- Make a subdirectory
dfa in the directory where you
unpacked the jar file.
- You can start the program as
java LanguageLab
-
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:
- Strings with even number of zeros
- Strings with odd number of ones
- 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.
- Find all occurrences of letter combinations "dfa" and "nfa" in a
text.
- Same as the previous exercise, but in any combination of upper
case and lower case letters.
- Find all numbers (i.e. sequences of digits with no other
characters) in a text.
- Find all negative numbers, i.e. numbers preceded by a - sign
- 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.
- Find all words in a text that have letters t and i in the
them (in either case). Words are separated by spaces characters.
- Find all words that start with a letter t
- Find all 'for' loops in a program with a condition
variable
< number
- Spam detector: Check if the given text starts with "Dear friend"
or "Dearest friend" (in any capitalization)
- Check whether a given text has exactly three question marks in
it
- Check whether a given text has at most three question marks in
it
- Use split
method of the Pattern class to split a string with items separated by |
- Use replaceAll
method of the Matcher class to replace all occurrences of "today" by
"yesterday".
- Replace all occurrences of the pattern mm/dd/yyyy by
"some day"
- Long problem: Postal address recognition. Write a regular
expression to check if a given text matches the US postal address
pattern. Think of what a valid postal address is. For simplicity
assume that a valid postal address has a comma between the street
address and the city name and between the city name and the
state/zip. Also assume that any 2-letter upper case combination
represents a state. Make sure that your expression accepts a
reasonable address.