For input file in question 1... how would i be able to tell between input for infinity(no arcs) and arcs with weight 0? or do we not have any arcs with weight zero?

gche043 wrote:

For input file in question 1... how would i be able to tell between input for infinity(no arcs) and arcs with weight 0? or do we not have any arcs with weight zero?

Yes I think we can assume that....

Do you know whether we will have to handle 1x1 matrices in q1 as it would be a bit tricky distinguishing between order and the actual matrix itself

in graph 2:
0 3 4
1 0 3
4 4 0

are they the shortest paths between each node?

if so, what is the value of K?

When I copy the content of a txt file to another file, the output file is exactly same as the input file, that's fine...
But when I print the content of the original file onto the console, the output looks like this:

The content of the file is "asdf" and I found that the strange output is the ASCII code of "asdf"-_-'...

Anyone can tell me how to get the output which is same as the origin?
I'm using method to read from file.

have you tried reading your 105 notes? or try the api or other previous post

fever691 wrote:

have you tried reading your 105 notes? or try the api or other previous post

My stage I compsci courses were taken in Canterbury Uni, so...little bit different between Akl and Chch...

Any hints? Thanks...

zbao002 wrote:

My stage I compsci courses were taken in Canterbury Uni, so...little bit different between Akl and Chch...

the 101 and 105 notes are on the web, check under the courses page
or read Mark's class files, big hint there...or try the api...but yea I suggest the 105 notes :)

I am still confused about the input for Q1, does the user pass in a text file containing the weighted matrix for you to traverse through?

Or does the user enter the weight values another way?

ie. how does the user pass in his matrix into your program?

your program takes a filename as a parameter. in other words, args[0] will contain the name of the file which contains the matrices.

question:if I use Marks definition for least cost. Then the cost is always the amount I can extract from the situation no matter whether or not there is a the cost. So how do I know before I get whether or not I can afford it?I don't, so I may not get there, right.


Another way of looking: How do I know that I can always get there?
I only go if I'm willing to pay and it always cost the exact amount that I have.

Hey all,,,


Just wondering are we expected to write the floyd.java file as a standalone program that doesnt implement any of the graphs classes from the handouts dir on mrks website?

Or will it be tested in the directory where these class files reside....

For instance, has anyone tried the Static method
public static int[] [] distanceMatrix(Graph G) @line 441 in GraphsAlgs.java?

When i call it, i get an ArrayIndexOut of bounds error within this file...

This is one reason why im wondering if we are expected to implement the graphs classes ourselves, and just use Mark's ones as a kickstart...

[quote:0081f57432]
5. The comment in the assignment that you should use the graph classes provided is a standard one I give every semester. Usually you really do need them, but this time the assignment is easier and you don't really need them. But feel free to steal pieces of code that may be helpful.

Does this work for anyone? my solution to Q2 doesnt produce the desired output using the floyds algorithm I created using Q1, it produces a new matrix but one of the weights arent correct.

I thought floyds algorithm was ment to handle matries with negative arcs?

Cheers.

But the Floyd's algorithm finds the least cost from getting one node to another node. But the Dijkstra's algorithm finds the shortest path from a starting node to every other node.
but yea, read the course book, I don't think the two algorithm's are the same

Floyds Algorithm does handle weights with negative arcs, the question is should we be examining the output from floyds algorithm under the conditions imposed by Dijkstra's? (did I spell that correctly?)

I just want to make sure I heard right, but did Mark say that Dijkstra's algorithm can start at any node, and that even with negative weights Dijkstra's algorithm can still "sometimes" find the correct answer?

[I think]
When there are negative arcs, Dijkstra may or may not generate the correct answer. Our job is to find the smallest one that Dijkstra doesn't give the right answer....
[/I think]

fever691 wrote:

I just want to make sure I heard right, but did Mark say that Dijkstra's algorithm can start at any node, and that even with negative weights Dijkstra's algorithm can still "sometimes" find the correct answer?

yep u heard him right! Dijkstra's algorithm can sometimes find the correct path depending on the graph u have.

just want to know exactly wht format for part 2..
The sheet said we should use standard weighted adjacency matrix format..do we need to explain anything to the marker or just one matrix..that is it..also do we need to have our own UPI included????hurry up

the smallest example U can find means what?


does it mean there is a smallest example or U can just create, imagine or

do any digraphs we think small?

[size=18:8472471f4a] [color=red:8472471f4a]

[color=red:27e23f535a] [size=24:27e23f535a] use mike's graph files[/color:27e23f535a] [/size:27e23f535a]

knack wrote:

[color=red:7a5fb9f3e3] [size=24:7a5fb9f3e3] use mike's graph files[/color:7a5fb9f3e3] [/size:7a5fb9f3e3]

i am confused too

In Mike's graph:

BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

where does the "System.in" come from?
If I have a "a.txt" file which contains the matrix, how could I read the content of the file?

you don't "have to" use Mark's graph classes. like he said, in one of his post. You can use his graph classes or jst simply do it yourself...if you've forgotten how to use arrays, go check out the 101 notes or the 105 notes for last semester

skyblue wrote:

[size=18:43b5c846c8] [color=red:43b5c846c8]

Read the 105 note, I/O sections then I think u will get some ideas.

BTW, I didn't use the Java-Graph package to work out quesiton 1, but I think I got the right output

man...we've really did learnt nothing on the Graph writing with java in lecture, how can guys generate code so fast? repeat?

david wrote:

In Mike's graph: BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

[color=blue:51c1229a45]
I mean i want the weight adjaceny matrix,i can get the connective adjaceny matrix by using mike's GraphAdjMatrix class.

[/quote]
[color=blue:47f5adfc7c]
I mean i want the weight adjaceny matrix,i can get the connective adjaceny matrix by using mike's GraphAdjMatrix class.


So do u mean we can get the input in the form of a adjacency matrix by just using the GraphAdjMatrix class?
Do we need to get the input character by character and reconstruct it?
I'm really lost~~~
Please do help~~~
I'm still at the very very begining of Q1~~~

anyone knows whetehr we can submit more than one java files or not? or just only the floyd.java? what if I have some abstract class file work with it?

is that hyphenated or not??




does it matter if the height of tree is the size of the Graph?


that last answer wasn't that enlightning but what do you mean
it has to maintain the DFS properties even if it's not a DFS

Can anyone heilp me for the Q1



I retrieved the text file then what should i do
How the graphs in the website will be helpful to us

sireesha wrote:

Can anyone heilp me for the Q1 I retrieved the text file then what should i do How the graphs in the website will be helpful to us

You don't need the graph files in from Mark's website. You should just apply Floyd's algorithm to the text you have retrieved.

If you view it as we did it in tutorials, time is incremented in two places (for DFS):
1) When a node is put on the stack (like the pre-order)
2) When a node is removed from the stack (like the post-order)

You could also say that we do it once when we visit, and once more when we have finished with a node.

Jono.

hi all, this is a question about DFS (and BFS for that matter):

i am a little unclear on when exactly we should increment the 'time' variable.. it seems to be like whenever we visit a new node.. but not quite. If someone could enlighten me, that'd be peachy :)

up to you i guess,

Mark has a global time++ counter so every node whether being visited or done has an incremented time on the last action.
but in the book they use 2 time++ inc's, one for the visted, one for the done time.

so going from node 1 -> 2 -> 3 and backup

the book: vT=1 -> vT=2 -> vT=3______backup______dT=1 -> dT=2 -> dT=3

Mark___: T=1 -> T=2 -> T=3______backup_______T=4 -> T=5 -> T=6

OTY - if not, can you let us all know Mark?

I meant preserve not maintain sorry, sillt no luck..

well I was trying to find out how long it would take for the earth to rotate

if dijkstra used his algorithm to locate a person anywhere on the globe. Whom would we start with and whom would we ask. How much mamory would it take if every person now and in the future was recorded in the database, assuming we knew the answer, only people were used and what would happen if each of them did not know their own name, except if it was told to them by someone else at the time we arrived at that particular person.

it's a shame you're not edited by the moderator.
just because you use the name "Dijkstra" it seems to give you the right to chat about anything.

hmmmm......i had a chipmunk once, his name was Floyd, yeh, he was small and brown and ate a lot of chipmunk food. i wonder what Prim would say about Floyd eating alot of Chipmunk food. Probably, "Floyd eats alot of Chipmunk food".

see the relevance?

You see, Floyd, my Chipmunk did eat alot of Chipmunk food, but, and this is the complex part so try to keep up, Prim didn't know Floyd......HA...so how could he say that Floyd ate alot of Chipmunk food, hence find the shortest path in a weighted Chipmunk cycle.
What's a weighted Chipmunk cycle?

It's a bicycle built for Chipmunks, but thats's confusing becuase unlike the weighted cycles we are used to, this one doesn't have weights attached.

haha... funny

using dij's algo to calculate the minimum distance between humans, with the edges representing perhaps knowledge of the name the other humans "in the matrix" (!?) would require a matrix with an order of the # of ppl in the world..

pls consult your psychiatrist for further assistance with your problem.

Can any of you provide some inputs and their outputs, just to check my code works.
Would that be called cheating? I don't think so.

you're too late hun the tickets are now on their way, what a waiste.




you will not get another offer like that again!


next games not for another six months.....

What's this about?

yeah.. in a weighted digraph's matrix, any zero not on the diagonal means there is no arc there - so the weight is +inf

Digraph 3: all-pairs matrix follows
0 1
+inf 0

just wondering is the +inf part of the matrix, so then if it is does that mean any zero except for the diagonal in the "all-pairs" matrix would have to be "+inf" ?

cko011 wrote:

do u know which file is the sample output of Q1?

this is the sample output:

Digraph 1: negative weight cycle detected, aborting

Digraph 2: all-pairs matrix follows
0 3 4
1 0 3
4 4 0

Digraph 3: all-pairs matrix follows
0 1
+inf 0

you can find it in Mark's website in his "Handout" section for us

do u know which file is the sample output of Q1?

is anyone able to use the java kit in the lab or has access to the network drive??/home directory//

so anyone know what's the standard output file of Q2?
is it only one matrix from the digraph that can show Dij algo doesn't work if negative arcs are allowed?

:P

so, if I am lucky enough, then I could just guess one...
right? -_-;

haha yeah i spose, if you're that desperate

:P

ohhh,

that's why my prgram never stops running..........

heh yeah i was real tired when i posted that
anyway you're supposed to replace all the zeros with +inf, except the ones on the diagonal. of course in your program, you represent +inf as some big big number, not actually "+inf"

fever691 wrote:

david wrote:    so, if I am lucky enough, then I could just guess one... right? -_-; go to tutorials...might help...cos I jst clicked jst then too :D

I think I've already got the answer.
I'm just kidding. :P

david wrote:

so, if I am lucky enough, then I could just guess one... right? -_-;

go to tutorials...might help...cos I jst clicked jst then too :D

I just feel a little bit unfair~~
anyway, I hope this could help someone.
:)

ok.. i see.

the fisrt number 4 which means how big the matrix is,
but what the meaning of the last number 0

yeap. just a single weighted digraph's matrix - eg.
[code:1:d0b5005178] 4
0 3 4 1
-2 0 1 0
0 1 0 3
-1 0 4 0
0[/code:1:d0b5005178]

this is not the actual answer of course, i just made it up :P

no, just give the digraph which makes it not work

For Q2, do we need to explain why Dijkstra's algorithm does not work?

I think the 0 refers to the next matrix, but since its of size 0, there is none

yeah, the zero just marks the end of the file

For Q2.
in Dijkstra algorithm, second part, the while loop, for each iteration,
it's looking for a vertex(in V(G) but not S) that is minimum distance to our
v.
[code:1:bc81869b12] find u (- V(G)\S so that dist[u] is minimum [/code:1:bc81869b12]

My questionn is, what if at this stage, there are two vertices that are with
the same dist, and this dist is the minimum, which one do we pick plz?

[quote:8929afdf06]
knack
pduf006

Posted: Wed Aug 06, 2003 12:41 pm Post subject:

yeap. just a single weighted digraph's matrix - eg.
[code:1:8929afdf06]
4
0 3 4 1
-2 0 1 0
0 1 0 3
-1 0 4 0
0
[/code:1:8929afdf06]

this is not the actual answer of course, i just made it up :P

i know. but that's "standard weighted adjancy matrix" format. its pretty stupid i guess, but i dont much care anymore since i've submitted my assignment :P
i dont wanna think about this anymore

come on mate! show some commitment! you've gotta make it perfect, simply because u want to, don't you?

does it make any differrence if there are two paths with the same total weights?

when? what context?

When we are detecting negative weighted cycle, which one do we play around with, the weighted adjacency matrix or the shortest distance matrix that would've been produced by our Floyd algorithm....or something else.

at a guess....if you wait until you have the shortest distance matrix,

it's too late to detect the negative-weight cycle?

just a guess tho'
any1 else??

can you ever get a non-zero entry on the diagonal?

I dunno if this helps but remember its a negative cycle if the total weight along the cycle is less than zero...

yesss,

when you have a neg......*edited*

sorry I asked.

knack pduf006 <---
how did you detect the negative cycle please? not the answer, but some hints please?
all the folks haven done it.....please drop some hints here plz..~~

i think enough hints have been dropped in this thread already.. read a few posts up

[quote:7ead10fc26] yesss,

when you have a neg......*edited*

fez wrote:

[quote:d39d1b6aec] yesss, when you have a neg......*edited*

How does that work? I thought a diagonal value meant the node had a loop onto itself, is that what the question means (q1) when it says "your program should be able to handle digraphs with and arcs"

?

dunno if this is gonna help but try running a matrix with negative weight cycle w\o checking it... look at the result and see if you can spot anything unusual

asheltie wrote:

at a guess....if you wait until you have the shortest distance matrix, it's too late to detect the negative-weight cycle? just a guess tho' any1 else??

how to detect the negative-weight cycle,(a cycle with total negative weight)?we need check triangles for each matrix ....
plz help

Could someone please post the code to measure the time it takes for a section of code to run? I cant remember since I did 105 like 2 years ago.

Thanks

Very simple...

[code:1:0d203d8ff5] long startTime = System.currentTimeMillis();
// do some stuff, call methods, whatever
long endTime = System.currentTimeMillis() - startTime;
[/code:1:0d203d8ff5]

System.currentTimeMillis() gets the number of milliseconds since Midnight (is it midnight ? or this year ? something like that...)

did I happen to mention how pleasing it was to see Mark in such fine spirits today during the lecture after tuesday. Obviously having a better day!

I still haven't heard if anyone has the notes for the last part of the lecture,so I thought I'd just post another happy forum message for all of us to reply to me!!



thank you for that! that was reaaaally great!!

so what u mean is in the input file you will use 0 to replace all infinite distance..is it?


one more question for the output file, u said we can use +inf to represent infinite in the output file ..so can i use . do that which u said in the lecture? i think output will be more tidey if use . than +inf

For Q1 (Floyd), we need to clarify the input format (weighted adjacency matrix). It is difficult to represent infinity, so I am using 0 in the (i,j) position to mean there is no arc from node i to node j. You can also interpret it to mean that there is an arc of weight zero, BUT this is not how I want to do it. That would give incorrect answers.

Q1 wants you to output the matrix d that contains in the (i, j) position the minimum weight of a path from i to j. The only possible area of confusion now is the diagonal: what should the (i,i) position be? The answer is it should be 0 for all nodes i. This is because a path can have no arcs and only one node (the empty path has weight zero). Of course if we had a loop of negative weight at a node, Floyd's algorithm would not yield zero for d(i, i), but in this case you are supposed to detect the fact and terminate with an error message.

If you end up not having any path from i to j then you are supposed to write out "+inf" to your output.

Here is a hint for how to avoid infinity. Compute the sum M of all the positive weights in the input matrix. No path can have length more than this, so we could use M+1 instead of infinity from the beginning.

Someone please remind me of this in lecture.

[quote:317d277d6f] I know, how can we possibly move from any relative position where there is only one path with less than a cost than not moving doesn't make sense!!The cost of not implementing the move becomes infinitely large so the distance from a node to itself becomes nonsensical in terms of ... big O notation ...

i thinks Q2 which ask us to find the smallest example of digraph that show Dij algo doesnot work if negative weight arcs are allowed.

does anyone know why dijkstra only likes non-negative path weights. Mathematically it does seem reasonable to have non-negative path weights and negative path weights for a MST, however what interpretation do we apply to graph G with n nodes where n is a finite non emty set(i.e. n >0) and a set of edges E with a finite set which is possibly empty, however in the case of a minimumset of a single node and a single path with a negative number, why does Dijkstra not indulge(in negative values)what interpretation do we apply to a minimum spanning tree with a negative minimum weight? if the cost is less that zero do we get an infinite loop? or in the case of there being a substantial tree do we get subtrees(subsystems) with weak components and ambiguous meanings for string selections. I don't see the difference for acceptance states and start states with no closure(not really sure about closure when acceptance states and start states are the same??no real possibility for subsets I guess?? ) it does indeed seem ambiguous!! I know, how can we possibly move from any relative position where there is only one path with less than a cost than not moving doesn't make sense!!The cost of not implementing the move becomes infinitely large so the distance from a node to itself becomes nonsensical in terms of ... big O notation ...

well, first of all dyak001.. a few newline characters never hurt anyone :P makes your post so much easier to read

now, onto your question
i cannot really tell you the answer, because then i would be telling you the answer to that assignment question.. but i'll try to explain without specifics.
[list:b23eba6acf]
[*:b23eba6acf] it is perfectly mathematically allowable to have negative weights. dijstra's algo *sometimes* fails on a graph with negative weights because of the way it works. it is a flaw in the algo.

[*:b23eba6acf] in the assignment, you are not allowed to use loops with total negative weight. i assume this is cos they are too easy - run dijkstra's algo on a graph with one and watch it break.

[*:b23eba6acf] you have to find another example of a graph that causes dijkstra's algo to return the wrong value. an example using the smallest graph possible gets you more marks.

[*:b23eba6acf] it has nothing to do with big-O..
[/list:u:b23eba6acf]

sireesha wrote:

The question is saying that we should not have any -ve weight cycles but from node2 to node1 is -1 so,that is an -ve weight cycle,isn't it cheers

i just believe it should be a negative weighted cycle with fewest nodes/edges.

The question is saying that we should not have any -ve weight cycles
but from node2 to node1 is -1

so,that is an -ve weight cycle,isn't it

cheers

"should have no negative weighted cycle"

as far as i know :
"should have done sth" means sth you should do but u didnot.

so:

"should have no negative weighted cycle" means there should be no
negative weighted cycle(according to Dijkstra's algo),but (in your answer) there are.It just gives a digraph which doesnot comply to the algo

is it correct?

"no negative weight cycles" means the digraph should have "no negative weight cycles"..

-___-

it states that there should be no cycle(s), so whether you have a cycle in your graph or not doesn't matter, but if you decide to put in a cycle in your graph it shouldn't be negative.

go to check your assignment sheet

"should done" doesnot mean "should do"



the former one done
but latter one done

is it, Mark?

i will try to un-confusion you :)

Dijkstra's algorithm sometimes doesn't work if the digraph has -tive wieghts.

An easy example of this is if the digraph has a negative weight - that is, it is possible to take a route starting at one node, take off around the graph, come back to the node you started at, and have the total cost less than zero.

Here's an example:[code:1:ef3209e92b]
node0----- 3 ---->node1---- 2 ------>node2
<------------------ -6 -----------/[/code:1:ef3209e92b]
here you can go node0->node1->node2->node0 for total cost -1

If you run the algo on this graph, it looks at node0 first, decides that the lowest cost route from node0 to node0 is 0, and adds node0 to the 'seen' list. this means that when it gets to node2, it doesnt update node0's distance because node0 has been 'seen'.

now, because that's so easy (!), you're not allowed to use it in the assignment question. you have to find a graph which does NOT have a negative weight cycle, only negative wieghts, but still causes Dijkstra's algo to fail (give the wrong answer)

oh and the smaller the example, the more marks you get
and of course smaller means less nodes/edges

hth!

no negative weight cycles you say?

does that mean the di-graph has to have a cycle or not?

can anyone help me regarding this Q2


It states Dijkstra algorithm does not work if -ve weight arcs are allowed
so,the above statement is easy to understand but the other one which is saying Your weighted digraph should have no negative weight cycles
but this statement makes me little bit confusion

thanx

but the Question is saying we should n't have any -ve weighted cycle


cheers

yeah okay, i don't see why not..
i'll upload them when i get home - 8pm ish

knack wrote:

i *am* using mark's graph files, but he didnt provide an implementation of Floyd's algorithm to copy :P

so i guess that means that we can submit more than the three files that were stated in the assignment handout sheet then...

hmm.. good point. i suppose maybe its assumed that the markers have Mark's files.. i doubt they'd make us upload them if we hadn't changed them..

well i managed to generate some random weighted graphs - each cell has probability 50% for a 0, 50% for a random weight 0-50. so here's some benchmarks for q1 :)
[code:1:539b5baafa] matrix size time
50x50 0ms
100x100 16ms
500x500 906ms
1000x1000 6877ms[/code:1:539b5baafa]
these were performed on one of the UGL machines, the ones with cdwriters.

i've cut my times in half since i started optimising, and i've got another big optimisation in mind, i just have to make sure it won't break the algo :)

I think Questiion 1 is not going to be any different than any one else's implementation of Floyds Algo.
But there are so many ways of implementing the last one, I just wanted to know how well I was doing.
I spent 3 hours reading the provided class files, ditched them and spent 2 hours doing Question 3 on my own. If i created a slow implemtation I would like to know so I can revise/improve/go back to the provided class files. I'm just concerned that the recursion could be sped up with iterations on the large graphs.

I created a MatrixMaker class that makes......matrices

how's yours going?

Knack would you be able to provide some of those "random matrix" that you got, for us to use?

re: benchmarks
ummm question3 just requires output, do you mean question 1? and if so, how did you generate those huge weighted graphs? i've been benchmarking just by repeatedly processing the same graph

I was just wondering whether anyone's used Mark's graph class files......

nice,
if it includes the printout, and it looks like it does here's a massive time improver.

create a StringBuffer()
for every System.out.println(.....
replace it with buffer.append(....

don't forget to add ......+ "\n") at the end of your strings

finally, do just 1 of these at the end of the program

System.out.println(buffer.toString());

for me it knocked down times of 400m/s to 10 m/s

it *doesnt* include printouts :P [edit] remember Floyd's algo is O(n^3) [/edit]
but thanks for the tip :)

i *am* using mark's graph files, but he didnt provide an implementation of Floyd's algorithm to copy :P

Mark?
would you be willing to revise or accept a slight deviation on a [size=9:5ba63f09d3] small [/size:5ba63f09d3] question3 requirement.
The requirement states that the nodes and their visited status are to be output *before* a call to DFSv. This means the output never contains nodes that are grey (visited but not finished). If we output the visited status just inside the DFSv (after the colourising), we produce a clearer picture of the same requirement you want in your original question, it's a better picture for debugging at the least. just a thought.

My 2nd question is for any1,
what times are people getting for Question 3.
Some benchmark to see if we are producing productive DFS's would be nice. here's a few to start the ball rolling:

[code:1:5ba63f09d3]
matrix size 20 50 100 1000

DFS w/o output 0ms 0ms 0ms 40ms

DFS w/output 20ms 40ms 90ms 4500ms

[/code:1:5ba63f09d3] [size=18:5ba63f09d3] [/size:5ba63f09d3]

didn't he say that we could use the maximum weight in the graph + 1 to indicate infinity?

smallest value of numberofnodes+numberofedges

chsi021 wrote:

I am aware that Mark has said he would use "0" instead of "+inf" for Q1 as the input for weighted adjecency matrix. So wat about Q2?? would using "+inf" be ok? or it has to be "0" Or doesn't really matter?

I wonder about this too....if we use 0, then what if one of the arcs have cost 0 - will that be interpreted as infinity then?

Christian

this might be a dumb question, but I gotta ask :P
does "smallest example" mean a example with the least number of nodes or a example with the smallest weight? or both?

ppflare wrote:

didn't he say that we could use the maximum weight in the graph + 1 to indicate infinity?

isn't that for question 1?

I am aware that Mark has said he would use "0" instead of "+inf" for Q1 as the input for weighted adjecency matrix.

So wat about Q2?? would using "+inf" be ok? or it has to be "0"

Or doesn't really matter?

i've no idea either..
sorry

what u talking abt?
we talking abt the input format of Q2!!!

so much confusion.

he'll put 0's instead of [.] dots for floyd's bit (Q.1) which he wants us to turn into [+inf] for the output - yay

for (Q.2) i'm also confused.......

I find the lectures very confusing, it always looks like Mark's confused as well sometimes, from that i can assume we're experiencing the 'norm for an abstract subject like this

In the sample answer:
Immediately before call # 1 to DFSv:
Unvisited: 0 1 2 3 4
Visited, not done:
Done:

Immediately before call # 2 to DFSv:
Unvisited: 1 2 3 4
Visited, not done: 0
Done:
...

What does "# 1" mean?

it mean the step that u take... "before #1" would mean : wots the 1st thing that u visit...

# stands for "number"

I was just playing around with some matrices to test how long my Floyds algo took with large graphs.

I created them randomly, with 50% of the nodes having infinity to begin with.

I tried one with
10 nodes: 0.000 seconds
100 nodes: 0.062 seconds
1000 nodes: 1 minute!!

So it really slows down... but I was wondering if other people have tried this ? Is this kind of speed acceptable do you think??

i don't have my code here today, but will let you know.......they should all be similar if we're using primitives

mine was faster :)

but yeah floyd's algorithm is O(n^3) so its gonna get slow quite fast

Thanks for that...

And it makes sense really.

With 100 nodes: 0.062 seconds

With 1000 nodes, where are multiplying the size by 10, so the time will be multiplied by 10x10x10, ie 62 seconds, or 1 minute

I wonder how big the input files that the markers will use are (???)

finally, some times

including the file reading,

1000_matrix takes 62,000 ms
which seems the norm,

w/o the file reading the 100_matrix is 90-100m/s which seems okay'ish cause there's no tricks here

well I think that -ve means that the intrinsic nature of Dijkstra doesn't allow unfinity to be included. If the possibility of the start states is infinite we could end up anywhere(infinite regression would take place), something which a computer might not find at all appealing, since each state can only be represented by 0's and 1's, this would severely restrict computational capacity for even the simplist of problems. By only allowing positive weights for a non-deterministic or deterministic finite automata we simplify the real world problems and decision making in computational mathematics. (32, 64 or 128 bit capacities).

cheers raag

Is -ve arc an arc that goes in the opposite direction to a directed arc with a positive weight? eg lets say that weight from node(0)-------->node(1) is 2. Would the -ve arc be from node1 back to node0 with the weight of -2??? thanx

no (i think this is what you mean):

node0 ------- -10 -------> node1

is NOT the same as

node0 <------- 10 --------- node1

a negative weighted arc is just an arc that it costs a negative amount to travel along.. say you have:

node0 -------- 4 --------> node1 ------- -2 -------->node2

then the cost to get to node2 from node0 is 2
you still can't get back from node2

come on, quit it. it stopped being funny last semester. seriously.

[quote:0f0801a548] dyak001
well I think that -ve means that the intrinsic nature of Dijkstra doesn't allow unfinity to be included. If the possibility of the start states is infinite we could end up anywhere(infinite regression would take place), something which a computer might not find at all appealing, since each state can only be represented by 0's and 1's, this would severely restrict computational capacity for even the simplist of problems. By only allowing positive weights for a non-deterministic or deterministic finite automata we simplify the real world problems and decision making in computational mathematics. (32, 64 or 128 bit capacities).

he's just trying to confuse you - ignore it :P

For Q2.
in Dijkstra algorithm, second part, the while loop, for each iteration,
it's looking for a vertex(in V(G) but not S) that is minimum distance to our
v.
[code:1:fdc5c90562]
find u (- V(G)\S so that dist[u] is minimum
[/code:1:fdc5c90562]

My questionn is, what if at this stage, there are two vertices that are with
the same dist, and this dist is the minimum, which one do we pick plz? or it rather depends on the implementation....

the lowest numbered one

does anyone have notes for the last part of tuesdays lecture, I wasn't quite able to here what Mark was saying, but I was quite inspired by his tearful approach to lecturing, well I do hoope it was his passion and not some personal issues he's having that would be quite disturbing and defiantely inappropriate!!

thanks red

well it depends on when the while loop terminates i guess

i think we will be studying this stuff later in the course - i saw some things like that in the coursebook.

I'm not too sure about how to check for a "cycle of negative total weight"
anyone able to give a hint?

and a negative weighted loop would be considered a cycle?

yep, its a negative cycle if the total weight along the cycle is less than zero

well.. i don't know whether i can answer your first question :\
hm.. just try to think about how a negative weighted cycle would show up during floyd's algorithm - in the "all-pairs matrix".

yes, i think a negative weighted loop would be a cycle

yay!!! after a "long long" time I jst worked out my first question...yea I feel stupid now, cos it's easy! :P

what if you have a matrix the is:
0 8 -5
3 0 0
0 -2 0
would this still be considered a "negative weighted" cycle?
because there is a cycle from

node 0 -----> node 2 -----> node 1 -----> node 0

but the cycle doesn't have "full" negative weights on each arc

knack wrote:

well.. i don't know whether i can answer your first question :\

heheh had to try :D

but a question if
for loop
for loop
for loop
means O(n^3)
then what happens if
while loop
for loop
for loop
for loop

? or say within a while loop call another method, where that method contains other for loops like the O(n^3) ??

The sum of three arcs is -ve. therefore its going to b ive cycle
eg
-10+2+3= -5

I think the confusion is between weighted and unweighted graphs.

In the adjacency matrix representation of an unweighted graph, we use a 0 for no arc, and 1 for an arc.

With a weighted graph, things are different. Now we need to store the weighting for each arc in the matrix (and 0 weight arcs are allowed). This means we need a new value for "no arc", for which we decided to use infinity.

Other possible points of confusion: I think originally Mark intended 0 to still be "no arc" (hence the large number of 0's in his original examples of weighted graphs). But since he decided to allow 0 weighted arcs, we have moved to inf for the "no arc" value re: [url] http://forums.cs.auckland.ac.nz:8181/viewtopic.php?t=5468[/url]

Jono.

As I said in lecture Tuesday, for Q1 we will use 0 to mean infinity (no arc) in the off-diagonal positions. In your program you will need to replace these 0's with "infinity". To do this, it is probably best to compute M = sum of all positive arc weights, and use M+1 for infinity.


In the diagonal positions, 0 means either no arc or a loop of weight zero, which amounts to the same thing when computing distances.

hey, how the hell can u have a -ve weight btwn 2 nodes?? isnt the smallest weight 0, wen there are no arcs connecting them?? TUTORS/LECTURES HELP US!!!!!!! :) :) :)

weight 0 means it costs nothing to get from A to B
weight +infinity means you cannot get from A to B

you *can* theoretically have negative weights.. think of it as moving downhill - you gain gravitational potential energy :)

wow,

alot of people mispelled Ditjskra's name:

Mark,
what's [quote:9b8d74704d] "Breath First",

[quote:7afbc44c75] alot of people mispelled Ditjskra's name:

fshe010 wrote:

^-^ ok.. so could you tell me why the example of Q3 from lecture finished the DFS research when still got node 4 unvisit

I didn't visit all the nodes too

we can't visit all nodes if we start from 0 node, so...

no, i think that would be cheating.

could u tell me how many call # number of q3

..no i can't..

i must have missed that. are you sure he left it unvisited? it wasnt a tree all by itself? mr lecturer? mr tutor?

so then when you can't go any further, start again from the next unprocessed node.. just like the algo in the book

^-^ ok..
so could you tell me why the example of Q3 from lecture finished the DFS research when still got node 4 unvisit

what's meaning of the first requirment of Q3 which is In every for loop , process nodes in increasing order of numerical label.

er.. how simple do you want it? first process node #1, then node #2, then node #3 etc etc etc :P

...
Immediately before call # 5 to DFSv:
Unvisited: 4
Visited, not done: 0 1 3
Done: 2

why mike ends the DFS research without visiting node 4?
Or he just didnot finish it.

i think the point is he said "Immediately before.." so everything listed after this line is the information right before doing the DFSv, then when the last node is finished there'll be no more DFSv to do, therefore the very last node is not listed.

Umm.. you can discuss how the algorithms work and how to use them, but please be careful to leave it at that. You should not discuss anything specific to the assignment (eg. which nodes you traversed in which order etc).

Cheers,
Jono.

knack wrote:

it means 1 then 2 then 3 then 4 etc numeric == numbers :)

do we need follow the number order 1,2,3,4,5 respectivity?or 5,1,2,3if 5 is root.

why?

i *think* we have to start at node 0

hey, in the "rules" for q3 it says that we have to go thru nodes in ascending order. does that mean we have to start with node 0? or can we choose any root, then go as far as we can and then go in ascending order???? (cuz if u start at node 0 there is more than 1 connected tree), thanx

well yeah, but where does it say you have to get one connected tree?

thanx,

for the answer,

at least thanks for telling us what to look for........

nope i think u need to start at root 6

coz there is no routes that go into 6

msir003 wrote:

hey, in the "rules" for q3 it says that we have to go thru nodes in ascending order. does that mean we have to start with node 0? or can we choose any root, then go as far as we can and then go in ascending order???? (cuz if u start at node 0 there is more than 1 connected tree), thanx

what is the meaning of numerial order?

it means 1 then 2 then 3 then 4 etc
numeric == numbers :)

crap I did it out of numerical order and jumped from 1 to 3

I think you need to start at 0 and 6 :)

start at 0, then if you run out of nodes to process and there are sill some left, start again at the lowest numbered unprocessed node

[quote:33472e640e]
Mark:
For Q1 (Floyd), we need to clarify the input format (weighted adjacency matrix). It is difficult to represent infinity, so I am using 0 in the (i,j) position to mean there is no arc from node i to node j. You can also interpret it to mean that there is an arc of weight zero, BUT this is not how I want to do it. That would give incorrect answers.
...
...
If you end up not having any path from i to j then you are supposed to write out "+inf" to your output.

Here is a hint for how to avoid infinity. Compute the sum M of all the positive weights in the input matrix. No path can have length more than this, so we could use M+1 instead of infinity from the beginning.

i think we assume that the only arcs of zero weight will be on the diagonal. all the other zeros represent infinity.

In Q1, does our program only need to handle one weight adjacency matrix in the input file? Or we need to handle many matrices at one time?

Our program should be able to take multiple weighted adjacency matrices in the input file. We can tell that from the input and output example in mark's handout directory.

knack wrote:

i think we assume that the only arcs of zero weight will be on the diagonal. all the other zeros represent infinity.

So u add all numbers in the matrix and add1 then u replace the sum with every 0 except ones at the diagonal

YES

run through Floyd's algorithm and it would work

shurik wrote:

run through Floyd's algorithm and it would work

hi,guys,how to write the java program?fro Q1,anyone can give me a hint

To get you started you need to get the matrix out of the txt file, Marks handouts dir has some java files that can help you there (not that I used them or anything)

fez wrote:

To get you started you need to get the matrix out of the txt file, Marks handouts dir has some java files that can help you there (not that I used them or anything)

on the website?

jimmy wrote:

fez wrote:    To get you started you need to get the matrix out of the txt file, Marks handouts dir has some java files that can help you there (not that I used them or anything) on the website?

yea at his website "my handouts"

shurik wrote:

jimmy wrote:    fez wrote:    To get you started you need to get the matrix out of the txt file, Marks handouts dir has some java files that can help you there (not that I used them or anything) on the website? yea at his website "my handouts"

there are a lot of sources.even i don't know which will be useful ?
anyway i have found it,thanks a lot!

jimmy wrote:

shurik wrote:    jimmy wrote:    fez wrote:    To get you started you need to get the matrix out of the txt file, Marks handouts dir has some java files that can help you there (not that I used them or anything) on the website? yea at his website "my handouts" there are a lot of sources.even i don't know which will be useful ? anyway i have found it,thanks a lot!

I didn't use the package of java-graph Mark provided, but I still got the correct output.

I finished the code, but I still get no idea what's going on in Q2.........:(

Bigbear wrote:

jimmy wrote:    shurik wrote:    jimmy wrote:    fez wrote:    To get you started you need to get the matrix out of the txt file, Marks handouts dir has some java files that can help you there (not that I used them or anything) on the website? yea at his website "my handouts" there are a lot of sources.even i don't know which will be useful ? anyway i have found it,thanks a lot! I didn't use the package of java-graph Mark provided, but I still got the correct output. I finished the code, but I still get no idea what's going on in Q2.........:(

how to do that?give me some hints?

[quote:96a3482b60] I didn't use the package of java-graph Mark provided, but I still got the correct output.

I finished the code, but I still get no idea what's going on in Q2.........:(

just means it has to be right. I hope the tutor that gave me those answers wasn't lying.

Yes, n = nodes and e = edges. You are looking for the smallest graph (in terms of both nodes and edges) for which Dijkstra's gives an incorrect answer. This graph may or may not have a cycle.

Jono.

can I have arcs that are 0 weight for Q2?
For Q1, we can't. That's for sure. Because, in standard weighted matrix, all off diagonal 0s are interpreted as +inf (arc doesn't exist)

Anyone knows why Dijkstra's algorithm doesn't work if negative weight arcs are allowed, please?

How can an arc be negative weight(cost) please?

i don't think i can tell you that.. it's sorta the assignment question :P

um.. just try and think about how it works and try running it on a few graphs with -tive weights, see if you can break it :)

btw - the assignment says "no negative cycles" - so you arent allowed to be able to go from A to A with less than zero cost - cos that's a really easy way of breaking Dijkstra :)

I hope the following answers all the common questions:

1. Even though in Q1 using, say, . instead of +inf would be tidier, please stick to the instructions given for formatting.

2. The input file you are given
for Q1 will contain several digraphs in
the standard weighted adjacency
matrix format.

3. For Q1, please send your output to standard output (System.out.print), not to a file - it makes marking much easier. We will redirect to a file when we mark it.

4. Some of the standard format files and sample answers on my website were a bit corrupted - you may want to check them again now they have been fixed.

5. The comment in the assignment that you should use the graph classes provided is a standard one I give every semester. Usually you really do need them, but this time the assignment is easier and you don't really need them. But feel free to steal pieces of code that may be helpful.

6. I really do want just 1 file floyd.java for Q1. You may assume that all the Java graph files on my website are available to the markers in the same directory that your floyd.java will be.

7. Someone asked me why the adb was not working - it has been working since Monday, so try again. The standard deadline time is 9pm as listed on the course website. I think I have told someone it was midnight, sorry.

Greedy Algorithms and Negative Costs
A greedy algorithm chooses the locally best option at each step, in hopes that this will produce a global optimum.
For Dijkstra's algorithm this is more than a hope: it guarantees shortest paths, provided all costs are non-negative. In this case one cannot get any cheaper by going further. It is a label setting method because once a cost (label) is determined, it need not be changed.

However this guarantee fails when there are negative costs. In this case, one can get cheaper by going further if one finds a negative link. Label correcting methods are needed, which might modify the cost to a node when a better cost is found. An example label correcting algorithm is given in the next section.

Note that negative cycles cannot be allowed: one could get an arbitrarily "short" path by looping repeatedly around the cycle

sometimes i found it is hard to follow the massive "proof"
but i tried to make it clear...



i guess the problem is:
if there is a negative arc in a cycle a-b-c-a so that the total cost of the cycle is negative, you will find the more times u walk around the cycle , u end up with less cost from a to c by keep looping

i.e u cannot find a *lowest* cost to walk from a to c.

is it the point?

o hi I've never done this before so I hope everyone understands what my question is, umm well for the assignment questions we have to use Dijkstras and Floyds algorithm to assess the minimum weight path for some grapg G. Oh I hope I spelled Dijkstra and Floyd correctly, anyway some graph G with n nodes and e edges, now for one of them I'm not supposed to use negative arc weights(so I won't...ha) for Dijkstras algorithm(i think), now for Floyds algorithm it doesn't matter(so I will ... ha) if we use negative weights even for a minimum graph with n nodes, where n is not an empty set and e edges where e can be an empty set for the minimum node vertice(s) problem where we get a total path sum less than zero, for some reason which I'm not aware of at the moment but Dijkstra does not like this(very Freudian i think) and Floyds not so fussed either way.

Now to my question does anyone knoe where I can find a copy of Dijstras and Floyds masterpieces :-).

I know one of them we starts with a increasing or decreasing weight list and selectively chose minimum weights at random(from anywhere....(Dijskra I think)), has a big O(n ...cubed...) time complexity,(greedy little sucker)..and we progressively work through the list until we have a minimum spanning tree... I think the difference with Floyds is that the selections are in an ordered arrangement, with any node as a start position, preferably a minimum weight node edge.(n..cubed aswell I think ...another greedy little sucker)

oh I do hope you can understand my difficulty and can help me out..that would be so great...thankssss


:-) cheers steve

if you buy the 220 notes you'll find them there

btw,
you spelt Dijkstra wrong on line 12 (or 11 if you don't count an empty line as a line?)

they're both in the coursebook, read ahead a little..

floyd doesnt mind a few negative weights, but screws up on a negative *cycle*

dijkstra can't handle negative weights at all (in some situations)
the question there is to find the smallest example of such a case

if you see file from marks handout page.
There is 0 at the end of list.
Should my programe recognise that as a end of file?
or should I print
ie)
....
....
Digraph 3: all-pairs matrix follows
0 1 3
1 0 1
3 0 3

Digraph 4: all-pairs matrix follows

C:\Assignment>_

like this? with 0*0 matrix drawn?
or dont print diagraph 4?
tell me~!~!~!
i need to submit!

the 0 is just an end of file marker, not a 0x0 matrix.

Is it impossible to submit my assignmnet without NetAccount?
Because I could not get excess into ftp site to download NetAccount.

inkeol83 wrote:

Is it impossible to submit my assignmnet without NetAccount? Because I could not get excess into ftp site to download NetAccount.

off course,u need connect to netcount to submit assignment

i am wondering....
as we are taking adjacency matrix format file as an argument..
but in the graph class file, it uses adjcency list as argument right??

as in the graph file..
[code:1:864ccee3c0]
//public class Graph extends GraphAdjMatrix
public class Graph extends GraphAdjLists
[/code:1:864ccee3c0]

so how should i store adjcency matrix??
i am confused and have no idea at all...
can anybody help???
thanks...

make the Graph class an extension of the GraphAdjMatrix class(i.e. comment out the bottom one and delete the comments from in front of the top one)

jwel027 wrote:

make the Graph class an extension of the GraphAdjMatrix class(i.e. comment out the bottom one and delete the comments from in front of the top one)

so we are allowed to modify the files provided?

ysakaed wrote:

so we are allowed to modify the files provided?

Lets leave it at that: u dont even really need the files provided, unless u want to make yr life really misrable

is a strong component a strong component if it's a forward arc or a back arc, surely a forward arc or back arc cannot ever be a strong component since all sub components are not reachable from all nodes in the system, so if we have a single pair of nodes with a single path connecting them and the pairing is a strong component( undirected ), can it ever be a forward arc or a back arc, or can it be both a forward arc and a back arc in which case does that make it two weak components. In this case with two weak components is it a mathematical representation of the sub components contained within the pairing. So if one of the components is not present at all times that would then make it( the pairing ) a weak component, surely?

one day, you're gonna have an actual legit question and noone will bother reading it.

Forward arc, back arc; both part of a component.
Strong if all reachable, weak if not.
Simplify man. Simplify yah Yak.

how to run Mark's program(those java files on the web)? the GraphDemo.java can't be compiled. are we supposed to write a program called Floy.java as a part of Mark's program or the Floy.java file is the whole program which can deal Q1? I don't know what Mark's program does and how I start Q1? I don't know what we are supposed to do? I am confused. Could someone make me clear.

could someone explain to me why this code works, It seems to run to previuosly compiled version. Since then it has been recompiled and run but produces the same output?

the parameters which were switched off were the PostOrd[l] ) variable, but somehow still produces output that the array is being assigned some values, although the assignment variable in the DFS method has been commented out and so should produce all zero's as the out put, however the output is the reverse of the array PreOrd[l] which is assigned the integer values at the begginning of the DFS method just prior to the call to DFS. Some of the comments have been deleted, however the code remains the same as that run on the computers in the lab at 2:50pm on the JCreator development environment.

<EDITED>

I realise you were trying to determine whether there was a bug in your setup of JCreator, but the code posted was getting a bit borderline. Ideally sections of working code should never be posted to the forum, and in this case people may have tried to use it for answering an assignment question.

Best to ask demonstrators for help with those sorts of problems.

Can either Mark, or someone else please provide a weighted adjacency matrix file, with its corresponding output, so that we can test part 1 of the asst? I don't see how that can be considered cheating

thanks

hello everyone

who tell me how many notes can make a cycle ?

if a note has a loop and the weight is negetive, i don't whether it is a cycly of negetive weight??

thanks

fangwen27 wrote:

hello everyone who tell me how many notes can make a cycle ? if a note has a loop and the weight is negetive, i don't whether it is a cycly of negetive weight?? thanks

3....more

who can tell me
negtive weight loop is a negtive weight cycle or not??

if it is . please tell me why?

i remember a cycle should has 3 or more note. right?

no.. it's different.
loop is from itself and finish on itself without visiting other nodes.

Cycle is a loop, it could only have 2 or 1 notes. The weight of the loop or cycle is the sum of the arcs in the loop(Cycle). i`m not gonna explan why, coz the book says the definition.!!

Can anyone tell me the difference between node u and node v?
this is insid the DFSv algorithm. I am confused when ilook at the algo to do my question 3. Wat do u mean by "v adjacent to u". Cheers!!

in the DFS you're looking @ each node in turn, the current node you are looking @ is labelled "V".
"U" is any node that has an edge from "V" to "U".

So if the matrix is:

0 2 0
1 0 4
0 3 0

and "V" is node 2
the node/s that "U" represents will be the one with the edge "3

Hi,
I'm having some problems with Floyd's algorithm when I have negative arc weigths.
Can someone please confirm that instead of using <infinity> for non-existent arcs, we are to use the 1+sum of all POSITIVE weights?
Or should we be using 1+the sum of ALL arcs (both positive and negative weights)?
If you've had this problem, can you please give me some hints about where I might be going wrong?
For example, with the following weighted adjacency matrix (where infinity would be replaced by sum of positive weights which is 21)

0 3 6 7
(21) 0 4 3
(21) 2 0 6
(21) -4 -1 0

we should get
0 3 6 7
(21) 0 4 3
(21) 2 0 6
(21) -4 -1 0

except I get
17 -4 -1 0
for the last row because at some point it compares [3,0] to [3,1] +[1,0] which is 21 > -4+21 which is 17.
Any suggestions?
Thanks

I have the same question as well. So I think the "infinity" value should be the sum of all positive numbers. There is no need to sum up all the absolute values of numbers even they are negative.
Anyone can clarify that?

sum of the positive arcs + 1 will do.
THe idea behaind this is, use a unique real number to represent +inf(no arc), as long as this number is not to be repeated by any other entries in ur matrix. therefore this number is easily identified. we can substitute this number back and forth when we compute it and print it out.
sum of all the negative arcs - 1 is also another option I guess... think about that///

Blah wrote:

I have the same question as well. So I think the "infinity" value should be the sum of all positive numbers. There is no need to sum up all the absolute values of numbers even they are negative. Anyone can clarify that?

Yes you don't need to sum anything besides the positive weighted arcs because the idea is to generate a value greater than the sum of the positive arcs to symbolize infinity.

Christian

Hi,
Can someone please confirm that for the negative arc weights, we replace all the non-diagonal zero values with max+1 BEFORE we perform any steps of Floyd's algorithm? And that these values will remain the same throughout until we replace them with +inf at the end?
And can anyone tell me if they get the same answer when running these two matrices through their algorithm?

matrix 1:
0 3 inf 7
inf 0 4 inf
inf inf 0 6
inf -4 -1 0

matrix 2:
0 3 21 7
21 0 4 21
21 21 0 6
21 -4 -1 0

Thanks

Okay, I'm going to answer my own question for anyone who might be having the same problem (thanks Jono for your insight!):
The problem was occurring because I was doing the comparison for minimum against max(inf) when one of the sum elements is also max(inf) so that when the other sum element is a negative value, it will decrease the max value. So its easily fixed by only doing the comparison if neither of the sum elements is equal to max.
Of course, now that I know that, it makes sense when you look at the graph...

[color=red:5cbda10081]

sure

just in case Mark doesn't receive or read my email in time for assignment 1, could you ask him when they might change the files that have been compiled for the original ones that are compiled when I press the compile button. it seems as though when I have no code at all listed in the class module it still compiles according to the code that was there some days ago, gees I forget when, although I think I can safely assume that somehow the computer and it's designers(software) have not informed me that the only software at this present time which seems to run on grenwich mean time is number.. well I forget where I was sitting the other day, or earlier today but noone else seems to be having difficulties with their java development environemt...those pesky faults why do so many developers use beta copies to use on us students, If the number of faults found in the assignment is reflective of the quality programs they release then regression analysis and cost function analysis might indicate that the withdrawal of the product from the market for redevelopment and replacement at such a late date might be astronomical. It must be a document driven process which usually requires such a high quality of programmers and developers involved inthe design of the product , since such bad quality programs and such a horrific number of faults at such a late date would indeed indicate under regression analysis that the cost curve would be exponential.

What are you on???!!

any system of rules is deterministic as it determines where, how and when resources are to be managed and resources ditributed within the context of that particular system. A deterministic and containing only one start state and a non-deterministic system more than one start state, so a non-deterministic system introduces uncertainty regarding start states and outcomes, however each subsystem is necessarily deterministic......and therefore must be a finite and descrete set of components.

For Question 3, are we supposed to run DFS on every node or run the DFSv from node 0 is enough?

read the asssignment,
sumwhere it mentions the order of reading the nodes, from that you'll find which node to start with

Lol look at the timestamps of the posts....

asheltie is so "on to it" that he posted a reply before the question was asked :P

A++

damn it you're right.........

i had this vision and ...............ooohh, it's gone.

2 moro i predict sum1 will ask a question about..................graphs!

hey when you get an answer can you let me know aswell, I'd reaaly be interested in finishing my dfs asap.

how does it go again... no names, no mike
know who!!, know how??
know who!!, not what!!

hello :

who can tell if i want my program can take a file, can i run
"java floyd<test.txt" command in DOS model?

your program should take a filename as a parameter - it should understand "java Floyd file1.txt"

i am getting panic attacks. could someone help me out plz?
I am trying to pass a file name to the main method. i tried moving the source file to c:\ then compile and run it using "javac filename.java", "java filename argument" in Dos-command line emvironment did not work --> "bad command".
then used
in = new BufferedReader(new FileReader(args[0] ));
even
in = new BufferedReader(new FileReader("C:\testmatrix.txt"));

with the second one, jcreator generated ioexception file not found
with the first one after went
configuration -> option -> sdk tool->run application
-> parameter ->prompt for main method -> browse for file -> apply
i got array index out of bound exception, what else has i got to do?

i'm a little confused,

[quote:ba24c507cd] I am trying to pass a file name to the main method. i tried moving the source file to c:\ then compile and run it using "javac filename.java", "java filename argument"

i guess panic state is not helping, you are right i should have made it clearer. what i meant to say was:

I am trying to pass a file name to the main method. i tried moving the source file and the text file that contains the matrix to c:\ then compile and run it using "javac floyd.java", "java floyd matrix.txt"

any help is very much appreciated.

the problem may be that you wrote
[quote:010a241905]
in = new BufferedReader(new FileReader("C:\testmatrix.txt"));

both matrix.txt and testmatrix.txt are text files that contain matrices, they are all placed in the same folder, they have the same purpose: to be taken by the main method as an argument. and i use only one of the files everytime i try to compile or run. because of the same format and purpose they should only give different weighted adjacency matrices after i ran the floyd.java , at this point. What i concern is that somehow the files can not even be located, or not passed through to the main method. Any idea?

i'm on the verge of tearing my hair out.

i finally understand why i can't use the command "javac floyd.java", "java floyd matrix.txt" at C:\ in Dos-command line.
it's something to do with location of the java bin and compiler and all.
short cut to solve this at the time is to move floyd.java, floyd.class and matrix.txt into folder: jdk.whatever\bin
and do everything in this folder, the ultimate solution is reseting the whole compiler - text editor - class path... somehow. damn i could use a gun shooting lesson.
asheltie thank heaps for trying really.

i couldn't see that one coming. so the message was for the compiler path not found.......of course, now

You can use the Control Panel/System/Advanced tab
under System variables just add the path into the line that says PATH

good luck.

if it's too hard to do right now, just type the full path of the java compiler and leave your floyd file wherever you like,
e.g
D:\jdk1.4.2\bin\javac.exe floyd.java
D:\jdk1.4.2\bin\java floyd matrix.txt

just don't close the black skin or you'll have to retype the long pathnames everytime you want to compile or run.

hello everyone?

i meet a problem !
i don't know how to take a file as a parameter beacause i haven't studied compsic105.

i only know run "java floyd< filename.txt" ,but someone tell me i should run "java floyd filename.txt" . i should not use "<".
now i have not any idea .

please give me help.

thanks!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

fangwen27 wrote:

hello everyone? i meet a problem ! i don't know how to take a file as a parameter beacause i haven't studied compsic105. i only know run "java floyd< filename.txt" ,but someone tell me i should run "java floyd filename.txt" . i should not use "<". now i have not any idea . please give me help. thanks!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

use:

public static void main(String argv[] ){
...

BufferedReader input = new BufferedReader(new FileReader(argv[0] ));
...
}
then java floyd input.txt should work- its what i used neway.

Hope that helps:)

mochagerl wrote:

fangwen27 wrote:    hello everyone? i meet a problem ! i don't know how to take a file as a parameter beacause i haven't studied compsic105. i only know run "java floyd< filename.txt" ,but someone tell me i should run "java floyd filename.txt" . i should not use "<". now i have not any idea . please give me help. thanks!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! use: public static void main(String argv[] ){ ... BufferedReader input = new BufferedReader(new FileReader(argv[0] )); ... } then java floyd input.txt should work- its what i used neway. Hope that helps:)

Part of my codes are:



and it works OK.What is the difference between ?I didn't take stage I compsci paper in AKL Uni as well...

Thanks

thanks !!!!!!!!!!!!!!!!!!!!!!!


i write some code , but when i compile them , always there are some errors , i don't know why?
[/code]

[quote:b27204e28b] and it works OK.What is the difference between String argv[] and String[] args?I didn't take stage I compsci paper in AKL Uni as well...

Thanks a lot to the person upstairs!

I am using the following codes to handle multi matrices:

... ...
while (token.hasMoreTokens()) {
.....
try{
...
}
catch{...}
}

But it does NOT work at all. My programme print out only the first matrix in the file.
Anyone give me a hint plz? Or tell me how you guys implement this...
Thanks!

hi, me again..
I was wondering if anyone knows a really good lawyer, who deals with possible harrassment, information privacy and human rights cases...




Yey team and a really big hi and thanks to all you guys...you've been such a great help...


p.s. no I don't like oysters...

it's just a chatbot.. don't get worked up by it!!

a couple of years ago i played a trick on a number of my friends on icq - installing a chatbot under an anonymous account, saying "hello" to them to start a conversation & sitting back to watch the inevitable battle-of-the-(t)wits that would ensue.

found it real funny how some people would start arguing with and ridiculing the bot, and remember laughing outloud when one guy i know starting calling it "stupid" - he was the one sitting there getting worked up by an algorithm!!

the most interesting log i gained from the experience was one night - went to bed straight after starting the bot on a conversation with a female friend of mine.. wake up in the morning to find that she'd spent over an hour talking to it & had even ended up propositioning it with cybersex!!! goodness gracious... the singularity may be closer than we think!!@#

if anyone wants a copy of the log i'll send it to them, obviously with names & ip's changed to protect the innocent...

could u plz send me? i want to see how clever bots can be

unless you can convince us that the uni allows anything to join the forum, which i doubt..........and that you've been given priv's to have 2 usernames......?? unlikely, you're just trying to escape from the schitzo world you've been living. So to help with your "self-recovery" i'll accept your poor attempt to rid yourself of this personality and let's hear no more.

it made no sense at all with it's poor logic so it could be reasonable to assume it's dumb. I guess it's creator should take that label also

and me too, please?

claw026. thanx:)

is that refering to your frame of reference or something else?

me too thanx

gche043

hi. can u send it to me as well?

does anyone know what the definition for a path and logic is.

i think logic might involve abstract paths of least uncertainty defining a model which uses both rule based systems of meaning, such as the general language used in outlining attributes and characteristics that are identified within possibly an open system( description ), such as the movement of an object in space in such a way as the language used to precisely outline the general characteristics of the system( structure ) in question in a scientific manner.( analysis ) such that the general characteristics, variables and attributes of the system provide the path( means ) of least uncertainty in identifying a that system. gee wiz uh huh...sounds like ummm one of those essay thingys, papers that those guru guys write umm gee wiz.....................hey...............................

gee let me get this straight, if we talk about a paricular way we just describing the system using general language.o.k. that's fairly basic, got that bit.

.a couple of questions then about logic and reasoning for dijkstra and floyd..

.how do we identify the difference between case base reasoning and structural aspects of logic within various modes or processes?

o.k. we've got open systems which are dynamic and have dynamic states, some non-deterministic systems...o.k. so far so good

.and we've got closed systems which have static states, where processes dictate sequential step by step operations which are triggered while the process is in operation..such as recursion..and deterministic systems and some non-deterministic systems...

.some non-deterministic systems models attempt to simplify complex real world systems which otherwise might not be able to be understood using any other methodologies and/or techniques....syetms such as those used in mathematics, physics or biology....( fuzzy systems etc )

some non-deterministic and deterministic processes for identification and analysis such as those used in computer science, language implementation, all use case base reasoning tools for the processes..??not qite sure but does that sound about right?

.

I've been deleting posts that are blatantly off topic (although it is best to err on the side of caution, rather than delete a possibly valid question). If you don't like anything else posted, just be patient. Topics that are irrelevant will not be replied to and thus will sink to the bottom of the forum.
Survival of the fittest.

Jono.

please kill dyak001 so that the forum doesn't completely fill up with sh^h^hrubbish

Hi
I found a disk belonging to Manasa Ramakrishna in the stage 2/3 labs over the weekend. If you're Manasa then please let me know what you want done with it.
You can email me at sdan017@ec.auckland.ac.nz
Thanx
-SAM-

could someone tell me why a regular expression from a dfa which accepts a string 10 and the nfa with the regular expression which accepts the string 10(10)* as in the example in the lecture on friday is an nfa. O.K. it has kleene closure by adding the cycle as a part of the regular expression, but when you convert the dfa to nfa form you get the same machine without the closure. There is only one start state in both and although there closure of the language L, allows a subset of strings 2Q with the nfa and the dfa doesn't, what actually makes it an nfa and not a dfa. Is it just the 2Q regular expression with kleene closure. What if we have machine with more than one start state but no Kleene closure. ALike one that accepts the regular extression 10 ||( e + (10) )...where e is the empty expression and the lhs != rhs. i.e. accept states for the strings are different.

well if you go to tutorials we covered the empty string, it only works if the start state IS also an accepting state.
and if you went to the lectures we saw a ....||..... language being converted from NFA to DFA.
[quote:2d9d503784]
What if we have machine with more than one start state but no Kleene closure. ALike one that accepts the regular extression 10 ||( e + (10) )...where e is the empty expression and the lhs != rhs. i.e. accept states for the strings are different.

I don't have a copy of the exercises in the course book for q2 & q3 and was wondering if someone could post a copy?

cheers

1 e
what does he mean there is no dfa that accepts the language L={0^n 1^2n | n>=0}, what about if we have something similar to his answer on friday with the b^3n then we get L={ 0^n 1^2n | n >=0 }, contains the subset of the dfa... 0*1*


phew!!
1 f
what does he mean only a prime number of 0's

what doea that mean??if we only have some characters like a,b,c for our alphabet then where is the integers in the language L={}. Can we have like 2K a's as a part of the language and 0k c's aswell? or does it have to exactly match the 3k b's....?so does that mean we can only have the language that exactly matches L={a*(3(nb))*)c* | n >=0} || L={a*(nb)*c* | n/3 is a whole number W >=0 } is that the form that the form we should express it in when outlining the logic? I think I'm still not quite sure when a dfa is a dfa and not an nfa or does it matter??is an nfa always convertible to a dfa? or never? Strictly speaking if we convert the nfa to a dfa is it the same machine? these and many questions more///////////

just to save time I thought I'd post this in 220 forum... has anyone finished the assignment yet?...how long did it take? if it took you like more that a week, can I have a copy, my girlfriends really on my case about spending some more "quality time" with her. I know some of you geniouses/ers who can wiz through this stuff might be able to help me out? She(my girlfriend ) is beginning to think!! that the computer is more important to me than her....


thanks Serge

As stated in the title...

I want to ask the same question~~~~~

try to change extension

haha i wouldnt

you can do it at uni i think

or find a program on the net, use google

why not?

cos changing the extension of a txt file or word document does not convert the format, of course..

it won't work, adobe acrobat will say 'error opening file' or something

try it and see

to create a pdf file......we need to use pdf writers.................
pdf writers are shareware!
can the lecturer re-think this submission criteria please!

To create PDF file you need to install software called Arcobat (NOT Arcobat Reader) which you NEED to buy(VERY EXPENSIVE or you can download from web, hope your guys can find it...^_^ ).

jlin093 wrote:

To create PDF file you need to install software called Arcobat (NOT Arcobat Reader) which you NEED to buy(VERY EXPENSIVE or you can download from web, hope your guys can find it...^_^ ).

Hmm it seems this assignment is encouraging illegal activity already... :(

they wouldnt make us buy stuff, maybe its on the 101 CD, I saw some acrobat stuff there.

http://www.pdf995.com/download2.html
This one converts to pdf from any file format

Anyone who use a Mac will be able to create PDFs easily as this function was built-in to the OS.

If you don't use Mac and don't want to install softwares into your computer, you can create PDFs online at Adobe's web site. Here is the link:

http://createpdf.adobe.com/?v=AHP

Sing up for a free trial and you can create 5 free PDFs.

Hope these helps.

You can also try using the program on our 220 resources page

says and I quote

[quote:eebbef5674]
for drawing graphs and automata in pdf format

For the regular expansions after the expanding we need to draw DFA and NFA. Do we need to draw them with brackets or without them

part1

1 to 1 with (ab|c) as a loop

or

with open brackets (expanded brackets)
1 to 2 is a
2 to 3 is b
and so on...

hi, guys, can someone explain what '|' means?

Does it mean union?

here is example "a|ab".

jlin093 wrote:

hi, guys, can someone explain what '|' means? Does it mean union? here is example "a|ab".

it means a and ab
| is a plus

eg
(a |ab)(ccc|d) = accc ,ad,abccc, abd

hope this helps its like maths

I dont really rem coz i was changing it a lot but i think
like in the text file and then i put my name id and upi after the numbers

hut wrote:

mine is as below. and i got full mark for this part. 0 1 2 0 0 0 0 -3 0 our difference is only that my total weight is 0 while yours is 1. i do not think it is fair to mark yours as wrong actually.

Did you put just that in the text file you submitted or this

3
0 1 2
0 0 0
0 -3 0
0

can someone who got full marks display there answer, or can someone else tell me why this is wrong, thanks

0 1 2
0 0 0
0 -2 0

yeah id be keen for that too, didnt really know what i was doing on that question but I thought I had it right

i submitted that matrix and got full marks - lol

but then my marker wrote this,
[quote:cf8a6b4506]
Your programs were TOO fast. (I am sure, this is because your program produced the short, yet WRONG answers!)

mine is as below. and i got full mark for this part.

0 1 2
0 0 0
0 -3 0

our difference is only that my total weight is 0 while yours is 1. i do not think it is fair to mark yours as wrong actually.

ok then what's wrong with my one

0 1 1
0 0 0
0 -2 0

looks okay, i didn't think you had to give a result less than zero. just show that the algorithm will not pick the least weighted option.
In all the cases here that seems satisfied.
get it remarked,
altho sum markers deduct more for annoying them a 2nd time.

i got 0 for this,

Can i ask for remark or smth?

Jim wrote:

can someone who got full marks display there answer, or can someone else tell me why this is wrong, thanks 0 1 2 0 0 0 0 -2 0

I got full marks for this:

[code:1:384aa920e6] 3
0 1 2
0 0 0
0 -2 0
0[/code:1:384aa920e6]

Christian

Jim wrote:

Did you put just that in the text file you submitted or this 3 0 1 2 0 0 0 0 -3 0 0

yes, with the nodes number 3 and closure 0.

hi, does anyone know where i can find the marking schedule for assignment 1? i got an unexpected low mark. really wanna find out what is going on.

thanks!

(or if some tutor has it, could you please send me a copy? thank you very much! my email is twan029@ec.auckland.ac.nz)

have contacted with the marker and it has been fixed.

but still have question about my updated mark.

what u guys got for assignment 1?
they deducted me 15 marks for speed!
how's u guys?

Somehow I have this feeling that assignment 1 was badly marked!
not saying it's markers fault or anything, maybe it was the inconsistent marking schedule??

If possible, could we please get a copy of the marking guidelines/ requirements, and the testing samples. Not just for the marks, but for the sake of knowing what is actually the expected knowledge from us!

But then again.......... I suspect any tutor/ Mark Wilson will see these posts at all.........

yren004 wrote:

what u guys got for assignment 1? they deducted me 15 marks for speed! how's u guys?

I got 99 of 100 so I'm pretty happy!

Christian

chsi021 wrote:

Somehow I have this feeling that assignment 1 was badly marked! not saying it's markers fault or anything, maybe it was the inconsistent marking schedule??

yes, i have the feeling too(but not only this assignment.). actually i got zero for question 1 at first. then i contacted my marker and he sent me the test input and sample output. mine is the same except the first digraph ONLY which i think the sample output is wrong. (i posted that in my another thread.) anyway, when i got my updated mark, i still got TWO wrong outputs somehow. and then, no reply for my enquiry any more. i think maybe i must have caused too much trouble.

i also think we should get the mark schedule posted. is there any one knowing who is supervising the assignment marking? thanks!

if there is a matrix having only one entry, 1. does that mean that is a digraph which has only one node and there is a loop which weights 1?then, the shortest distance from this node to itself should be 0? or 1?

thanks!


p.s.
the digraph in the standard format is:
1
1
0

can we have the sample answer for assignment 1? it's good for us to have a look at the code because we could improve our skill by doing that. If we are allowed to have get the sample answer, that will be great.

hm.... sorry about this hassle.

-------------------------------------------------------------------------------
assignment get marked by different markers, thats cool

we do the assignment differently. thats cool

marker marks the assigment. thats right

depending on who the marker is. that is how lucky you are,

you can 15 or MORE marks. thats, 15% of total 8.333% even though the Answer were same. especially for Q2 in Ass1.





So anyone who put 4 nodes in Q2 should get 25 Marks. not 10

What bout 3?

for Q3, yes, yes assuming the answer we put are exactly like in the sample style, and right.
there shouldnt be any reason for deducting.



for Q2, given a valid answer that Dijsktra won't work for Negative matrix with example of 4 NODES, which I and my friend did , exaclty same nodes.... had a different marking result, and i dont mean by 1 or 2 marks.

zerodays wrote:

for Q3, yes, yes assuming the answer we put are exactly like in the sample style, and right. there shouldnt be any reason for deducting. for Q2, given a valid answer that Dijsktra won't work for Negative matrix with example of 4 NODES, which I and my friend did , exaclty same nodes.... had a different marking result, and i dont mean by 1 or 2 marks.

Why would you use 4 nodes when the assignment asks for the smallest graph you can find showing that Dijkstra doesn't work? Should be easy to do it with 3 nodes....

Christian

4nodes was what i thought of it as shortest path,

i aint here to say 4 nodes is right, but it is closest,

i write becuz of different brain interpretation between markers.

Anyone else having trouble starting this assignment?
Ive read the notes over and over for Automata, still have no idea how to do Q1, Q2 I have attempted, got the NFAs (though one of them came out a DFA and dont know how to get an NFA for it so I guess Im doing it wrong) and am pretty much lost.

Just want to know if anyone else is having trouble

Same here i thought i was doing NFA but after reading the notes i realised its DFA.

now that I have your undevided attention.when is an answer an answer?
An answer is only an answer if it is all I know!! Which means does anyone have a copy of the questions in parts of assignment two that involve exercises from the course book. Gee wiz if you give me the questions I won't tell you my answers!!

What sort of format are they looking for?

do we have to draw the DFA or is it acceptable to show the starting states, finishing states, transition table, etc?

in otherwords, do we need to represent our answers graphically or textually?

Graphically...

r u sure coz i was thinking doing it as tables

I was thinking of an adjacency list

Well, if you go to the Assignments page, you will find a link to a tool for drawing graphs. So, I think we have to do it graphically.

are we treating 0 as a positive integer

i believe not.. but i could be wrong :P

if we have two regular expressions R1 & R2, sigma = {a,b}

R1 = a
R2 = b*

and we have another regular expression R3

R3 = R1|R2

should R3 accept the empty string because R2 has to?

In terms of logic, I don't think it should accept the null string.

A U {} = A...

I view it as R3 = a|b*

so yeah, I would of thought that it would accept the empty string since b^0 is acceptable

Since many people seem bothered by Ass 1 marking, here are the general guidelines given to markers. They are allowed some flexibility in interpretation but should be consistent. If you believe an error has been made in marking, contact the course administrator.

--
For Q1, you should mark 55% on correctness (using testfloyd1) and 45% on speed. Run mine and compare with students. If theirs does not compile and there is no obvious reason that can easily be fixed, give 0. Otherwise deduct 10%, fix, and run.
If they get less than 5/10 right on testfloyd1, they don't get to do speed testing.

Each of testfloyd2, 3, 4 is used for the speed testing, independently. A factor of 5 worse than mine scores 0, and a factor of 0.75-1 scores full marks. You decide the scores for the other ranges .

For Q3, don't be too tough on obvious cut and paste errors but do deduct something for carelessness. Be very tough on anything that is a clear error of logic.

For Q2 they don't need to give any justification why their example works. Choose some decreasing function of n + e that is 1 when n+e=6 and 0 for n+e >=10, and award marks accordingly. If they have a negative weight cycle, give them 0 for the question.

-----


Also, a correct answer for Q2 is

0 1 2
0 0 0
0 -2 0
0

I can make available the test files for Q1 if enough people want them. My solution java program I would prefer to keep. It is not a great example of programming style. I am happy to discuss it individually in office hours with those who care enough about it to come.

thanks for the explaination of the assignment marking!

and i hope we can have the test files for Q1 available. thank you!

i am curious and a habitual speed freak so of course i would like to see your java files.
you can still keep them.
your mentioning of the fibonacci heap was a teaser Mark, and you haven;t yet explained it to my 3rd year friends....damn,
hope you're lecturing my 3rd year papers.

if you change your mind about showing your java files call me.

yeah,, i really need to see the test file ofr Q1 , because i did some wrong in first question but i still dont know why it was wrong.

I too would like to would like you to make Q1 test files available, I hope you still read or forum.

the relationship between L1 n L2

jjin008 wrote:

the relationship between L1 n L2

It's the intersect, which is the parts of L1 and L2 that are equal. So if L1 = {a,b,c} and L2 = {a,d,e} then L1 n L2 would be {a}.

I think.

Christian

i confused Q1 (a)
what does 3kb's mean in this question?
can someone understand this question explain to me please?

i have some idea: does it mean we need to build DFA that accepts
multiple 3 times of b (b is the input alphabet) ??

yep

Then what does the {a, b, c} stuff mean?

What i understand from the question is that- the input alphabets are gonna be a, b or c (thats why the {a, b, c}). there can be any number of a's or c's. but there is a restriction on the number of b's. the input number of b's should be a multiple of 3, i.e 3, 6, 9...so on.
we have to build a min DFA that accepts inputs like abbbc, abacbbcababcb, but rejects inputs like abb, abc.
hope that helps :)

About this "3k b" thingee...
Is our DFA only supposed to accept an input that has multiple of three "b"s IN A ROW...or, it doesn't matter where these "b" are, as long as there are mutiple number of three "b"s.

say,
It would certainly accept "abbbc"
Is it supposed to accept "ababcbs" as well, please?

[quote:5119cf6eca] we have to build a min DFA that accepts inputs like abbbc, abacbbcababcb, but rejects inputs like abb, abc.
hope that helps :)

jbal034 wrote:

[quote:458b8d5c8a] we have to build a min DFA that accepts inputs like abbbc, abacbbcababcb, but rejects inputs like abb, abc. hope that helps :)

well does that mean that the b's can be anywhere caz from what i understood it could be like this for eg.. abbbbbbca like 3k b's continiously...

could some one please clarify me on this.. thx :)

Building:109(General Library), Room:B10---> Family Name: A ~ D
Building:115(Lower Lecture Theater), Room:201---> Family Name: E ~ L
Building:109(General Library), Room:B15---> Family Name: M ~ T
Building:115(Lower Lecture Theater), Room:308---> Family Name: V ~ Z


Please try to get there by 615pm at the very latest. Reading of test starts at 620pm. Test ends 730pm.

Can anyone please tell me where Rm 308 of LLT is?

Thx so much

i think its just LLT

I was thinking about that too, but I noticed that:

[quote:c852c92e98] Building:115(Lower Lecture Theater), Room:201---> Family Name: E ~ L
Building:115(Lower Lecture Theater), Room:308---> Family Name: V ~ Z

oh true

check the map it got the building numbers, may b one of those rooms is ULT. yea just check the map with biulding numbers.

Just remembered a rule that was omitted from the concatenation list...
Rule 1.5 : If a start state of M1 is also an accept state, then the start states of M2 are also start states in M12 (the new automaton).

Cheers,
Jono.

what is the difference between (a|b)* and (a*|b*) ???
are there the same thing??
somebody help please!

byan013 wrote:

what is the difference between (a|b)* and (a*|b*) ??? are there the same thing?? somebody help please!

I think that would be the same thing....


Christian

i dont think so

i think (a*|b*) u dont really need brackets so when i expand it i think i woud get this

a,b,aa,bb,aaa,bbb,......

they would have to mean different things.
For (a|b)*, the * is the 1st precedence.
So what do you do with the *?
How do you apply Kleenes to the brackets?
We don't have egs in our lecture notes.
I'm guessing you have multiple As and Bs together.
Like aaabaaaabbbbaabababbbaaaa....

(a|ab)* ==> {a, ab, aa, abab, aaa, ababab, .... }
This is what i think but not sure.. have not attended lecture..

inkeol83 wrote:

(a|ab)* ==> {a, ab, aa, abab, aaa, ababab, .... } This is what i think but not sure.. have not attended lecture..

no its not u need to *
a ab aab aba aaba abaa .....

byan013 wrote:

what is the difference between (a|b)* and (a*|b*) ??? are there the same thing?? somebody help please!

No, they are not.

(a|b)* = {a, b}* = {emptyString, a,b,ab,aa,ba,bb,aba........}
(a*|b*) = a* U b* = {emptyString, a,aa,aaa,aaaa,aaaaa.....b,bb,bbb,bbbb,bbbbb......}

i think lance is right

Is Lance perfectly sure?

(a|b)* = {a, b}* = {emptyString, a,b,ab,aa,ba,bb,aba........}

if sure show me exact input strings available..
I dont quiet get your answer..

got the same problem here son heh :)

i thinking mad about this..

Say lance is right,

[quote:0461a6d350] (a|b)* = {a, b}* = {emptyString, a,b,ab,aa,ba,bb,aba........}

I think all of these are mentioned in the tutorila... ^.*

so just as a suggestion:
1) make the NFA (a|b ) having same start state.
2) take the closure of that

In order to answer the Q1, do we need to draw the graph of the DFA/NFA, or we just need to express it in words, like M=(Q={a,b,c}.......)?

Also, if we need to draw the graph, how can we draw graphs in the notepad? anyone can give me an advice?

Anyway, what program r u all using? notepad or ppt?

Hi all. just to let you know way way in advance.
me and some other people are trying to organise a lan for after the end of year exams. it will be a whole day lan, and the comps will be setup the day before so no hassels

so keep an eye out and try to make it if you can

(¯`·.¸lingario¸.·´¯)

Make sure you get some good stuff and we'll be there.

Make sure you get some good stuff and we'll be there.

what is lan????

tutor was teaching this stuff and divided this fomular
10*(10*10)0*0 into 3 parts..

m1 = 10*
m2 = (10*10)
m3 = 0*0

and concadinated them..

If this is the right way of solving problem than where do I cut from the input?

[code:1:73c2d5f823]
ie) a|(a|b)* (bc|(ba|ccc)*)*
m1 m2[/code:1:73c2d5f823]
Is there any way to diveide m2?

inkeol83 wrote:

If this is the right way of solving problem than where do I cut from the input? a|(a|b)*(bc|(ba|ccc)*)*

I'd like to know too, as when I was originally working this out, I got this huge machine with 28 nodes where I was working on R1 R2, with

R1 = a|(a|b)*
R2 = (bc | (ba | ccc)*)*

but I found it much easier to work on the expression R1 | R2

R1 = a
R2 = (a|b)*(bc(ba|ccc)*)*

which yielded a machine with just 13 nodes that whittled away to about 7 or 8 nodes after minimization

Does anyone know (100% sure) if we will have to know the pseudo code to things like BFS, DFS, Floyd, etc for the test or if we just need to have a working knowledge of how to do everything?
Like, knowing how to do things is easier than knowing the coding steps - so does anyone know which it is?
Thanx

For the questions 2-5 of part 2, are these supposed to follow on from each other, or are we supposed to start over each time?

on the course web page, it shows
Assignment 2 due 26 September 2003

in the assignment dropbox, it shows
COMPSCI.220.C.SS Compsci220 Ass-2 Mon Sep 29 21:00:00 2003

then... -_-''

i am guessing its has been extended :D

Yeah - the assignment due date is Monday - I have an email from Michael Dinneen saying that - so yeah...
Thank goodness!

I dont know which is which..
If there is more than one starting state than it is NFA
but condition (May have more than one transition for a given character)
I dont understand what it is..
Sum1 explain.. plz

If i'm not wrong what that means is that for each state, if it has like 2 'a' transitions coming out of it going ot different states then it is an NFA....

It means that if you have two arrows going from the node with the same letter, then it is an NFA. Its ok to have more than one outgoing transition as long as each transition represents a diferent letter.

what's the precedence of "!" ?
the question doesn't mention that~~~

hrh wrote:

what's the precedence of "!" ? the question doesn't mention that~~~

I've noticed that as well and sent a mail to MJD, hoping to get an answer in time...

Christian

Post his response here if you would please.

christian wrote:

hrh wrote:    what's the precedence of "!" ? the question doesn't mention that~~~ I've noticed that as well and sent a mail to MJD, hoping to get an answer in time... Christian

According to the tutor which i asked after the tutoriual today, the "!" has the highest presedence of all the productions.

Christian

Having done the assignment on paper, i decided to begin putting it into a PDF file and submit it...

More fool me to think this would be an easy task...

I downloaded the ipe program on the resource page, and after drawing my first answer realised i couldnt get the text i had written in the editor to show up in adobe acrobat reader...

So i sought out other PDF creaters, and downloaded around 5 others, each one requiring administrative rights to install, rendering them absolutley useless...

What the hell is wrong with Word .doc files?
You can draw pictures, import bitmaps, and they actually display the text you have typed in....

Im probably missing something completely obvious that is making my text not appear, but i still think its stupid to have to learn how to use some third party program to create pdf's when micro$oft word is entirley capable of performing exactly the same task!

-Rob-

strong agree...change to use Word!!!!!!!!!

Agree!!Agree!!
There is no point to put our time on this kind of stuff!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Change it to doc. please!!!!!!!!!!!!!!!!!!!!!!

I agree Maximum Redg! Lets make this into a poll.

yes, the more exclamation marks you put, the more people will see your point of view

:p

anyway, i guess the reason pdf was chosen is cos it's portable.. not all the markers use windows and office i am guessing (shock horror)

it is a bit of a bugger to make them though, esp. if you havent before (i havent)

i would prefer to have this be a paper assignment.. it would be so much easier to hand in a sheet of refill

Has anyone figured out how to make text appear in the pdf using that sh*tty editor that is on the resource page?

Have u tried downloading a warez Adobe PDF Writer already?

And does anyone know the answer to my thread question below this one? (Test Coverage)

download pdf995
use Word, then "print" to .pdf file.

If you're using computer in the lab, you could print the file to .ps then convert it online with ps2pdf.com (MS Word will print your .doc to a .upf file or something like that, you need to change the ext name to .ps manually).
Also, MS Visio on CS dept's computers is very handy when dealing with automata.

[quote:c883cc3e3e] I agree Maximum Redg! Lets make this into a poll.

Stop guys. There is an easy way to convert your word file to pdf file.
[url] http://web.com.auckland.ac.nz/services/student/studentpdf.htm[/url]
Check the above link and you will all be on the spot...

umm...isn't that service for students with access to the business school computers?

do we have to use com school computer???

I got the r drive from the cs lab anyway. I am not sure whether others got that as well:P

Hello fellow hardworking students,

Can somebody who knows tell me, if Mark's section for our test include (and automata theory) would be within the test material.

If someone can point out what includes and excludes, that'll save my day!

Thank you all~

VP1

Hmm, check your email, i got one from Mike a couple of days ago clearing this up, i deleted it... but i think it was something along the lines of that there will only be automata theory, and not the stuff hes been doing with parse trees and grammar....

i think.....

[color=darkblue:5a565c5420] This is from another thread........[/color:5a565c5420]

[quote:5a565c5420="Mark Wilson"]
Please try to get there by 615pm at the very latest. Reading of test starts at 620pm. Test ends 730pm.

Do we have the lecture today?

no

1. Write down the strong components of the digraph whose adjacency
lists representation is given below.
0: 2
1: 0
2: 0 1
3: 4 5 6
4: 5
5: 3 4 6
6: 1 2
ANSWER:
{1, 2}, {3, 4, 5}, {6}


Where is the node 0?
i think the answer should be {0,1,2} {3, 4, 5}, {6}

yes ur right

is the unary production a recursive one? I've got something like

<this> -> -<this> | <next> (thats a minus sign at the front of <this>)

and by this production, I should be able to parse something like -------4 as a valid string. I think it should be like

<this> -> -<next> | <next>

where the next production should catch stuff like bracketed expressions and the root production and things like that. Any advice, anyone?

is it: {es, a,b,aa,bb,aaa,bbb,....,}

or: {es, a,b,aa,bb,aba,bab,abab,baba,....,}

es = empty string.

Anyone who knows?

Christian

I think it's the latter because the (a|b)* term on the right picks up basically every combination of a's and b's in the language that the "a" on the left doesn't (assuming sigma is {a, b}) including the empty string.

What is the meaning of "#" and x#y?

I saved my work as a PDF file in IPE. But the adobe reader can not open it!!!! Some one help me please!!!!

that is y I suggest to change Word to submit lo..if someone wish..convert them by theirself lo..they know how to convert to PDF anyway...><!!

sorry to say that lo..finally I got mine one converted succesfully...good...hoho

how did u manage that?

just like someone said on the forum..go to adobe web site and click free trial..apply one account..then u can convert 5 free .pdf document lo..hahha..that works.......

this confuses me because many different thoughts are on forum and I think is correct but still not sure!!
I want to know the true answer for it..
I might have drawn wrong automata for all questions..

yes the regx (a|bc)* means something like

aaaaabcbcaaaabcbc

ie. any number of a's and any numbers of bc's in any order for any number of times.

you can think of it this way,
1) choose from either a or bc
2) do as many times of 1) as you like!

HTH ^^

i am confuse about this , who can give me a regular expressions

i agree [quote:fa9e0df82c] It's the "|" .

Does anyone know what the "+" sign denote for? Does that mean the "|" operator or the actual plus operator?
Cheers!

It's the "|" .

Me too
While on the topic of Q3, im confused about part 1, not sure how to display whitespace in context free grammar. Any examples I can look at? (Ive already googled, didnt get much)

maybe you did get an answer - but it was white space so you missed it?

As long as inputs are concerned, wot is the difference between automata (bc|ba|ccc)* and (bc|(ba|ccc)*)* ?
They accept the same set of inputs. don't they? plz?

They are not the same...You can refer to a previous post with a similar question..

Let me ask all of you, do you think it will be any point of making this automaton? i manage to get the answer (i hope i did) and its this long a$$ DFA i also had the pleasure of minimising.

What is the whole point of doing this? so that i can waste a whole day of my life trying to figure a pointless stuff... i think the previous 2 automata will give me enough practice... it is boringly easy unlike most of the other assignments where there would be some kind of challenge.

I think this is the equivalent of copying out a page out of the compsci text for a 100 times.

_____|__1___ |__2____<-- inputs
__a__|_empty_|__b___
__b__|___c___|__a___
__c__|___a___|__b___

this is transition table and there is a --1--> empty
Than is that not DFA? so NFA?

Or transition going to Empty state doesn't matter for finding out which Finite Automata it is?

inkeol83 wrote:

_____|__1___ |__2____<-- inputs __a__|_empty_|__b___ __b__|___c___|__a___ __c__|___a___|__b___ this is transition table and there is a --1--> empty Than is that not DFA? so NFA? Or transition going to Empty state doesn't matter for finding out which Finite Automata it is?

I think you can have an empty state in a DFA, it just means it is a not very usable machine.....You need to put the empty state in the transition diagram, though.

Christian

are we expected to give grammers which always extend privious questions?
i.e. question 5 extends 4
4 extends 3
3 extends 2
2 extends 1

I think the questions are independent of each other...

i think they extend each other

Each grammar should based on the its previous one.
We can tell that from the 4.8.2.5. The example contains comparison operators, which should be added to our grammar in 4.8.2.3
That's what I think.

Great minds think alike

[quote:906a65fc4c="The Fri"] Great minds think alike

Agree...

do we need to do Q5 on 4.8.2 ??
the question has a * on it

You mean 4.8.4?

Im assuming we do, since the assignment specs say Sesction 4.8.4 (1-5) and not (1-4)

yes
i mean 4.8.4 Q5
maybe we do not need to do it , is it?

[quote:5b6816c46b] Im assuming we do, since the assignment specs say Sesction 4.8.4 (1-5) and not (1-4)

the last part of Q2 didnot mention the level of "!" related to other operators, who konws where it should be?

There was a previous post regarding this

[url] http://forums.cs.auckland.ac.nz:8181/viewtopic.php?t=7532[/url]

anyone done 1. (e), could you gimme some ideas how to do it?
also stuck in (f) & (g). thanks

For Questions e and g, theres bits in the course book about these issues. Once you understand question e, I think u might get a better understanding of how to solve f.

can we find a scanner at Uni?? where??

there're some in Tamaki lab.

there are some scanners in the basement of the new computer science building..

Do I lose marks for not putting transition table?

no. as long as your minimized graph is right

anyone can give a hint for 4.8.4 Q5?
thanks

From the IPE homepage download section: "It includes everything you need to run and use Ipe on Windows"

They don't mention they you need Latex, and they don't mention that to use Latex you need Tex or something. Without this thing, it won't convert any text into the PDF files. Just lots of arrows and circles.

Anyone managed to get IPE to convert the text ? Anyone know how to actually download Latex, or what the problem is ?

?????

... can be found in the boxes in the staircase opposite to the resource centre (basement of the science centre).

If you didn't go to the lecture please pick up a copy of the handouts as soon as possible.

Note that I won't give handouts for the remaining lectures since the content is covered in the course book. However, the lectures might give additional examples and some other useful information so it's a good idea to come to the lectures and to read the handouts :-)
Copies of the lecture and assignment handouts can be found on the 220 web page.

Hope you enjoy this course :-)
Burkhard

Because of the Vice-Chancellor's Robb Lecture Series the COMPSCI 220 lecture moves on Tuesday the 14th October, Thursday the 16th October and Tuesday the 21st October (5-6pm) from LLT to PLT1.

Cheers,
Burkhard

your lecture 2day was interesting.

just wondering about the ray-tracing

has any1 made algorithms so people with bad eyesight can see images on a PC screen clearly ??

does the idea sound possible at all?

.. how would you do that with raytracing? i missed the lecture (sorry) so perhaps i missed something interesting

he mentioned ray-tracing and how it resembles the way we see things in reality, but applied in reverse order.
Instead of the light reflecting off objects and into our eyes, ray-tracing sends a ray out to the object........

i just thought that if it resembles the way things are seen then surely sum1 has altered the algo's to resemble the shortcomings of people with sight problems.

asheltie wrote:

just wondering about the ray-tracing has any1 made algorithms so people with bad eyesight can see images on a PC screen clearly ?? does the idea sound possible at all?

An interesting question :-)
I haven't seen any research papers about this topic. In principal it is possible but there are practical limitations.

For example, assume we have an observer with a lens distortion (e.g. short sightedness). For a given focal point, say the centre, of the image it is possible to trace the rays is such a way that the resulting (distorted) image compensates for the lens distortion of the observer. However, if the look-at point of the oberver changes, say he/she looks at a corner of the image, then this wouldn't be the case anymore. So what you really want to have is an image which dynamically distorts according to the look-at point of the observer.

The above described idea is however useful in another applications, i.e. the correction of images obtained with low quality cameras (such as web cams). Since the lenses of such cameras are usually of very low quality they produce a distorted image. Using a test scene it is possible to develop a transformation which corrects the web-cam image.
Sounds like a good stage 3 project :-)
(Actually there are many papers on this topic but it's a useful topic and has an acceptable difficulty)

Cheers,
Burkhard

i'm doing a Logic and Computation degreee.
And hoping to do a Compsci honours.
If i do 372 and 375 perhaps i would be better equipped for this kind of project for 780? - does that sound feasible?????

I am already doing a 380 project this summer (converting CECIL into wap so students can use their phones to access grades etc.....:-)

asheltie wrote:

i'm doing a Logic and Computation degreee. And hoping to do a Compsci honours. If i do 372 and 375 perhaps i would be better equipped for this kind of project for 780? - does that sound feasible?????

In order to do a Computer Graphics project I usually expect that that a student has done 372 and passed with B+ or better (exceptions are possible). In some circumstances I allow students to do 372 and a 380/780 project at the same time but in general I recommend to do 372 first.
375 is not necessary to do a Graphics project but it is very useful if you want to do a project which involves both Computer Graphics and Computer Vision. I think Computer Graphics and image processing fit quite nicely into your degree so unless there are some regulations which prevent you from doing this I think it's a good idea to do these courses :-)

See you,
Burkhard

what's the big O for the following two loops?
[color=red:2a34bb6438] 1)[/color:2a34bb6438] for (int i = 0; i<1000;i++)
System.out.println("Kill me");

[color=red:2a34bb6438] 2)[/color:2a34bb6438] for (int i = 0; i< 1000; i++){
for(int j = 0; j< 1000; j++)
System.out.prinltn("Kill me");
}

aren't they both O(1)?

i'm not a tutor but these r too easy that the real tutor probably won't bother answering
O(1)
O(1)

altho the 2nd one will actually be O(0), unless u fix the error with your println() statement

why

i would have thought they were O(n) and O(n²)
assuming you meant that 1000 to represent n..

knack wrote:

i would have thought they were O(n) and O(n²) assuming you meant that 1000 to represent n..

One of my friends at other University said that he was told the big O for the previous questions are O(1) (bothof them) by his tutuor. I am a bit confused , that's why I asked such a simple question.

jzho020 wrote:

knack wrote:    i would have thought they were O(n) and O(n²) assuming you meant that 1000 to represent n.. One of my friends at other University said that he was told the big O for the previous questions are O(1) (bothof them) by his tutuor. I am a bit confused , that's why I asked such a simple question.

We will talk about the "Big-Oh" notation in the next lecture. If you have a look into the course book you will see that the "Big-Oh" notation captures the running time of an algorithm with respect to a constant factor, i.e. g(n)=O(f(n)) is there are two constants c and n0 such that g(n)<=c*f(n) for all n>n0.

If your loop takes one thousand steps then choose f(n)=1, n0=1 and c=1001 and you have t(n)<=c*f(n) for all n>n0. This means the loop is O(1).

Similarly you get the same result for the double loop above since both loops have a constant number of steps.

Of course if you change 1000 to n then you get indeed O(n) for the single loop and O(n^2) for the double loop.
You can verify very easily that O(1) doesn't work in that case: let's say the single loop has a running time of T(n)=c*n.
Then there are no constants c1 and n0 such that c*n<c1*1 for all n>n0.

In order to proof that the loop is O(n) you can choose c1=(c+1) and n0=1:
c*n<(c+1)*n for all n>1, i.e. a single loop with n steps and a constant number of steps in the loop body has the time complexity O(n).

Hope that helps,
Burkhard

how about n^-1
do we treat it as o(n) or o(n^-0.1)?

i know it trend to be a constant when n apporach to infinity
but when n is small its result is quite large.
By the way i think i did hear Burkhard said we treat it as n.
But i am not sure. Can anyone tell me?

Cannabis wrote:

how about n^-1 do we treat it as o(n) or o(n^-0.1)? i know it trend to be a constant when n apporach to infinity but when n is small its result is quite large. By the way i think i did hear Burkhard said we treat it as n. But i am not sure. Can anyone tell me?

n^-1 = O(1) since you can find a c, n0 such that n^-1<c*1 for all n>n0.
For example, choose c=1 and n0=1.
Note that the function n^-1 doesn't make sense as a running time since a computer program can't get infinitely fast for infinitely large data sets.

Cheers,
Burkhard

Burkhard:
could u post the solution to exercises on the course page..........







cheers

pump wrote:

Burkhard: could u post the solution to exercises on the course page.......... cheers

Yes, I will post the solutions a couple of days after we talked about the topics in the lecturer. The reason for this is that I want to give everybody the opportunity to try the exercises without being "tempted" to look at the solution first.

Cheers,
Burkhard

Dear Burkhard, could please check it?

ryan wrote:

Dear Burkhard, could please check it?

The hint is correct. If you do telescoping and you have values q>1 in your sum then of course you can still solve the recurrence relation but you can't use the formula given in the hint and your solution is not as nice and elegant as the one suggested by giving you the hint.

If you have a close look at your telescoping sum you will recognise that you can rewrite the sum so that you have a different factor before the sum and values q<1 in the sum which allows you to use the formula in the hint.

Hope that helps,
Burkhard

Hi Burkhard,

I am quite surprised to find that the assignment 3 will only be dealing with the (max) first 2 weeks of your lectures. I mean I didn't expect it to be due so soon.



I have CS335 5% and IS330 14% all due on the same day Monday 13th Oct, so if there is going to be another extension, would it be possible for you to let us know in advance?

I know it's all about student psychology - give an extension too early and people will still leave to the last minute. I'd just like to know whether I need to stay up all week or if i could schedule some zzz's for Sunday?

Alex

Yes, I also hope there will be a extension.

I have two cs230 assignments, one cs210 (very hard one) and the cs220 assignment due in next week.

I am gonna die......

~_~'

the 220 a3 is very easy if u take a good look at it.
i think that's why it's due early, most of it can be done already with knowledge taught in tutorials.
the rest of the answers are in the 220 book

hope this doesn't spoil your chances for extensions, but it's hardly worth one :-)

al wrote:

Hi Burkhard, I am quite surprised to find that the assignment 3 will only be dealing with the (max) first 2 weeks of your lectures. I mean I didn't expect it to be due so soon.

The assignment 3 is very easy and you can answer most of the questions already now. Note that question 3 is not related to the analysis of sorting which we will do later in the lecture. You can solve the question without any knowledge of Computer Science just by thinking about it. We will talk about the big-Oh notation today in the lecture and then you will then be able to finish that question, too. A good student who understands everything in the lecture should be able to finish the assignment in 1-2 hours maximum!

I will hand out assignment 4 on Friday and that assignment will be a bit longer and will also contain some programming questions. Anyway, I better tell you now that I give extensions unless you have a doctor certificate or some very special circumstances arise.

If I would give an extension then:
1) you are likely to need another extension for the second assignment
2) you have less time to study for the exam
3) I can't publish the sample solutions until everybody hands in which might mean that you don't get the sample solutions before the exam.
4) the markers are even less likely to finish marking before the exam which certainly doesn't help you with the exam.

If you have too much work to do for other courses please feel free to ask the supervisors of these courses for an extension :-)
The workload for this course and for this assignment in particular is well within the usual limits and shouldn't cause you any problems.

Cheers,
Burkhard

Cool. Thanks for the reply. I didn't notice 25/6% = 4.16% and there's an assignment 4! Duh!

[url] http://www.cs.auckland.ac.nz/compsci220s2c/lectures/Burkhard/220S2C_2003_Part3_Lec2_solutions.pdf[/url]

I also posted a preliminary version of the slides for the nest two lectures. This covers everything you need to know for the assignment. See "Section 3: Tools for Algorithm Analysis"

[url] http://www.cs.auckland.ac.nz/compsci220s2c/lectures/[/url]

Cheers,
Burkhard

[url] http://www.cs.auckland.ac.nz/compsci220s2c/lectures/Burkhard/220S2C_2003_Part3_Lec3_solutions.pdf[/url]

Cheers,
Burkhard

now that i have your attention,

question 2 of the assignment -

is it an error that b must be > 1 ???

worked it out several times and it seems wrong - if sum1 who has done it could confirm that i am wrong that would be appreciated *thnx*

I don't think it matters because a>b, therefore the ratio you get at the end should mean that it fits nicely into one of the solutions on p42-43.

sweeet

- burkhard explained it in the lecture 2day

I really still don't understand this question about how to sum the items left over up, and didn't follow what was explained in class about it. I don't understand how to use the knowledge that a<b<1 to in any way simplify the terms so they would fit into the hint given...

it seems alot of people do not know about it.........i was able to ask sum1 from China, where they learn the formulas like this in high school maths.

maybe ask the tutor to explain...........or try it without using that formula???

sorry i'm no help but it's all i know

I dont know how to do this either, I understand Telescoping, but not with confusing-ass formulas like that.

a>b>1 is very useful, without this, you won't be able to use the hint given.........

a>b>1 has some other meanings. rearrange it into a simpler form, like x<y.

hope you guys understand^^

Hey guys,
Coming up on Monday is a meeting for CompSci reps. Please let me know asap if there is anything that you would like me to take to that meeting.
You can either post here, but better yet, email me:
sdan017@ec.auckland.ac.nz

Thanx
-SAM-

When will the test mark be out?? It's been quite a while since we did the test.

have to agree,

where are they?

i had emailed Rakib and he replied saying that the test marks will be out by the end of next week.

cool, thanks.

Can anyone tell me what the format of the assignment3 solution? At the end says put the answer into a .doc, does it mean just the final answer or include workings as well?Cheers

I want to question it as well, seems many question can work out just the first eyesight, not really know how to show working on some of these questions.

plus, can we handwrite then scan it?

Felix wrote:

Can anyone tell me what the format of the assignment3 solution? At the end says put the answer into a .doc, does it mean just the final answer or include workings as well?Cheers

For question (1) it's enough to give the solution - though if it's wrong you have automatically 0 marks, whereas if you show your working the markers might give you partial marks.

For question 2 and 3 you MUST show your working.

The solution should be in '.doc' or 'pdf' format. If you write the document by hadn and then scan it make sure that the images are compressed. It's probably best to first reduce the number of grayscale bits and then convert it into gif-format. Anyway, as long as the markers can read your document on their computers and it is not too big (< 1MByte) then it's fine.

Cheers,
Burkhard

It seems that the lecture slides are no longer accessible through the compsci website... is it deliberate or is it being fixed?

gche043 wrote:

It seems that the lecture slides are no longer accessible through the compsci website... is it deliberate or is it being fixed?

Works fine with me. Maybe the server was temporarily down - this has happened a couple of times lately. If you access the slides from home the chance that something doens't work is even higher since all connections outside the department are managed by ITSS.

Cheers,
Burkhard

in the answers to FIRST SEMESTER, 2002 exam, georgy has got in a table that a polynomial with leading term 100n^3 is O(n^4)(the table on page 2, 4th row). Is this a typo?

without seeing the paper - it looks like a mistake '_,_'

It doesn't look like a mistake to me. It seems true, though not as precise as it could be. Remember what the definition of big-O is: the key fact is that if f is O(g) and h is bigger than g then f is also O(h). It is only an inequality in the definition after all.

I haven't looke at the original either.

jwel027 wrote:

in the answers to FIRST SEMESTER, 2002 exam, georgy has got in a table that a polynomial with leading term 100n^3 is O(n^4)(the table on page 2, 4th row). Is this a typo?

It's not a typo, 100n^3 is O(n^4), but it's not the smallest O, called big Theta, which is what we really want....

Christian

Can someone please help me with Question 3, I must be missing something because I thought the quickest sorting algorithm available is something like O(n log n). So, how are we supposed to come up with a linear time algorithm?? I have read over the question a million times, but I still can't spot the catch(if any exists).

Thanks

linear time means.....0(n)

I know, isn't O(n log n) greater then O(n)

jrub001 wrote:

Can someone please help me with Question 3, I must be missing something because I thought the quickest sorting algorithm available is something like O(n log n). So, how are we supposed to come up with a linear time algorithm?? I have read over the question a million times, but I still can't spot the catch(if any exists). Thanks

The fastest comparison based algorithm for sorting a collection of items with a total order but no other restrictions is indeed O(n log n)!

However, we do have some additional restrictions, e.g. we know that all items are within a certain range of numbers ... well, I can't say more than this without giving the solution away.
You might also want to think about whether you really need comparions for sorting the items. By the way, the solution has nothing to do with the sorting algorithms explained in the course book.

Cheers,
Burkhard

Cheers

... now online :-)

[url] http://www.cs.auckland.ac.nz/compsci220s2c/lectures/Burkhard/220S2C_2003_Part3_Lec4_solutions.pdf[/url]

and

[url] http://www.cs.auckland.ac.nz/compsci220s2c/lectures/Burkhard/220S2C_2003_Part3_Lec5_solutions.pdf[/url]

Cheers,
Burkhard

The assignment was handed out on Friday. I put all left over copiesin the 220 box in the staircase opposite to the resource centre (basement of the science centre).

You can find an electronic copy on the 220 assignments web page:
[url] http://www.cs.auckland.ac.nz/compsci220s2c/assignments/assignment4.pdf[/url]

Have fun :-)

Burkhard

I looked at the assignment web page but there is no such skeleton file methinoned in the handout avaliable. Is that because you haven't put it up or it resides somewhere else?

Blah wrote:

I looked at the assignment web page but there is no such skeleton file methinoned in the handout avaliable. Is that because you haven't put it up or it resides somewhere else?

Sorry, completely forgot!! :-(

I have put it now onto the web page. Thanks a lot :-)

See you,
Burkhard

who tell me

if f(n) = n - n^2

what is the Big-Oh notation of the funtion

O(n) or O(n^2) which one


thanks

O(n^2)

Actually, when computing big-O we want the tightest upper bound. Any negative term does not increase the rate at which an algorithm slows with problem size.

Perhaps you can try finding a tighter upper bound on O(f(n)): see if you can find a c such that c.n < f(n) (i.e. f(n) is O(n)).
If that isn't enough fun, you could then try to find a c such that, c.1 < f(n) (i.e. f(n) is O(1)).
If you are STILL not sick of it, you could try to write a Java program that runs in time f(n).

Jono.

This whole thread doesn't make sense. The definition of big-O on p27 of coursebook only refers to functions that are (eventually) positive-valued, and n - n^2 certainly isn't.

The more general definition (which is standard but not needed in our book, since running times of algorithms are nonnegative) allows functions that have both positive and negative values. In this case the definition is that f(n) is in big-O of g(n) if there are c>0 and n_0 such that |g(n)| \leq c |f(n)| for n>=n_0.

Under this definition we have n - n^2 \in O(n^2) and that is as tight a bound as you can get.

Hey !
Just got the marks for Ass-02 . I got 0 cos my file couldnt be opened . After all the trouble i took writing it up , getting it scanned , then getting it converted to pdf format . it opened fine on my computer and the comp at uni .
And it takes over 3 weeks for them just to tell me that my file couldnt be opened . I'm halfway b/w upset n angry . I hope this can be sorted out in someway .
Anyone else havin trouble ?
take care
cheers
M

I suggest you email the course administrator, whose job it is to consider such cases.

for decreasing functions like 4n^-3, do they have a lower computational complexity than constant time O(1)?

I think the functions wth negative powers will have lower Computational Complexity, as compared to 0(1). Reason, when n -> infinity, the function(s) will tend to zero.

twirl wrote:

for decreasing functions like 4n^-3, do they have a lower computational complexity than constant time O(1)?

Functions with complexities like that are actually impossible I think, because it is impossible to increase the computing time by increasing the input data....

Christian

Now this is not definite, but in my view if we have a function f(n) = O(n^-1) for example, then the existance of hidden constants means that
f(n) = b.n^-1 + c
Now using rules for determining big-O of a function we have:
O(f(n)) = O(b.n^-1) + O(c) = max(O(n^-1) , O(1)) = O(1)

So in this case, the hidden constants are actually more significant than the n^-k term. Similarly, any function representing a real algorithm cannot be faster than O(1).

Jono.

christian wrote:

twirl wrote:    for decreasing functions like 4n^-3, do they have a lower computational complexity than constant time O(1)? Functions with complexities like that are actually impossible I think, because it is impossible to increase the computing time by increasing the input data.... Christian

That's right, it doesn't really make sense to have a function with decreasing running time. But assumed you really want to have a Big-Oh notation then n^k (k<0) is O(1).

As far as I know O(0) is not defined - but even if it were, you can't say that n^k (k<0) is O(0) since n^k>0 (k<0) for all n. Hence you can't find constants c and n0 such that n^k < c*0 for all n>n0.

Hope that helps,
Burkhard

Can anyone tell me whats the Big Oh for "Log5n*Log5n"???

is it O(Logn)??

It's (log5n)2 which is 25(logn)2. Thi big-oh is O((logn)2)

Cheers!!