CS 312 (W'07, T Th sections)

A small error in the C# source code prevents the project from building. I think any student who looks at the code should be able to figure out the simple fix, though. (just add a "();" to the end of the line where the error is).

This and other minor enhancements are available at the SVN location:
http://itsvn.byu.edu/cs312/CoreAlignment/branches/assignment/

Andrew,

Thanks for posting your tweaked version I am sure people will find that useful.

I can't replicate your () error. Could you tell me what line it is on?

Mike.

Sure. The bug is in the core-alignment-generator\Form1.cs file, line 443.

I have run across a problem in the database. Key 15 and 16 both define a layerType for Problem 1, Core 2, layer 5. 15 defines it as sandstone, while 16 defines it again as limestone. I asked Cindy and she said to post it and see what Dr. Jones and Dr. Ringger have to say about it. SO, what have ye to say about it? which shall we use?

Some students asked that I post the SQL to find out a few useful counts, so here they are. In all these, use the following syntax to execute the SQL:
int answer = (int)selectCommand.ExecuteScalar();

To find out # of problems:
SELECT MAX(problem) FROM tLayers
To find out # of cores in a problem:
SELECT MAX(core) FROM tLayers WHERE problem = x
To find out # of layers in a core:
SELECT MAX(layer) FROM tLayers WHERE problem = x AND core = y

The SVN distribution is available for download as a zip file here.

This distribution has classes, projects and some methods renamed and rewritten in some cases to (hopefully) help it make more sense. The UI has been improved as well.

Daniel,

Use the last value read in. So if you read the rows in increased key order, you'd get limestone as the layer type. Also note that there is a problem generator with the code which you can use to generate more problems for use in evaluating your improvement should you so desire.

Andrew,

Thanks as always for the improvements and code. I feel like we should be paying you. Oh wait! We already tried to hire you once and it didn't work out for us :)

Mike.

Wow, thanks Andrew... we do appreciate your work!

It has always paid off in this class to wait till D.Jones and Andrew have worked through things...

In class today, I mentioned that I would post some LCS lengths for your use in deciding if your algorithm is correct or not. Here goes...

Core 1 to core 2 in problem 1: 5 layers in commom (so LCS = 5). So connectedRight for core 1 problem 1 will contain 5 rows set to T and connectedLeft for core 2 problem 1 will contain 5 rows set to T as well.
Core 2 to core 3 in problem 1: 7 layers in commn (so LCS = 7). Similarly, connectedRight in core 2 problem 1 will contain 7 rows set to T and connectedLeft in core 3 problem 1 will contain 7 rows set to T.

here are some nifty addendum to Andrew's sql (5 posts up):
For Selecting a certian core (having already predeterminded the specific core you want.)
"SELECT * FROM tLayers WHERE core = " + myCore + " AND problem = " + myProblem + " ORDER BY layer"

Some more sql problems:

Does anyone know how to change this:

string updateCommandString = "UPDATE tLayers SET connectedLeft = FALSE"+ " , connectedRight = TRUE"
+ " WHERE problem = " + currentProblem + " AND core = -1 AND layer = -1";
(this is the line from the code)

into making it only assign connectedRight to TRUE and not do anything with connectedLeft

Matthew, just delete the part of the string that sets the connectedLeft.

string updateCommandString = "UPDATE tLayers SET connectedRight = TRUE"

+ " WHERE problem = " + currentProblem + " AND core = -1 AND layer = -1";

Big O(n^2) is not possible. Here's some nifty proof:

if you were to take two words, say "cat" and "fix", in order to determine that the longest common subsequnce is 0, you have to compare every letter in word 1 to every letter in word 2, which results in O(n*m) ~= O(n^2). Because the worst case is O(n^2), and big O is a measure of worst case, the worst case will always be O(n^2).

Barring that case, there it is definitely possible to creative a O(n) algorithm with average case O(n), elsewise it's not happenin'

DrFindley,

Big O(n^2) for which problem where n = what?

What I want is an algorithm that runs in O(n^2) for aligning two adjacent cores where each core is length n.

I think that's what you are asking about?

Mike.

I believe what drfindley is referring to is the last part of the writeup where it asks to create a new algorithm. I too had this problem in finding a O(n) algorithm, until I realized that the question is asking for O(n) space. If I understand correct, the new algorithm for the write-up must use O(n) space but can be any Big-O time (O(2^n) for example). Please correct me if I'm wrong.

mfarley5 is right on. The I meant to put O(n) running time, but I didn't look closely enough at the question to see it meant O(n) space.

mfarley5 and DrFindley,

You are correct. The algorithm needs O(n) space and whatever time bound you end up with is fine. Just make sure (1) the algorithm works and (2) you got the right time bound.

mike.

Is there anything special that should be done with the 'void' layer type? More specifically, is it possible for it to have a connectedRight or Left value = TRUE if it matches up in an adjacent core with another void layer type?

dkendall,

There's nothing special about the void layer type. It is just a void in the core sample and can match void layers on either side.

Mik.e

Thanks for signing in, . Now you can comment. (sign out)

(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)

URL:
Remember me? YesNo

Comments: