kevin-wayne / algs4 Goto Github PK
View Code? Open in Web Editor NEWAlgorithms, 4th edition textbook code and libraries
Home Page: http://algs4.cs.princeton.edu/code/
License: GNU General Public License v3.0
algs4's People
Contributors
Stargazers
Watchers
Forkers
abdullah353 jeremiahmarks nkhuyu agalloch yongliangdu stevenio mcthulhu hstraub rubyfrea techkrish dengdaiyemanren mathslimin bamcdougall snger nawasthi23 greent2008 xiaobingbenyu chinalongganhu pankaj-lakhina an-yun xiaoqiang-yang xiaoqiangyang rivenx robin2234 mukul-1985 yangls06 bala92 mackjoner dinolupo matiomlei danmerz franlisa yimengael amyoxen qingmu keepitss sridhar-newsdistill crazyit gaganjotsingh org-prinstonsam dieface ivmos anoor2css vmaudgalya svetliomihailov zincxenon cnibley yanxutao snailcarl mimibar lavatory gzzing doit05 alannesta fgm-148 kangxh wenaz tntchen ch93 tima04 mkgobaco fy2 tangmj123 ss5211 zyh329 xiaobibibi studyindepth tkarssli charlescliff wendy006 sbhjt12345 yerrarapusuresh poacherbro reversemind wochicaomei alexeylevin tzpbingo lambertyu happyspace suyilearn zjsen668 korayucar vinc456 fsabado shivakrishna-k fubst0318 mblub devinsodhi sjqgithub ravichoudhary33 murat-ch vshallc allianzcortex mumu1221 weekey0 rushidesai1 tedwon taehui parksangkil angellykalgs4's Issues
Error in GrahamScan
Sample points:
- (1, 1)
- (0, 0)
- (0, 5)
- (5, 0)
Result hull is [(1, 1), (0, 5), (0, 0), (5, 0)] instead of [(0, 0), (5, 0), (0, 5)]
Error caused by Arrays.sort(points) in line 73. The class should use Arrays.sort(a) - an array created as a part of defensive copy, not an original array that is not used in calculations.
Inconsistent size() with TST deletion using the put method
As suggested by the api contract of put in TST.java,
If the value is {@code null}, this effectively deletes the key from the symbol table.
However, when calling the put method with null value to delete an exisiting key, the size of the symbol table doesn't decrement by one. Instead, the size just remains the same, which is inconsistent with the number of keys fetched by the orderkeys() method.
public void put(String key, Value val) {
if (key == null) {
throw new IllegalArgumentException("calls put() with null key");
}
if (!contains(key)) n++;
root = put(root, key, val, 0);
}Below is a simple test routine.
@Test
void testTSTDelete()
{
// The whole test routine passes, but something is wrong...
TST<Integer> tst = new TST<>();
tst.put("a", 1);
tst.put("b", 2);
tst.put("c", 3);
assertEquals(3, tst.size());
/*
call the put method with null value to remove b from the TST, as suggested by the
api contract "If the value is {@code null}, this effectively deletes the key from the symbol table."
*/
tst.put("b", null);
// expected tst.size() == 2, but was 3
assertEquals(3, tst.size());
assertNull(tst.get("b"));
int cnt = 0;
for (String key : tst.keys())
{
cnt++;
assertNotEquals("b", key);
System.out.print(key + " ");
}
// only get 2 keys, inconsistent with tst.size() == 3
assertEquals(2, cnt);
}Here's a piece of advice. Just add one line to decrement the size by one to fix the inconsistency : )
public void put(String key, Value val) {
if (key == null) {
throw new IllegalArgumentException("calls put() with null key");
}
if (!contains(key)) n++;
else if(val == null) n--; // delete existing key
root = put(root, key, val, 0);
}Bug In linux instalation instructions
Hi, in this page http://algs4.cs.princeton.edu/linux/ there is a little bug in the linux instalation instructions.
This command sudo chmod 755 checkstyle-{algs4,cos226,algs4} should be sudo chmod 755 checkstyle-{algs4,cos226,coursera}
Sorry if this is the wrong place to report this, but I didn't find any other place. I'm taking the free coursera mooc.
Some programs missing from the repo
Hi Kevin,
I found that some of the programs are present as links in the main site, e.g. http://algs4.cs.princeton.edu/33balanced/SplayBST.java.html but these are not present in this repo. Can we please include all such programs also in the repo, to make this as a complete reference.
Thanks and regards,
Ash
files words3.txt and tiny.txt do not exist
Hi, I am struggling to locate files:
http://algs4.cs.princeton.edu/21sort/words3.txt
http://algs4.cs.princeton.edu/21sort/tiny.txt
which are mentioned in all sorting algorithms, like for example here:
http://algs4.cs.princeton.edu/21elementary/Selection.java.html
No clear what is "repository" of algs4
Hello,
What is the Maven dependency and what is the repository we should to use to build application using Maven?
Could you please provide the appropriate entries we can use in pom.xml in the project?
Best regards
Powazny
Maven central
Hey,
Do you have any plans to publish the algorithms in maven central? Would just make the project more usable...
-niklas
Insertion is not faster than Selection ???
According to the book ๏ผi write the sorting code of Insertion and Selection by myself.According to my test ,i find that the Insertion is not faster 1.7 times than Selection. I checkout my code but it is not error.I am very curious.Why is my data so different from the book.My test data is about 0.8 times. Selection sort faster than Insertion sort ?The following is my resource code and test code:
Insertion sort code
public static void sort(Comparable[] a)
{
int N = a.length;
for(int i = 1; i < N; i++)
{
for(int j = i; j > 0 && less(a[j], a[j-1]) ; j--)
{
exch(a, j, j-1);
}
}
assert isSorted(a);
}
Selection sort code
public static void sort(Comparable[] a)
{
int N = a.length;
for(int i = 0; i < N; i++)
{
int min = i;
for(int j = i + 1; j < N; j++)
{
if(less(a[j], a[min]))
{
min = j;
}
}
exch(a, i, min);
}
assert isSorted(a);
}
test code
public static void main(String[] args)
{ int N = 1000;
int T = 100;
double t1 = timeRandomInput("Insertion", N, T);
double t2 = timeRandomInput("Selection", N, T);
System.out.println(t2/t1);
}
public static double timeRandomInput(String alg, int N, int T)
{
double total = 0.0;
Double[] a = new Double[N];
for(int t = 0; t < T; t++)
{
for(int i = 0; i < N; i++)
a[i] = StdRandom.uniform();
total += time(alg, a);
}
return total;
}
public static double time(String alg, Comparable[] a)
{
Stopwatch timer = new Stopwatch();
if(alg.equals("Insertion")) Insertion.sort(a);
if(alg.equals("Selection")) Selection.sort(a);
return timer.elapsedTime();
}
Separate .java files into packages according
Hi!
I was wondering if it wouldn't be better to separate the .java files into packages corresponding to specific topics (like searching, graphs, etc) instead of having all of them into a single folder/package.
BST ceiling should return null or throw exception?
In the reference implementation, if a ceiling is called on a non-empty BST with an argument that is larger than the maximum element, the BST returns a null reference.
The documentation instead indicates that the operation should throw an exception.
(The operation does throw an exception if the BST is empty.)
A case can be made for both behaviours, but currently the implementation and documentation contradict each other.
Can't figure out exercise 2.3.11
I just can't imagine a situation that will change the time complexity of quick sort to O(n^2) when we change the stopping condition for scanning smaller than a[lo] instead of smaller or equal than a[lo]. And I can not find any answers on the internet.
Build error
Does anyone know how to fix the build error?
โ algs4 git:(master) โ javac BinarySearch.java
BinarySearch.java:94: error: cannot find symbol
In in = new In(args[0])
^
symbol: class In
location: class BinarySearch
BinarySearch.java:94: error: cannot find symbol
In in = new In(args[0]);
^
symbol: class In
location: class BinarySearch
BinarySearch.java:101: error: cannot find symbol
while (!StdIn.isEmpty()) {
^
symbol: variable StdIn
location: class BinarySearch
BinarySearch.java:102: error: cannot find symbol
int key = StdIn.readInt();
^
symbol: variable StdIn
location: class BinarySearch
BinarySearch.java:104: error: cannot find symbol
StdOut.println(key);
^
symbol: variable StdOut
location: class BinarySearch
5 errors
[improvement] EdgeWeightedDigraph search for paths by number of nodes or
First of all thanks for this work, brilliant piece for learning curve in not only graph theory. I had an idea to improve EdgeWeightedDigraph class by obtaining Paths by:
- number of nodes in path: can be equalTo, GT, G, LT, L types
- node or node list
What do you think?
maven and gradle project builder
Hi
I spent a bit of time and almost learned how to use these. But I did want to ask if there is an update I may have missed. I do not want to build a jar file from any of the source, I just want to compile some of the source and run them as I read your book. Is there a quickstart guide that worked for others perhaps that you could share with me? I ask b/c I tried to run Javac BinarySearch.java and got an error about missing main or something. So I am wondering if I should do something differently.
Regards-
Sam
Bintray Maven repo out of date
The current version in the Bintray repo is 1.0.3. It's out of date, specifically missing some updates to Picture.java that were committed back in September 2017.
Outdated doc comment for BinarySearch
The class doc comment for BinarySearch still references the rank operation, but rank has been deprecated in favor of indexOf.
The rank operations takes logarithmic time in the worst case.
EdgeWeightedDigraph.java wrong data file url
in the top comment section of EdgeWeightedDigraph.java, the url of data files are wrong.
for example, https://algs4.cs.princeton.edu/44st/tinyEWD.txt will lead to file not found page
the correct url, after a google search, turns out to be https://algs4.cs.princeton.edu/44sp/tinyEWD.txt
so 44st should be changed to 44sp in the url
Ignore this issue
No content
`StdRandom::geometric(double p)` allows casting Infinity to an int
StdRandom::geometric(double p) allows casting Infinity to an int.
The potential issue occurs when p = 1.0. This may or may not be what you want, but it seems dicey even if the maximum integer is the closest approximation.
in README-MAVEN.md
- backslash with apostrophe ,like in c:\some-highlited-maven-dir , must be
replaced by 2 backslashes and apostrophe \' , otherwise text is corrupted
this error can be present in all explanations about windows.
in linux we have forward slash.
- different lines - one under another - visible as single line in resulting text.
to really separate lines, you need 2-ce press return at the end of the line.
It is important in text, where command line params set, PATH, M2_HOME, etc... commands must be separated.
Is there a bug in BST.java?
I am just wondering is this a bug or not for the BST.java:
At the line 147, the comments said "@throws NullPointerException if key is null". But it is possible to use the public void put(Key key, Value val) method to put null key when the root of the tree is still null without throwing any exceptions.
But later operations on the BST such as get, delete etc. will throw NullPointerException because we have constructed a root node with null key.
RedBlackBST delete problem
If right child of node to be deleted is null and the left child is not null, the whole left branch will be deleted. Instead, the method should return the left branch.
diameter of an undirected graph
Is there a methode to calculate the diameter of a Graph?
QuickX.sort(Comparable[] a, int lo, int hi)
Hey,
Could it be possible to make QuickX.sort(Comparable[] a, int lo, int hi) public instead of having it private?
Just by looking at the code I don't see any reason why it couldn't be public, but perhaps I am missing something here?
-niklas
Problem in SymbolGraph
It seems that the main methode is stuck in infinit loop in SymbolGraph class. When I execute the program, it never finishes.
Shouldn't rank need to be updated here
algs4/src/main/java/edu/princeton/cs/algs4/UF.java
Lines 164 to 165 in 922bb05
Typo in comment: a tournament is not a DAG
algs4/src/main/java/edu/princeton/cs/algs4/DigraphGenerator.java
Lines 141 to 143 in 97bddfb
Thanks!
Michaรซl
Publish algs4.jar to jCenter or maven centrual repositray
Rounding errors in AssignmentProblem
When using AssignmentProblem on the attached data, there are problems with rounding residuals, leading to negative values returned by reducedCost.
The below test case shows this in the form of the smallest case that happens (N=4) on one of my specific matrix.
When calculating the solution for the whole matrix, without assertions, even weirder things happen, as then at some point DijkstraSP's constructor complains about negative edge โ a closer look reveals it's "negative zero" value, so this might be potentially another source of bugs.
I suspect the two or more same cost values in the matrix, although those should also trigger an error for N=3.
import org.junit.Before;
import org.junit.Test;
import edu.princeton.cs.algs4.AssignmentProblem;
public class TestNegativeZeroAssignment {
/*
5.1155, 4.99745, 4.99745, 4.99745, 4.99745, 4.99745, 4.99745, 4.99745, 4.99745, 4.99745, 4.99745, 4.99745, 4.99745, 4.99745, 4.99745, 4.99745, 4.99745, 4.99745, 4.99745, 5.1155, 5.1155, 5.1155, 5.1155, 5.1155
168.2473, 164.36467, 164.36467, 164.36467, 164.36467, 164.36467, 164.36467, 164.36467, 164.36467, 164.36467, 164.36467, 164.36467, 164.36467, 164.36467, 164.36467, 164.36467, 164.36467, 164.36467, 164.36467, 168.2473, 168.2473, 168.2473, 168.2473, 168.2473
238.9088, 233.39552, 233.39552, 233.39552, 233.39552, 233.39552, 233.39552, 233.39552, 233.39552, 233.39552, 233.39552, 233.39552, 233.39552, 233.39552, 233.39552, 233.39552, 233.39552, 233.39552, 233.39552, 238.9088, 238.9088, 238.9088, 238.9088, 238.9088
573.4521000000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 573.4521000000001, 573.4521000000001, 573.4521000000001, 573.4521000000001, 573.4521000000001
552.9472000000001, 540.18688, 540.18688, 540.18688, 540.18688, 540.18688, 540.18688, 540.18688, 540.18688, 540.18688, 540.18688, 540.18688, 540.18688, 540.18688, 540.18688, 540.18688, 540.18688, 540.18688, 540.18688, 552.9472000000001, 552.9472000000001, 552.9472000000001, 552.9472000000001, 552.9472000000001
498.0872, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 498.0872, 498.0872, 498.0872, 498.0872, 498.0872
564.6784000000001, 551.64736, 551.64736, 551.64736, 551.64736, 551.64736, 551.64736, 551.64736, 551.64736, 551.64736, 551.64736, 551.64736, 551.64736, 551.64736, 551.64736, 551.64736, 551.64736, 551.64736, 551.64736, 564.6784000000001, 564.6784000000001, 564.6784000000001, 564.6784000000001, 564.6784000000001
338.6162, 330.80198, 330.80198, 330.80198, 330.80198, 330.80198, 330.80198, 330.80198, 330.80198, 330.80198, 330.80198, 330.80198, 330.80198, 330.80198, 330.80198, 330.80198, 330.80198, 330.80198, 330.80198, 338.6162, 338.6162, 338.6162, 338.6162, 338.6162
502.53970000000004, 490.94263, 490.94263, 490.94263, 490.94263, 490.94263, 490.94263, 490.94263, 490.94263, 490.94263, 490.94263, 490.94263, 490.94263, 490.94263, 490.94263, 490.94263, 490.94263, 490.94263, 490.94263, 502.53970000000004, 502.53970000000004, 502.53970000000004, 502.53970000000004, 502.53970000000004
721.6495, 704.99605, 704.99605, 704.99605, 704.99605, 704.99605, 704.99605, 704.99605, 704.99605, 704.99605, 704.99605, 704.99605, 704.99605, 704.99605, 704.99605, 704.99605, 704.99605, 704.99605, 704.99605, 721.6495, 721.6495, 721.6495, 721.6495, 721.6495
692.3683000000001, 676.39057, 676.39057, 676.39057, 676.39057, 676.39057, 676.39057, 676.39057, 676.39057, 676.39057, 676.39057, 676.39057, 676.39057, 676.39057, 676.39057, 676.39057, 676.39057, 676.39057, 676.39057, 692.3683000000001, 692.3683000000001, 692.3683000000001, 692.3683000000001, 692.3683000000001
615.3081999999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 615.3081999999999, 615.3081999999999, 615.3081999999999, 615.3081999999999, 615.3081999999999
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
*/
long[][] bits = new long[][] {
new long[] { 4617445559400841347L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617445559400841347L, 4617445559400841347L, 4617445559400841347L, 4617445559400841347L, 4617445559400841347L },
new long[] { 4640123692170381728L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4640123692170381728L, 4640123692170381728L, 4640123692170381728L, 4640123692170381728L, 4640123692170381728L },
new long[] { 4642609872678736731L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642609872678736731L, 4642609872678736731L, 4642609872678736731L, 4642609872678736731L, 4642609872678736731L },
new long[] { 4648255353834361901L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648255353834361901L, 4648255353834361901L, 4648255353834361901L, 4648255353834361901L, 4648255353834361901L },
new long[] { 4648074990826550828L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4648074990826550828L, 4648074990826550828L, 4648074990826550828L, 4648074990826550828L, 4648074990826550828L },
new long[] { 4647470058880353121L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647470058880353121L, 4647470058880353121L, 4647470058880353121L, 4647470058880353121L, 4647470058880353121L },
new long[] { 4648178179553012955L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648178179553012955L, 4648178179553012955L, 4648178179553012955L, 4648178179553012955L, 4648178179553012955L },
new long[] { 4644664615379664057L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644664615379664057L, 4644664615379664057L, 4644664615379664057L, 4644664615379664057L, 4644664615379664057L },
new long[] { 4647548388088715884L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647548388088715884L, 4647548388088715884L, 4647548388088715884L, 4647548388088715884L, 4647548388088715884L },
new long[] { 4649558911950411268L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649558911950411268L, 4649558911950411268L, 4649558911950411268L, 4649558911950411268L, 4649558911950411268L },
new long[] { 4649301351791409392L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649301351791409392L, 4649301351791409392L, 4649301351791409392L, 4649301351791409392L, 4649301351791409392L },
new long[] { 4648623523983508740L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648623523983508740L, 4648623523983508740L, 4648623523983508740L, 4648623523983508740L, 4648623523983508740L },
new long[] { 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L },
new long[] { 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L },
new long[] { 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L },
new long[] { 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L },
new long[] { 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L },
new long[] { 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L },
new long[] { 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L },
new long[] { 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L },
new long[] { 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L },
new long[] { 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L },
new long[] { 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L },
new long[] { 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L }
};
double[][] weights;
// this N is the minimal that trigger an exception:
// java.lang.AssertionError: Dual variables are not feasible
// at edu.princeton.cs.algs4.AssignmentProblem.<init>(AssignmentProblem.java:80)
int maxN = 4;
@Before
public void makeWeights() {
int N = Math.min(maxN, bits.length);
weights = new double[N][];
for (int i = 0; i < N; ++i) {
weights[i] = new double[N];
for (int j = 0; j < N; ++j) {
weights[i][j] = Double.longBitsToDouble(bits[i][j]);
}
}
}
@Test
public void testAssignmentProblem() {
AssignmentProblem ap = new AssignmentProblem(weights);
}
}
Incorrect instructions in Average.java
The comment in Average.java for how to run it says:
* % java Average
However, it's in a package and should be:
* java edu.princeton.cs.algs4.Average
BTree, after inserting is not updating value to null
Before, when adding a sequence of (K: 1, V: 10), (3, 30), (8, 80), (7, 70), (5, 50), (6, 60), on rotating Node value is not set to null, so the parent key of 7, has a value of 50 (but should be null.
Node u = insert(h.children[j++].next, key, val, ht - 1);
if (u == null) {
return null;
}
t.key = u.children[0].key;
t.val = null; // fix
t.next = u;
algs4/BTree
{
"root": {
"m": 3,
"children": [
{
"key": 1,
"next": {
"m": 2,
"children": [
{
"key": 1,
"val": 10
},
{
"key": 3,
"val": 30
},
{
"key": 4,
"val": 40
},
{
"key": 8,
"val": 80
}
]
}
},
{
"key": 4,
"next": {
"m": 3,
"children": [
{
"key": 4,
"val": 40
},
{
"key": 5,
"val": 50
},
{
"key": 6,
"val": 60
},
{
"key": 8,
"val": 80
}
]
}
},
{
"key": 7,
"val": 50,
"next": {
"m": 2,
"children": [
{
"key": 7,
"val": 70
},
{
"key": 8,
"val": 80
},
null,
null
]
}
},
null
]
},
"height": 1,
"n": 7
}
and after fix result
{
"root": {
"m": 3,
"children": [
{
"key": 1,
"next": {
"m": 2,
"children": [
{
"key": 1,
"val": 10
},
{
"key": 3,
"val": 30
},
{
"key": 4,
"val": 40
},
{
"key": 8,
"val": 80
}
]
}
},
{
"key": 4,
"next": {
"m": 3,
"children": [
{
"key": 4,
"val": 40
},
{
"key": 5,
"val": 50
},
{
"key": 6,
"val": 60
},
{
"key": 8,
"val": 80
}
]
}
},
{
"key": 7,
"next": {
"m": 2,
"children": [
{
"key": 7,
"val": 70
},
{
"key": 8,
"val": 80
},
null,
null
]
}
},
null
]
},
"height": 1,
"n": 7
}
What is the so called whitelist in exercise 1.1.23?
I am confused on what the whitelist is..
Please point me in the right direction on that exercise, thanks very much.
StdRandom.java, gaussian( ), polar form, closed interval [-1,+1]
Excuse me for being a little pedantic...
In the function gaussian( ):
uniform(-1.0, 1.0) is called to generate the uniformly distributed values of x and y.
The polar form of the Box-Muller transform requires x and y to be in the closed interval [โ1.0, +1.0].
Whereas, the output of uniform(-1.0, 1.0) is half-open interval [-1.0, +1.0).
StdDraw.java has a bug in method init() and createMenuBar()
it has errors in init() method
draw.addMouseListener(std);
draw.addMouseMotionListener(std);
frame.addKeyListener(std);
std is not the type what the method need.
i use jdk1.8
typos in java doc
here:
algs4/src/main/java/edu/princeton/cs/algs4/ThreeSum.java
there is a typo in line 3
- Execution: java ThreeSum input.txt
Which should be - Execution: java ThreeSum < input.txt
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0
I have successfully imported the source code of algs4-master into my own eclipse project, also called algs4-master, but why do I get errors after running us-> Java Application in eclipse?
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0
at edu.princeton.cs.algs4.BinarySearch.main (BinarySearch.java:94)
a small mistake in StdIn.readAll()
the original code in stdin.java
// used to read the entire input
223 private static final Pattern EVERYTHING_PATTERN = Pattern.compile("\A");
but the function stdin.readall() doesn't work.
so i change the pattern to "\z"
it works.
.gitignore
add in .gitignore this entry
to avoid build results in git
*/target/**
Target - is maven's result folder.
There you can find jar and docs (if generated).
Target never enters git.
Is it a mistake inside StdRandom.shuffle
Hi Kevin,
I am looking at shuffle function inside StdRandom.java, more specifically, the line 520:
/**
* Rearranges the elements of the specified subarray in uniformly random order.
*
* @param a the array to shuffle
* @param lo the left endpoint (inclusive)
* @param hi the right endpoint (exclusive)
* @throws IllegalArgumentException if {@code a} is {@code null}
* @throws IndexOutOfBoundsException unless {@code (0 <= lo) && (lo < hi) && (hi <= a.length)}
*/
public static void shuffle(int[] a, int lo, int hi) {
if (a == null) throw new IllegalArgumentException("argument array is null");
if (lo < 0 || lo >= hi || hi > a.length) {
throw new IndexOutOfBoundsException("invalid subarray range: [" + lo + ", " + hi + ")");
}
for (int i = lo; i < hi; i++) {
int r = i + uniform(hi-i+1); // between i and hi
int temp = a[i];
a[i] = a[r];
a[r] = temp;
}
}
It is said hi is exclusive so that i think
int r = i + uniform(hi-i+1); // between i and hi
should be
int r = i + uniform(hi-i); // between i and hi-1
because if r equals hi, a[r] may trigger out of IndexOutOfBoundsException.
Best wishes,
By Linbo
algs4.jar can't work
Hi kevin,do you mind my asking you some questions?
this is my computer config.
macOS 10.13.1 zsh idea
recently I bought book to learning Algorithms, 4th.I download algs4.jar info a folder,config CLASSPATH like this
In Idea project,I add jar into dependency
and here is my project tree
when I use javac to compile UFTest.java ,no error occurred.but when I use terminal run java commend it only cursor blink no error occurred also.
Do you know why?
regarding "unit testing": suggest move to JUnit or TestNG rather than main method invocation
Currently, in assignments and source code, tests are made via calling methods in the main method, this require the user to check input, output manually and is not that efficient.
I highly recommend that those unit tests can be written in JUnit or TestNG, which is more close to the meaning of unit tests, while providing convenience to students who are doing programming assignments.
PS: I just enrolled algorithms-part1 at coursera and it's awesome. Thank you for providing such a great online free course.
For example, for the percolation I just finished, suppose we prepare test cases like this(you can use them freely and correct if I made some mistake. It spent me some time man):
greeting57.txt,2522,false
heart25.txt,352,false
input1-no.txt,0,false
input1.txt,1,true
input10-no.txt,55,false
input10.txt,56,true
input2-no.txt,2,false
input2.txt,3,true
input20.txt,250,true
input3.txt,6,true
input4.txt,8,true
input5.txt,25,true
input50.txt,1412,true
input6.txt,18,true
input7.txt,16,true
input8-dups.txt,34,true
input8-no.txt,33,false
input8.txt,34,true
java60.txt,578,true
jerry47.txt,1476,true
sedgewick60.txt,2408,true
snake101.txt,5101,true
snake13.txt,85,true
wayne98.txt,5079,true
And I wrote unit test like this, which is helpful while I improve my coding to meet the grade requirement:
@Test
public void runAll() {
In in = new In(this.getClass().getResource("/percolation-test-cases.txt"));
int failed = 0;
while (!in.isEmpty()) {
String line = in.readLine();
String[] array = line.split(",");
Percolation perc = this.from(array[0]);
try {
assertEquals(perc.numberOfOpenSites(), Integer.parseInt(array[1]));
assertEquals(perc.percolates(), Boolean.parseBoolean(array[2]));
} catch (AssertionError e) {
System.err.println(line + " -> " + perc.numberOfOpenSites() + "," + perc.percolates());
failed++;
}
}
if (failed > 0) {
throw new AssertionError(failed + " test cases failed!");
}
}
@Test
public void isFull() {
Percolation perc = new Percolation(3);
perc.open(1, 1);
perc.open(3, 1);
assertFalse(perc.isFull(3, 1));
perc.open(1, 3);
perc.open(3, 3);
assertFalse(perc.isFull(3, 3));
perc.open(2, 3);
assertTrue(perc.isFull(3, 3));
assertFalse(perc.isFull(3, 1));
}Rename parameters for intervals.
For 1D and 2D-Intervals, I suggest renaming xleft/xright/yleft/yright to xmin/xmax/ymin/ymax respectively.
The former terms are suggestive of a particular coordinate system, while the latter terms are not.
can't find 1Mints.txt
I downloaded the algs4-data.zip from https://algs4.cs.princeton.edu/code/, but I did not find the 1Mints.txt. help~~
DijkstraSP issue
I am confusing about the judgement of consitency of edgeTo[v] and distTo[v]
Here is the code:
private boolean check(EdgeWeightedDigraph G, int s) {
// check that edge weights are nonnegative
for (DirectedEdge e : G.edges()) {
if (e.weight() < 0) {
System.err.println("negative edge weight detected");
return false;
}
}
// check that distTo[v] and edgeTo[v] are consistent
if (distTo[s] != 0.0 || edgeTo[s] != null) {
System.err.println("distTo[s] and edgeTo[s] inconsistent");
return false;
}
for (int v = 0; v < G.V(); v++) {
if (v == s) continue;
if (edgeTo[v] == null && distTo[v] != Double.POSITIVE_INFINITY) {
System.err.println("distTo[] and edgeTo[] inconsistent");
return false;
}
}
// check that all edges e = v->w satisfy distTo[w] <= distTo[v] + e.weight()
for (int v = 0; v < G.V(); v++) {
for (DirectedEdge e : G.adj(v)) {
int w = e.to();
if (distTo[v] + e.weight() < distTo[w]) {
System.err.println("edge " + e + " not relaxed");
return false;
}
}
}
// check that all edges e = v->w on SPT satisfy distTo[w] == distTo[v] + e.weight()
for (int w = 0; w < G.V(); w++) {
if (edgeTo[w] == null) continue;
DirectedEdge e = edgeTo[w];
int v = e.from();
if (w != e.to()) return false;
if (distTo[v] + e.weight() != distTo[w]) {
System.err.println("edge " + e + " on shortest path not tight");
return false;
}
}
return true;
}
I think if (edgeTo[v] == null && distTo[v] != Double.POSITIVE_INFINITY) should be
if (edgeTo[v] == null && distTo[v] == Double.POSITIVE_INFINITY)
// check that distTo[v] and edgeTo[v] are consistent
if (distTo[s] != 0.0 || edgeTo[s] != null) {
System.err.println("distTo[s] and edgeTo[s] inconsistent");
return false;
}
for (int v = 0; v < G.V(); v++) {
if (v == s) continue;
if (edgeTo[v] == null && distTo[v] != Double.POSITIVE_INFINITY) {
System.err.println("distTo[] and edgeTo[] inconsistent");
return false;
}
}
A problem occurred when run build file build.gradle
The error result is :
Build file '/var/java-projects/algs4/build.gradle' line: 81
A problem occurred evaluating root project 'algs4'.
> Cannot add task 'wrapper' as a task with that name already exists.
One edge is enough for self loop edges
Both EulerianPath.java and EulerianCycle.java have the self-loop handling code:
// careful with self loops
if (v == w) {
if (selfLoops % 2 == 0) {
Edge e = new Edge(v, w);
adj[v].enqueue(e);
adj[w].enqueue(e);
}
selfLoops++;
}Since an edge can only be used once, adj[w].enqueue(e); can be safely removed.
BTree issues
Hi,
I think I have found a few problems with the BTree implementation.
-
Not sure if this is really a problem, but the same key can be inserted multiple times;
-
If the same key is inserted more than M-1 times, there will be a split, and only the M/2 keys of the new node will be accessible, while the other ones will be forever inaccessible;
-
When a slipt occurs, the old node keeps the keys that were sent to the new node, even though they now inaccessible in that node; again, this may not be a problem;
-
When a key is removed, the method still increments the size counter, instead of decreasing it;
Since I am using the this BTree implementation, I have fixed these problems on my side.
where are largeW.txt, largeT.txt, tinyW.text tintT.txt on page 9 and 47
It is said
we provide on the book-site the files largeW.txt (1 million integers) and largeT.txt (10 million integers).
But I could not find where they are.
Anyone knows that?
BreadthFirstPath and farthest vertex
can BreadthFirstPath give us the farthest vertex from the source vertex?
Java algorithms?
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. ๐๐๐
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google โค๏ธ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.