stanford-algs/testCases/course3/assignment3HuffmanAndMWIS/question1And2/output_random_32_1000.txt

I belive that right answer is 19 and 9 all others are correct in my huffman algorithm.

stanford-algs/testCases/course3/assignment3HuffmanAndMWIS/question1And2/output_random_48_10000.txt

30 and 12

I'm looking at the fifth test case for n=5, https://github.com/beaunus/stanford-algs/blob/master/testCases/course1/assignment3Quicksort/input_dgrcode_05_5.txt

According to https://github.com/beaunus/stanford-algs/blob/master/testCases/course1/assignment3Quicksort/output_dgrcode_05_5.txt quicksort using the first element as pivot should result in 7 comparisons.

My code says it should be 6, and I've verified it manually.
If you start with [4, 5, 2, 3, 1] then your initial pivot is 4, you make 4 comparisons and you end up with [ 2, 3, 1, 4, 5].
On the left side you call the partition subroutine on [2,3,1] which uses 2 as its pivot and makes 2 more comparisons (6 total comparisons). You end up with [1,2,3] and you call the partition subroutine on the [1] and the [3] which both trigger the base case and result in no further comparisons.
On the right side you call the partition subroutine on just the [5] which also triggers the base case and makes no further comparisons.

from https://github.com/beaunus/stanford-algs/tree/master/testCases/course1/assignment3Quicksort

File names contain 4 relevant values:

n
the number of integers
first
the number of comparisons using the first element of the array as the pivot element
final
the number of comparisons using the final element of the array as the pivot element
median
the number of comparisons using the median-of-three of the array as the pivot element

can you please explain what that means for file input_dgrcode_01_5.txt with values:

3
2
1
4
5

Ravishankar Joshi suggested that the results did not account for symmetric edges. It appears that our solution was based on a directed graph, rather than an undirected graph.

2 test cases contributed by Rahmeen are incorrectly named, and cause tester.py to fail.

These 4 files:
input_Rahmeen14_01.txt
input_Rahmeen14_02.txt
output_Rahmeen14_01.txt
output_Rahmeen14_02.txt

need to be renamed to:
input_Rahmeen_14_1.txt
input_Rahmeen_14_2.txt
output_Rahmeen_14_1.txt
output_Rahmeen_14_2.txt

Hi,

First: thank you so much for putting this together; this very useful.

For input_random_37_200, i found a min cut of 9. Your current output is 10.

Let me know if you need anything else.

countinversion.txt

The following files have wrong solutions.
input_mostlyCycles_14_64.txt
input_mostlyCycles_6_16.txt
input_mostlyCycles_40_3200.txt
input_mostlyCycles_3_8.txt
input_mostlyCycles_9_32.txt
input_mostlyCycles_11_32.txt
input_mostlyCycles_10_32.txt
input_mostlyCycles_22_200.txt
nput_mostlyCycles_5_16.txt
input_mostlyCycles_8_16.txt
input_mostlyCycles_4_8.txt

In some of them (though not all), I've identified the reason to be that your algorithm fails to identify unconnected nodes as SCCs, which they are by definition. See https://math.stackexchange.com/questions/148305/is-a-single-node-graph-a-strongly-connected-component.

For example, in 4_8.txt, node number 4 is isolated. Even though it does not appear in the list explicitly, the SCC algorithm assumes that all nodes 1 to n exist without gaps, which means that if one node does not appear in the list, it does not mean it doesn't exist, it only means it has no outgoing edges. 6_16.txt has the same problem, node 12 is isolated. These two examples were small enough for me to draw by hand.

An isolated node is a SCC by definition, and should appear as a '1' in the SCC output array. If a graph has more than 5 SCCs with 2 or more vertices, you would of course not see this in a top5. But this reveals a bug in your underlying SCC algorithm.

The others have a wrong answer, but I don't know what the reason for the error is.

The first batch of test cases had incorrect results when the sums of the nodes' weights exceeded the range of an integer.

This was pointed out to me by 徐家奇.

I have made a new branch with some new test cases that should account for this problem. I will wait for some confirmation before merging them to master.

https://github.com/beaunus/stanford-algs/tree/3.3.1And2-use_long/testCases/course3/assignment3HuffmanAndMWIS/question1And2

Directed edge distance from 124 to 143 is 13, but directed edge distance from 143 to 124 is 1194.
Spent over 3 days finding out why solution does not match.

• Include parameters from Python3 tester
• Don't pause on failed tests
• Provide summary instead of individual test details

my code gives correct answer for all the test cases in ur repository but for all the questions in programming assignment it gives NULL which is not the correct answer,add some careful test cases please,i m unable to find out my mistake

btw thanks for making this amazing repository

I think the discrepancy is caused by the remainin capacity for loop not reaching the full capacity of the knapsack. It seems like the loop goes as far as capacity - 1. Therefore the results are wrong if the solution for capacity C and C-1 are different, and are correct if both problems have the same solutions.

I'll post here some test-cases that I've tried, with the solution that I've found.

• knapsack-example-w-10-n-10-solution-12.txt
  My solution: 14 (different)
  Items in the sack (starting at item 1): [1, 2, 4, 5, 7, 10]
  Total weight in the sack: 10
  Total value in the sack: 14

• knapsack-example-w-10-n-10-solution-16.txt
  My solution: 18 (different)
  Items in the sack (starting at item 1): [3, 4, 5, 6, 7, 10]
  Total value in the sack: 18
  Total weight in the sack: 10

• knapsack-example-w-100-n-10-solution-171.txt
  My solution: 171 (same)
  Items in the sack (starting at item 1): [3, 4, 6, 8, 10]
  Total value in the sack: 171
  Total weight in the sack: 122

• knapsack-example-w-100-n-10-solution-187.txt
  My solution: 187 (same)
  Items in the sack (starting at item 1): [1, 3, 4, 6, 9]
  Total value in the sack: 187
  Total weight in the sack: 96

Distance for Node 99 should be 333, not 331

https://github.com/beaunus/stanford-algs/blob/master/testCases/course2/assignment2Dijkstra/output_random_1_4.txt

How is NULL the correct answer?
i == j := 0 && You have two directed paths from 2 -> 2 with different weights.

    stanford-algs/testCases/course4/assignment1AllPairsShortestPath/input_random_1_2.txt

The first error in in output_mostlyCycles_3_8.txt
The input file input_mostlyCycles_3_8.txt has 7 edges and 7 vertex
1 3
2 7
3 2
4 1
5 8
7 5
8 4

I verified manually has a single cycle that covers all edges/vertexes -> 1->3->2->7->5->8-> 4->1
The corresponding output file has 7,1,0,0,0 but it should be 7,0,0,0,0 as there is a single connected component of 7 vertexes
and has an extra '1' (note also that the sum counts in the output file indicate 8 Vertex, but the graph only has 7)
(note there is no vertex 6 in this graph)

Similarly input_mostlyCycles_4_8.txt has 7 vertex (and 7 edges)
1 2
2 1
3 6
5 8
6 5
7 3
8 7
and has two strongly connected components (1->2->1) and (3->6->5->8->7->3)
and so the output should be 5,2,0,0,0 but output_mostlyCycles_4_8.txt has 5,2,1,0,0 (and the sum of the counts is '8' which is one more that in in the file (there is no vertex 4)

I've also checked output_mostlyCycles_10_32.txt
which has 11,10,5,4,1 and should be 11,10,5,4,0 (I've checked this one manually, and found input file has 30 Vertex but the sum of the counts show 31)

Other files which seem to have the a similar problem (but I have not verified other than my program)
output_mostlyCycles_11_32.txt (Contains 16,8,5,2,1 but I think this should be 11,10,5,4,0)
output_mostlyCycles_14_64.txt (Contains 48,11,2,2,1 but I think this should be 48,11,2,2,0)
output_mostlyCycles_22_200.txt (Contains 121,64,7,4,1 but I think this should be 121,64,7,4,0)
output_mostlyCycles_40_3200.txt (Contains 3187,4,4,3,1 but I think this should be 3187,4,4,3,0)

In all of the cases there seems to be a extra "1" size in the result

One thought that I had that since first few files with issues have less vertex that the problem size (e.g. input_mostlyCycles_3_8.txt has a problem size of '8' but only has 7 vertexes from the edges in the file that the intention is that that any vertexes not listed need to be filled in with no edges, but if that that the case, it is not clear.

The assignment for Dijkstra's algorithm is given on an undirected graph, but here all the test cases are for directed graphs. Is this on purpose? Can anyone explain why?

https://github.com/beaunus/stanford-algs/tree/unconfirmedTestCasesOptionalTheoryBatch1/testCases/course1/optionalTheoryProblemsBatch1

Created by @Rahmeen14.

Awaiting confirmation.

After writing out the graph by hand, I believe the test case answer for 5_16 in Course 2 Week 1 should be 10,3,1,1,1, not 10,3,1,1,0. Since the inputs only write outgoing edges, and we know 16 total nodes exist in the graph (by the file name, 5_16), we see that nodes 6, 9 and 16 are not mentioned in the input file. Thus, we have our SCC's of 10 and 3, and then nodes 6, 9, and 16 make up the last size 1 SCC's of the output.

Either the file name should be changed to 5_15, which would exclude node 16 and thus provide only 2 size 1 SCC's, or the test case must be corrected. Attached is my drawn diagram of the graph with SCC's circled in red.

https://github.com/beaunus/stanford-algs/blob/master/testCases/course4/assignment1AllPairsShortestPath/input_random_12_8.txt
This test case has -221 min value not -231 in output file (https://github.com/beaunus/stanford-algs/blob/master/testCases/course4/assignment1AllPairsShortestPath/output_random_12_8.txt)

Hey,

I'd like to report an issue with two of the test files in Course 1, Assignment 1, namely:
input_Rahmeen_14_1.txt
input_Rahmeen_14_1.txt

(as well as their associated output files)

Both of these input files have tests which are out of the scope of the first assignment. In both files, the two inputs have a different number of digits. In addition, some of the inputs have integers whose number of digits are not a power of 2. Every other test meets these requirements so these stand out.

As a result, students who chose to simplify their algorithm based on the assumptions given in the assignment will encounter errors running the tester on these files (especially annoying when trying to run automated tests on the entire directory).

Numerous test cases for the Dijkstra problem have weird data, where nodes have edges of different lengths to the same nodes. For example, line 1 of input_random_10_16.txt is like follows:

1 20,460 45,1543 109,763 173,1326 32,660 124,74 184,211 154,512 44,1246 100,152 45,1575 57,1553 81,4 82,654 158,1332 158,902 134,1799
...
45 199,82 1,1543 153,679 5,1187 156,829 139,1270 48,1464 30,176 1,1575 71,881 179,1384 3,1875 126,2

Notice that node one has an edge of length 1543 to node 45, and it also has an edge of length 1575 to node 45. Thankfully, both reverse edges are available from node 45, so we don't have an issue where one direction is faster than the other.

This situation pops up in almost every test case for at least some nodes. It's not a major problem, but it doesn't add anything to have these extra longer nodes - they will always be ignored.

I've been verifying the paths on my code and found that this one path file seems to have some incorrect entries:

Paths from vertex 1 to 6,15,54,62,79 94 and 169 show up in the file as empty, however I've found the following path and verified that they exist.

mmednick@MMDESKTOP-45T7JF7:~/Development/rust/short2/bellman_ford$ diff output_path_random_20_64.txt djk_tcs/paths_random_20_64.txt
6c6
< 6 => path => 1, 38, 59, 57, 32, 81, 99, 85, 86, 144, 142, 117, 64, 49, 4, 51, 103, 179, 119, 131, 100, 163, 165, 129, 84, 62, 79, 169, 6

6 => path => 6
15c15
< 15 => path => 1, 38, 59, 57, 32, 81, 99, 85, 86, 144, 142, 117, 64, 49, 4, 51, 103, 179, 119, 131, 100, 163, 165, 129, 84, 62, 79, 169, 6, 15

15 => path => 15
54c54
< 54 => path => 1, 38, 59, 57, 32, 81, 99, 85, 86, 144, 142, 117, 64, 49, 4, 51, 103, 179, 119, 131, 100, 163, 165, 129, 182, 26, 54

54 => path => 54
62c62
< 62 => path => 1, 38, 59, 57, 32, 81, 99, 85, 86, 144, 142, 117, 64, 49, 4, 51, 103, 179, 119, 131, 100, 163, 165, 129, 84, 62

62 => path => 62
79c79
< 79 => path => 1, 38, 59, 57, 32, 81, 99, 85, 86, 144, 142, 117, 64, 49, 4, 51, 103, 179, 119, 131, 100, 163, 165, 129, 84, 62, 79

79 => path => 79
94c94
< 94 => path => 1, 38, 59, 57, 32, 81, 99, 85, 86, 144, 142, 117, 64, 49, 4, 51, 103, 179, 119, 131, 100, 163, 165, 129, 84, 62, 79, 169, 6, 94

94 => path => 94
169c169
< 169 => path => 1, 38, 59, 57, 32, 81, 99, 85, 86, 144, 142, 117, 64, 49, 4, 51, 103, 179, 119, 131, 100, 163, 165, 129, 84, 62, 79, 169

I've wrote some code to verify the path and was for example for 1 to 6:
[2022-09-06T19:50:49Z INFO short::dirgraph] Checking to see if path [1, 38, 59, 57, 32, 81, 99, 85, 86, 144, 142, 117, 64, 49, 4, 51, 103, 179, 119, 131, 100, 163, 165, 129, 84, 62, 79, 169, 6] is valid
[2022-09-06T19:50:49Z INFO short::dirgraph] Vertex 1 has an outgoing connection to Vertex 38 with a weight of 11738
[2022-09-06T19:50:49Z INFO short::dirgraph] Vertex 38 has an outgoing connection to Vertex 59 with a weight of 48627
[2022-09-06T19:50:49Z INFO short::dirgraph] Vertex 59 has an outgoing connection to Vertex 57 with a weight of 58905
[2022-09-06T19:50:49Z INFO short::dirgraph] Vertex 57 has an outgoing connection to Vertex 32 with a weight of 19391
[2022-09-06T19:50:49Z INFO short::dirgraph] Vertex 32 has an outgoing connection to Vertex 81 with a weight of 70603
[2022-09-06T19:50:49Z INFO short::dirgraph] Vertex 81 has an outgoing connection to Vertex 99 with a weight of 80398
[2022-09-06T19:50:49Z INFO short::dirgraph] Vertex 99 has an outgoing connection to Vertex 85 with a weight of 36552
[2022-09-06T19:50:49Z INFO short::dirgraph] Vertex 85 has an outgoing connection to Vertex 86 with a weight of 39721
[2022-09-06T19:50:49Z INFO short::dirgraph] Vertex 86 has an outgoing connection to Vertex 144 with a weight of 2445
[2022-09-06T19:50:49Z INFO short::dirgraph] Vertex 144 has an outgoing connection to Vertex 142 with a weight of 5282
[2022-09-06T19:50:49Z INFO short::dirgraph] Vertex 142 has an outgoing connection to Vertex 117 with a weight of 56962
[2022-09-06T19:50:49Z INFO short::dirgraph] Vertex 117 has an outgoing connection to Vertex 64 with a weight of 47676
[2022-09-06T19:50:49Z INFO short::dirgraph] Vertex 64 has an outgoing connection to Vertex 49 with a weight of 25843
[2022-09-06T19:50:49Z INFO short::dirgraph] Vertex 49 has an outgoing connection to Vertex 4 with a weight of 8221
[2022-09-06T19:50:49Z INFO short::dirgraph] Vertex 4 has an outgoing connection to Vertex 51 with a weight of 44444
[2022-09-06T19:50:49Z INFO short::dirgraph] Vertex 51 has an outgoing connection to Vertex 103 with a weight of 31513
[2022-09-06T19:50:49Z INFO short::dirgraph] Vertex 103 has an outgoing connection to Vertex 179 with a weight of 49399
[2022-09-06T19:50:49Z INFO short::dirgraph] Vertex 179 has an outgoing connection to Vertex 119 with a weight of 46175
[2022-09-06T19:50:49Z INFO short::dirgraph] Vertex 119 has an outgoing connection to Vertex 131 with a weight of 25699
[2022-09-06T19:50:49Z INFO short::dirgraph] Vertex 131 has an outgoing connection to Vertex 100 with a weight of 70871
[2022-09-06T19:50:49Z INFO short::dirgraph] Vertex 100 has an outgoing connection to Vertex 163 with a weight of 37399
[2022-09-06T19:50:49Z INFO short::dirgraph] Vertex 163 has an outgoing connection to Vertex 165 with a weight of 18912
[2022-09-06T19:50:49Z INFO short::dirgraph] Vertex 165 has an outgoing connection to Vertex 129 with a weight of 50241
[2022-09-06T19:50:49Z INFO short::dirgraph] Vertex 129 has an outgoing connection to Vertex 84 with a weight of 52707
[2022-09-06T19:50:49Z INFO short::dirgraph] Vertex 84 has an outgoing connection to Vertex 62 with a weight of 75646
[2022-09-06T19:50:49Z INFO short::dirgraph] Vertex 62 has an outgoing connection to Vertex 79 with a weight of 25726
[2022-09-06T19:50:49Z INFO short::dirgraph] Vertex 79 has an outgoing connection to Vertex 169 with a weight of 53274
[2022-09-06T19:50:49Z INFO short::dirgraph] Vertex 169 has an outgoing connection to Vertex 6 with a weight of 14487
Path is valid and has a weight of 1108857

I've also manually checked the files and do see those edges there:
egrep '(^1 |^38 |^59 |^57 |^32 |^81 |^99 |^85 |^86 |^144 |^142 |^117 |^64 |^49 |^4 |^51 |^103 |^179 |^119 |^131 |^100 |^163 |^165 |^129 |^84 |^62 |^79 |^169 |^6 )' djk_tcs/input_random_20_64.txt
1 5,15048 38,11738
4 139,62275 49,8221 51,44444
32 57,19391 81,70603
38 1,11738 170,78144 59,48627 96,14954
49 64,25843 4,8221 172,19164 48,10172 120,74866
51 110,39554 103,31513 95,46695 4,44444
57 27,79355 32,19391 59,58905
59 57,58905 25,65394 38,48627
62 84,75646 79,25726
64 117,47676 186,66505 49,25843
79 62,25726 169,53274
81 17,25740 30,63395 99,80398 39,28703 125,55160 32,70603
84 129,52707 ** 62,75646**
85 99,36552 22,39991 109,32698 86,39721
86 144,2445 85,39721
99 81,80398 76,2508 85,36552
100 163,37399 131,70871
103 179,49399 51,31513 113,58428
117 137,46674 64,47676 142,56962
119 179,46175 131,25699
129 84,52707 182,55297 165,50241
131 100,70871 119,25699
142 144,5282 117,56962 187,17444
144 86,2445 142,5282 106,307
163 165,18912 100,37399
165 129,50241 163,18912 193,64077
169 79,53274 6,14487 (final destination)
179 119,46175 103,49399

Dear Beau,
thanks a lot for this very useful repo.
I have an issue with the test cases covering the Quick Sort.
I have passed all 20 for each option, first, last and middle pivot.
But when I submit with the test list of integers, I have ok for the first one, but failed with the two last ones.
Have you already experimented a code which gives 20x3 good answers with test cases, but failed with the challenge list of integers?
Is there something wrong when I read the integers from the txt file?
Thanks
Best regards
Jerome

input_random_10_16_18.txt: this question test case name
input_random_10_16.txt: Other question test case name

This question test file names has two input sizes instead of one and python3 tester can only read one input size.

Traceback (most recent call last):
  File "tester/python3/tester.py", line 148, in <module>
    test(student_algorithm, test_cases_folder,  *option_values)
  File "tester/python3/tester.py", line 29, in test
    file_type, file_user, file_num, file_size = filename[:-4].split('_')
ValueError: too many values to unpack (expected 4)

expected input is:
[number_of_nodes] [number_of_edges]
and then number_of_edges lines below.

But the line count of edges and [number_of_edges] is not equal.
For example, the first line of input_random_11_40.txt is

40 78

but only 51 edges below.

Will you consider to fix it?
Thank you.

I was checking my algorithm and it seems that this input should have 22 as a result, instead of 12.

The items are the following:

1. w: 1; v: 0
2. w: 3; v: 0
3. w: 1; v: 3
4. w: 2; v: 1
5. w: 3; v: 4
6. w: 0; v: 3
7. w: 2; v: 1
8. w: 1; v: 4
9. w: 2; v: 4
10. w: 3; v: 4

And the capacity of the knapsack is 10. Picking the items [3, 5, 6, 8, 9, 10] (highlighted in the list) you have the following weight used: 1+3+0+1+2+3 = 10 (it fits); and the total value inside the knapsack is: 3+4+3+4+4+4 = 22, better than 12.

I don't know if that's a misspelling when writing the result, or if that's coming from a wrong algorithm used to compute it.

I've tested other files and the result that I get is also different than the one written in the name of the file. But even if my algorithm could be wrong, for this small test-case I solved it by hand and the result makes sense to be bigger than 12.

I am getting error stuck at 20 can you suggest what can be done ? or just what is the correct answer which will be accepted?

For the test cases provide I was getting the wrong answer from my algorithm for question #3 from the data in input_random_32_800.txt and higher.

However, when I ran the data required for the assignment I passed. I wanted to post this as a heads up. I'm not sure whether this is an issue with my algorithm or the test data, but if you are getting some failed cases from the test data I recommend still trying to submit your answer.

I am happy to send you my repo to test if you want to investigate further.

rather than having seperate files, you could just add a new line for the desired output. that way you'd just scan txt files and one by one

https://github.com/beaunus/stanford-algs/blob/master/testCases/course1/assignment2Inversions/input_beaunus_2_4.txt

There are 3 inversions: 3-1, 3-2 and 4-2