Terry Flint

Greenhorn

Posts: 20

posted 4 years ago

I had my first lecture on algorithms today and the instructor had an exercise he wanted us to work on in class. I thought I'd be able to get around it, given it was first lecture after all, but I was one of the ones who couldn't complete it (not quite the only one). First off, here's the simple example he gave to get the idea into our heads:

Naturally, this produces the following table:

0 1 2 3

1 0 3 2

2 3 0 1

3 2 1 0

So far, so good. He then extracted the idea to make a more general algorithm:

He asked us to code this in java. Obviously, he wanted it to be a method which would have the parameter int n.

This n will then be used to produce a grid of n*n. I don't know if a 2D array or a 2D ArrayList is more appropriate for this.

I've now started to think an ArrayList makes more sense, because I don't even know if I can reassign an array to a different size.

I am frankly to ashamed of the abominable coding I tried to do in class to show it, and I want to start from scratch.

I don't want outright solutions, but I do want hints on how to do this. I imagine I will be needing two nested for loops to cycle through the array/ArrayList.

I notice that if the square is at [i][j], all the left cells will have the same i value and a lesser j value, and all of the above cells will have the same j value and a lesser i value (I think).

I thought I'd be able to use booleans to check for whether a cell was above or left, but the way I was doing it, that required associating a boolean with an int, which just made no sense.

Now, since facepalming and headdesking doesn't seem to work to well, I thought I'd admit that I need some help.

What should I do? By the way, links to online courses and documentation on algorithms like this would be appreciated if they are available (Beginner level stuff obviously).

*Write down a grid, say, 4£4, of the numbers 0, 1, 2,..., that has the property that each number in the grid is the smallest number not appearing above it in the same column, or to its left in the same row.*Naturally, this produces the following table:

0 1 2 3

1 0 3 2

2 3 0 1

3 2 1 0

So far, so good. He then extracted the idea to make a more general algorithm:

*Write down an n * n grid, of the numbers 0, 1, 2,,..., that has the property that each number in the grid is the smallest number not appearing above it in the same column, or to its left in the same row.*He asked us to code this in java. Obviously, he wanted it to be a method which would have the parameter int n.

This n will then be used to produce a grid of n*n. I don't know if a 2D array or a 2D ArrayList is more appropriate for this.

I've now started to think an ArrayList makes more sense, because I don't even know if I can reassign an array to a different size.

I am frankly to ashamed of the abominable coding I tried to do in class to show it, and I want to start from scratch.

I don't want outright solutions, but I do want hints on how to do this. I imagine I will be needing two nested for loops to cycle through the array/ArrayList.

I notice that if the square is at [i][j], all the left cells will have the same i value and a lesser j value, and all of the above cells will have the same j value and a lesser i value (I think).

I thought I'd be able to use booleans to check for whether a cell was above or left, but the way I was doing it, that required associating a boolean with an int, which just made no sense.

Now, since facepalming and headdesking doesn't seem to work to well, I thought I'd admit that I need some help.

What should I do? By the way, links to online courses and documentation on algorithms like this would be appreciated if they are available (Beginner level stuff obviously).

posted 4 years ago

Step 1) Turn off your computer.

Step 2) Get some paper, pencils, and one or more very large erasers.

Step 3) write down how YOU would do this.

Step 4) Revise the above steps multiple times, making them simple and simpler, until a 10yr old child can understand and follow them.

Step 5) When you are done with the above, revise it some more.

ONLY when you have completed steps 1-5 should you consider writing even one line of java code.

Step 2) Get some paper, pencils, and one or more very large erasers.

Step 3) write down how YOU would do this.

Step 4) Revise the above steps multiple times, making them simple and simpler, until a 10yr old child can understand and follow them.

Step 5) When you are done with the above, revise it some more.

ONLY when you have completed steps 1-5 should you consider writing even one line of java code.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors