Algorithms(using Java) 4th Edition

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

Algorithms (4th Edition)

Robert Sedgewick (Author), Kevin Wayne (Author)

This fourth edition of Robert Sedgewick and Kevin Wayne’s Algorithms is the leading textbook on algorithms today and is widely used in colleges and universities worldwide. This book surveys the most important computer algorithms currently in use and provides a full treatment of data structures and algorithms for sorting, searching, graph processing, and string processing -- including fifty algorithms every programmer should know. In this edition, new Java implementations are written in an accessible modular programming style, where all of the code is exposed to the reader and ready to use.

The algorithms in this book represent a body of knowledge developed over the last 50 years that has become indispensable, not just for professional programmers and computer science students but for any student with interests in science, mathematics, and engineering, not to mention students who use computation in the liberal arts.

The companion web site, algs4.cs.princeton.edu contains

An online synopsisFull Java implementationsTest dataExercises and answersDynamic visualizationsLecture slidesProgramming assignments with checklistsLinks to related material

The MOOC related to this book is accessible via the "Online Course" link at algs4.cs.princeton.edu. The course offers more than 100 video lecture segments that are integrated with the text, extensive online assessments, and the large-scale discussion forums that have proven so valuable. Offered each fall and spring, this course regularly attracts tens of thousands of registrants.

Robert Sedgewick and Kevin Wayne are developing a modern approach to disseminating knowledge that fully embraces technology, enabling people all around the world to discover new ways of learning and teaching. By integrating their textbook, online content, and MOOC, all at the state of the art, they have built a unique resource that greatly expands the breadth and depth of the educational experience.

Product Details

• Hardcover: 992 pages
• Publisher: Addison-Wesley Professional; 4 edition (March 9 2011)
• Language: English
• ISBN-10: 032157351X
• ISBN-13: 978-0321573513
• Product Dimensions: 19 x 3.8 x 23.4 cm
  

http://algs4.cs.princeton.edu/code/

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏1 回帖

关键词：Algorithms Algorithm Edition editio dition currently important including searching computer

1. PolynomialRegression.java
   
2. 
   
3. 
   
4. Below is the syntax highlighted version of PolynomialRegression.java from § Algorithms.   Here is the Javadoc.
   
5. 
   
6. 
   
7. /*************************************************************************
   
8. *  Compilation:  javac -cp .:jama.jar PolynomialRegression.java
   
9. *  Execution:    java  -cp .:jama.jar PolynomialRegression
   
10. *  Dependencies: jama.jar StdOut.java
    
11. *
    
12. *  % java -cp .:jama.jar PolynomialRegression
    
13. *  0.01 N^3 + -1.64 N^2 + 168.92 N + -2113.73 (R^2 = 0.997)
    
14. *
    
15. *************************************************************************/
    
16. 
    
17. import Jama.Matrix;
    
18. import Jama.QRDecomposition;
    
19. 
    
20. /**
    
21. *  The <tt>PolynomialRegression</tt> class performs a polynomial regression
    
22. *  on an set of <em>N</em> data points (<em>y_i</em>, <em>x_i</em>).
    
23. *  That is, it fits a polynomial
    
24. *  <em>y</em> = β₀ +  β₁ <em>x</em> +
    
25. *  β₂ <em>x</em>² + ... +
    
26. *  β_<em>d</em> <em>x</em>^<em>d</em>
    
27. *  (where <em>y</em> is the response variable, <em>x</em> is the predictor variable,
    
28. *  and the β_<em>i</em> are the regression coefficients)
    
29. *  that minimizes the sum of squared residuals of the multiple regression model.
    
30. *  It also computes associated the coefficient of determination <em>R</em>².
    
31. *  <p>
    
32. *  This implementation performs a QR-decomposition of the underlying
    
33. *  Vandermonde matrix, so it is not the fastest or most numerically
    
34. *  stable way to perform the polynomial regression.
    
35. *
    
36. *  @author Robert Sedgewick
    
37. *  @author Kevin Wayne
    
38. */
    
39. public class PolynomialRegression {
    
40.     private final int N;         // number of observations
    
41.     private final int degree;    // degree of the polynomial regression
    
42.     private final Matrix beta;   // the polynomial regression coefficients
    
43.     private double SSE;          // sum of squares due to error
    
44.     private double SST;          // total sum of squares
    
45. 
    
46.   /**
    
47.      * Performs a polynomial reggression on the data points <tt>(y[i], x[i])</tt>.
    
48.      * @param x the values of the predictor variable
    
49.      * @param y the corresponding values of the response variable
    
50.      * @param degree the degree of the polynomial to fit
    
51.      * @throws java.lang.IllegalArgumentException if the lengths of the two arrays are not equal
    
52.      */
    
53.     public PolynomialRegression(double[] x, double[] y, int degree) {
    
54.         this.degree = degree;
    
55.         N = x.length;
    
56. 
    
57.         // build Vandermonde matrix
    
58.         double[][] vandermonde = new double[N][degree+1];
    
59.         for (int i = 0; i < N; i++) {
    
60.             for (int j = 0; j <= degree; j++) {
    
61.                 vandermonde[i][j] = Math.pow(x[i], j);
    
62.             }
    
63.         }
    
64.         Matrix X = new Matrix(vandermonde);
    
65. 
    
66.         // create matrix from vector
    
67.         Matrix Y = new Matrix(y, N);
    
68. 
    
69.         // find least squares solution
    
70.         QRDecomposition qr = new QRDecomposition(X);
    
71.         beta = qr.solve(Y);
    
72. 
    
73. 
    
74.         // mean of y[] values
    
75.         double sum = 0.0;
    
76.         for (int i = 0; i < N; i++)
    
77.             sum += y[i];
    
78.         double mean = sum / N;
    
79. 
    
80.         // total variation to be accounted for
    
81.         for (int i = 0; i < N; i++) {
    
82.             double dev = y[i] - mean;
    
83.             SST += dev*dev;
    
84.         }
    
85. 
    
86.         // variation not accounted for
    
87.         Matrix residuals = X.times(beta).minus(Y);
    
88.         SSE = residuals.norm2() * residuals.norm2();
    
89.     }
    
90. 
    
91.    /**
    
92.      * Returns the <tt>j</tt>th regression coefficient
    
93.      * @return the <tt>j</tt>th regression coefficient
    
94.      */
    
95.     public double beta(int j) {
    
96.         return beta.get(j, 0);
    
97.     }
    
98. 
    
99.    /**
    
100.      * Returns the degree of the polynomial to fit
     
101.      * @return the degree of the polynomial to fit
     
102.      */
     
103.     public int degree() {
     
104.         return degree;
     
105.     }
     
106. 
     
107.    /**
     
108.      * Returns the coefficient of determination <em>R</em>².
     
109.      * @return the coefficient of determination <em>R</em>², which is a real number between 0 and 1
     
110.      */
     
111.     public double R2() {
     
112.         if (SST == 0.0) return 1.0;   // constant function
     
113.         return 1.0 - SSE/SST;
     
114.     }
     
115. 
     
116.    /**
     
117.      * Returns the expected response <tt>y</tt> given the value of the predictor
     
118.      *    variable <tt>x</tt>.
     
119.      * @param x the value of the predictor variable
     
120.      * @return the expected response <tt>y</tt> given the value of the predictor
     
121.      *    variable <tt>x</tt>
     
122.      */
     
123.     public double predict(double x) {
     
124.         // horner's method
     
125.         double y = 0.0;
     
126.         for (int j = degree; j >= 0; j--)
     
127.             y = beta(j) + (x * y);
     
128.         return y;
     
129.     }
     
130. 
     
131.    /**
     
132.      * Returns a string representation of the polynomial regression model.
     
133.      * @return a string representation of the polynomial regression model,
     
134.      *   including the best-fit polynomial and the coefficient of determination <em>R</em>²
     
135.      */
     
136.     public String toString() {
     
137.         String s = "";
     
138.         int j = degree;
     
139. 
     
140.         // ignoring leading zero coefficients
     
141.         while (j >= 0 && Math.abs(beta(j)) < 1E-5)
     
142.             j--;
     
143. 
     
144.         // create remaining terms
     
145.         for (j = j; j >= 0; j--) {
     
146.             if      (j == 0) s += String.format("%.2f ", beta(j));
     
147.             else if (j == 1) s += String.format("%.2f N + ", beta(j));
     
148.             else             s += String.format("%.2f N^%d + ", beta(j), j);
     
149.         }
     
150.         return s + "  (R^2 = " + String.format("%.3f", R2()) + ")";
     
151.     }
     
152. 
     
153.     public static void main(String[] args) {
     
154.         double[] x = { 10, 20, 40, 80, 160, 200 };
     
155.         double[] y = { 100, 350, 1500, 6700, 20160, 40000 };
     
156.         PolynomialRegression regression = new PolynomialRegression(x, y, 3);
     
157.         StdOut.println(regression);
     
158.     }
     
159. }
     
160. 
     
161. 
     
162. 
     
163. Copyright © 2002–2010, Robert Sedgewick and Kevin Wayne.
     
164. Last updated: Sat Oct 5 06:29:24 EDT 2013.

复制代码

1. Bag.java
   
2. 
   
3. 
   
4. Below is the syntax highlighted version of Bag.java from § Algorithms.   Here is the Javadoc.
   
5. 
   
6. 
   
7. /*************************************************************************
   
8. *  Compilation:  javac Bag.java
   
9. *  Execution:    java Bag < input.txt
   
10. *
    
11. *  A generic bag or multiset, implemented using a singly-linked list.
    
12. *
    
13. *  % more tobe.txt
    
14. *  to be or not to - be - - that - - - is
    
15. *
    
16. *  % java Bag < tobe.txt
    
17. *  size of bag = 14
    
18. *  is
    
19. *  -
    
20. *  -
    
21. *  -
    
22. *  that
    
23. *  -
    
24. *  -
    
25. *  be
    
26. *  -
    
27. *  to
    
28. *  not
    
29. *  or
    
30. *  be
    
31. *  to
    
32. *
    
33. *************************************************************************/
    
34. 
    
35. import java.util.Iterator;
    
36. import java.util.NoSuchElementException;
    
37. 
    
38. /**
    
39. *  The <tt>Bag</tt> class represents a bag (or multiset) of
    
40. *  generic items. It supports insertion and iterating over the
    
41. *  items in arbitrary order.
    
42. *  <p>
    
43. *  This implementation uses a singly-linked list with a static nested class Node.
    
44. *  See {@link LinkedBag} for the version from the
    
45. *  textbook that uses a non-static nested class.
    
46. *  The <em>add</em>, <em>isEmpty</em>, and <em>size</em> operations
    
47. *  take constant time. Iteration takes time proportional to the number of items.
    
48. *  <p>
    
49. *  For additional documentation, see <a href="http://algs4.cs.princeton.edu/13stacks">Section 1.3</a> of
    
50. *  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
    
51. *
    
52. *  @author Robert Sedgewick
    
53. *  @author Kevin Wayne
    
54. */
    
55. public class Bag<Item> implements Iterable<Item> {
    
56.     private int N;               // number of elements in bag
    
57.     private Node<Item> first;    // beginning of bag
    
58. 
    
59.     // helper linked list class
    
60.     private static class Node<Item> {
    
61.         private Item item;
    
62.         private Node<Item> next;
    
63.     }
    
64. 
    
65.     /**
    
66.      * Initializes an empty bag.
    
67.      */
    
68.     public Bag() {
    
69.         first = null;
    
70.         N = 0;
    
71.     }
    
72. 
    
73.     /**
    
74.      * Is this bag empty?
    
75.      * @return true if this bag is empty; false otherwise
    
76.      */
    
77.     public boolean isEmpty() {
    
78.         return first == null;
    
79.     }
    
80. 
    
81.     /**
    
82.      * Returns the number of items in this bag.
    
83.      * @return the number of items in this bag
    
84.      */
    
85.     public int size() {
    
86.         return N;
    
87.     }
    
88. 
    
89.     /**
    
90.      * Adds the item to this bag.
    
91.      * @param item the item to add to this bag
    
92.      */
    
93.     public void add(Item item) {
    
94.         Node<Item> oldfirst = first;
    
95.         first = new Node<Item>();
    
96.         first.item = item;
    
97.         first.next = oldfirst;
    
98.         N++;
    
99.     }
    
100. 
     
101. 
     
102.     /**
     
103.      * Returns an iterator that iterates over the items in the bag in arbitrary order.
     
104.      * @return an iterator that iterates over the items in the bag in arbitrary order
     
105.      */
     
106.     public Iterator<Item> iterator()  {
     
107.         return new ListIterator<Item>(first);  
     
108.     }
     
109. 
     
110.     // an iterator, doesn't implement remove() since it's optional
     
111.     private class ListIterator<Item> implements Iterator<Item> {
     
112.         private Node<Item> current;
     
113. 
     
114.         public ListIterator(Node<Item> first) {
     
115.             current = first;
     
116.         }
     
117. 
     
118.         public boolean hasNext()  { return current != null;                     }
     
119.         public void remove()      { throw new UnsupportedOperationException();  }
     
120. 
     
121.         public Item next() {
     
122.             if (!hasNext()) throw new NoSuchElementException();
     
123.             Item item = current.item;
     
124.             current = current.next;
     
125.             return item;
     
126.         }
     
127.     }
     
128. 
     
129.     /**
     
130.      * Unit tests the <tt>Bag</tt> data type.
     
131.      */
     
132.     public static void main(String[] args) {
     
133.         Bag<String> bag = new Bag<String>();
     
134.         while (!StdIn.isEmpty()) {
     
135.             String item = StdIn.readString();
     
136.             bag.add(item);
     
137.         }
     
138. 
     
139.         StdOut.println("size of bag = " + bag.size());
     
140.         for (String s : bag) {
     
141.             StdOut.println(s);
     
142.         }
     
143.     }
     
144. 
     
145. 
     
146. }
     
147. 
     
148. 
     
149. Copyright © 2002–2010, Robert Sedgewick and Kevin Wayne.
     
150. Last updated: Tue Mar 25 04:52:35 EDT 2014.

复制代码

1. BTree.java
   
2. 
   
3. 
   
4. Below is the syntax highlighted version of BTree.java from §6.2 B-trees.
   
5. 
   
6. 
   
7. /*************************************************************************
   
8. *  Compilation:  javac BTree.java
   
9. *  Execution:    java BTree
   
10. *
    
11. *  B-tree.
    
12. *
    
13. *  Limitations
    
14. *  -----------
    
15. *   -  Assumes M is even and M >= 4
    
16. *   -  should b be an array of children or list (it would help with
    
17. *      casting to make it a list)
    
18. *
    
19. *************************************************************************/
    
20. 
    
21. 
    
22. public class BTree<Key extends Comparable<Key>, Value>  {
    
23.     private static final int M = 4;    // max children per B-tree node = M-1
    
24. 
    
25.     private Node root;             // root of the B-tree
    
26.     private int HT;                // height of the B-tree
    
27.     private int N;                 // number of key-value pairs in the B-tree
    
28. 
    
29.     // helper B-tree node data type
    
30.     private static final class Node {
    
31.         private int m;                             // number of children
    
32.         private Entry[] children = new Entry[M];   // the array of children
    
33.         private Node(int k) { m = k; }             // create a node with k children
    
34.     }
    
35. 
    
36.     // internal nodes: only use key and next
    
37.     // external nodes: only use key and value
    
38.     private static class Entry {
    
39.         private Comparable key;
    
40.         private Object value;
    
41.         private Node next;     // helper field to iterate over array entries
    
42.         public Entry(Comparable key, Object value, Node next) {
    
43.             this.key   = key;
    
44.             this.value = value;
    
45.             this.next  = next;
    
46.         }
    
47.     }
    
48. 
    
49.     // constructor
    
50.     public BTree() { root = new Node(0); }
    
51. 
    
52.     // return number of key-value pairs in the B-tree
    
53.     public int size() { return N; }
    
54. 
    
55.     // return height of B-tree
    
56.     public int height() { return HT; }
    
57. 
    
58. 
    
59.     // search for given key, return associated value; return null if no such key
    
60.     public Value get(Key key) { return search(root, key, HT); }
    
61.     private Value search(Node x, Key key, int ht) {
    
62.         Entry[] children = x.children;
    
63. 
    
64.         // external node
    
65.         if (ht == 0) {
    
66.             for (int j = 0; j < x.m; j++) {
    
67.                 if (eq(key, children[j].key)) return (Value) children[j].value;
    
68.             }
    
69.         }
    
70. 
    
71.         // internal node
    
72.         else {
    
73.             for (int j = 0; j < x.m; j++) {
    
74.                 if (j+1 == x.m || less(key, children[j+1].key))
    
75.                     return search(children[j].next, key, ht-1);
    
76.             }
    
77.         }
    
78.         return null;
    
79.     }
    
80. 
    
81. 
    
82.     // insert key-value pair
    
83.     // add code to check for duplicate keys
    
84.     public void put(Key key, Value value) {
    
85.         Node u = insert(root, key, value, HT);
    
86.         N++;
    
87.         if (u == null) return;
    
88. 
    
89.         // need to split root
    
90.         Node t = new Node(2);
    
91.         t.children[0] = new Entry(root.children[0].key, null, root);
    
92.         t.children[1] = new Entry(u.children[0].key, null, u);
    
93.         root = t;
    
94.         HT++;
    
95.     }
    
96. 
    
97. 
    
98.     private Node insert(Node h, Key key, Value value, int ht) {
    
99.         int j;
    
100.         Entry t = new Entry(key, value, null);
     
101. 
     
102.         // external node
     
103.         if (ht == 0) {
     
104.             for (j = 0; j < h.m; j++) {
     
105.                 if (less(key, h.children[j].key)) break;
     
106.             }
     
107.         }
     
108. 
     
109.         // internal node
     
110.         else {
     
111.             for (j = 0; j < h.m; j++) {
     
112.                 if ((j+1 == h.m) || less(key, h.children[j+1].key)) {
     
113.                     Node u = insert(h.children[j++].next, key, value, ht-1);
     
114.                     if (u == null) return null;
     
115.                     t.key = u.children[0].key;
     
116.                     t.next = u;
     
117.                     break;
     
118.                 }
     
119.             }
     
120.         }
     
121. 
     
122.         for (int i = h.m; i > j; i--) h.children[i] = h.children[i-1];
     
123.         h.children[j] = t;
     
124.         h.m++;
     
125.         if (h.m < M) return null;
     
126.         else         return split(h);
     
127.     }
     
128. 
     
129.     // split node in half
     
130.     private Node split(Node h) {
     
131.         Node t = new Node(M/2);
     
132.         h.m = M/2;
     
133.         for (int j = 0; j < M/2; j++)
     
134.             t.children[j] = h.children[M/2+j];
     
135.         return t;   
     
136.     }
     
137. 
     
138.     // for debugging
     
139.     public String toString() {
     
140.         return toString(root, HT, "") + "\n";
     
141.     }
     
142.     private String toString(Node h, int ht, String indent) {
     
143.         String s = "";
     
144.         Entry[] children = h.children;
     
145. 
     
146.         if (ht == 0) {
     
147.             for (int j = 0; j < h.m; j++) {
     
148.                 s += indent + children[j].key + " " + children[j].value + "\n";
     
149.             }
     
150.         }
     
151.         else {
     
152.             for (int j = 0; j < h.m; j++) {
     
153.                 if (j > 0) s += indent + "(" + children[j].key + ")\n";
     
154.                 s += toString(children[j].next, ht-1, indent + "     ");
     
155.             }
     
156.         }
     
157.         return s;
     
158.     }
     
159. 
     
160. 
     
161.     // comparison functions - make Comparable instead of Key to avoid casts
     
162.     private boolean less(Comparable k1, Comparable k2) {
     
163.         return k1.compareTo(k2) < 0;
     
164.     }
     
165. 
     
166.     private boolean eq(Comparable k1, Comparable k2) {
     
167.         return k1.compareTo(k2) == 0;
     
168.     }
     
169. 
     
170. 
     
171.    /*************************************************************************
     
172.     *  test client
     
173.     *************************************************************************/
     
174.     public static void main(String[] args) {
     
175.         BTree<String, String> st = new BTree<String, String>();
     
176. 
     
177. //      st.put("www.cs.princeton.edu", "128.112.136.12");
     
178.         st.put("www.cs.princeton.edu", "128.112.136.11");
     
179.         st.put("www.princeton.edu",    "128.112.128.15");
     
180.         st.put("www.yale.edu",         "130.132.143.21");
     
181.         st.put("www.simpsons.com",     "209.052.165.60");
     
182.         st.put("www.apple.com",        "17.112.152.32");
     
183.         st.put("www.amazon.com",       "207.171.182.16");
     
184.         st.put("www.ebay.com",         "66.135.192.87");
     
185.         st.put("www.cnn.com",          "64.236.16.20");
     
186.         st.put("www.google.com",       "216.239.41.99");
     
187.         st.put("www.nytimes.com",      "199.239.136.200");
     
188.         st.put("www.microsoft.com",    "207.126.99.140");
     
189.         st.put("www.dell.com",         "143.166.224.230");
     
190.         st.put("www.slashdot.org",     "66.35.250.151");
     
191.         st.put("www.espn.com",         "199.181.135.201");
     
192.         st.put("www.weather.com",      "63.111.66.11");
     
193.         st.put("www.yahoo.com",        "216.109.118.65");
     
194. 
     
195. 
     
196.         StdOut.println("cs.princeton.edu:  " + st.get("www.cs.princeton.edu"));
     
197.         StdOut.println("hardvardsucks.com: " + st.get("www.harvardsucks.com"));
     
198.         StdOut.println("simpsons.com:      " + st.get("www.simpsons.com"));
     
199.         StdOut.println("apple.com:         " + st.get("www.apple.com"));
     
200.         StdOut.println("ebay.com:          " + st.get("www.ebay.com"));
     
201.         StdOut.println("dell.com:          " + st.get("www.dell.com"));
     
202.         StdOut.println();
     
203. 
     
204.         StdOut.println("size:    " + st.size());
     
205.         StdOut.println("height:  " + st.height());
     
206.         StdOut.println(st);
     
207.         StdOut.println();
     
208.     }
     
209. 
     
210. }
     
211. 
     
212. 
     
213. Copyright © 2002–2010, Robert Sedgewick and Kevin Wayne.
     
214. Last updated: Mon Jul 25 08:34:07 EDT 2011.

复制代码

请问楼主忘记贴附件了吗？还是我阅读权限不够，看不到附件。