reneargento / algorithms-sedgewick-wayne Goto Github PK
View Code? Open in Web Editor NEWSolutions to all the exercises of the Algorithms book by Robert Sedgewick and Kevin Wayne
License: MIT License
Solutions to all the exercises of the Algorithms book by Robert Sedgewick and Kevin Wayne
License: MIT License
The sequence that cannot be the sequence of keys examined is:
d. 2, 7, 3, 8, 4, 5
The option b is [4, 10, 8, 7, 5, 3]. "10" is the next key of "4", which means that the search path goes to the right subtree of "4".Therefore, "3" cannot appear in the search path. So, option b cannot be the sequence of keys examined as well.
the tilde notation defines ~f(N) as a function with which the limit of the actual stuff happening ( g(n) divided by ~f(n) ) tends to 1 when n tends to infinity to
1.4.5
a) ~N (this one is ok )
b) ~1
you wrote 1/N but for f(N) = 1 + 1/N , the limit when n -> infinity of (1 + 1/N)/(1/N) = infinity so ~F(N) is clearly not = to 1/N
c) ~1
d) ~2N^3
e) ~1
lg2(2N)/lg2(N) = lg2(2)/lg2(N) + lg2(N)/lg2(N) = 1 + lg2(2)/lg2(N)
lim n-> infinity ( 1 + lg(2)/lg(N) ) /1 = 1/1 + 0/1 = 1 so ~1
f) ~2
lg(NĀ²+1)/lg(N) approximately = lg(NĀ²)/lg(N) = 2lg(N)/lg(N) = 2
lim n-> inf. 2/2 =1 so ~2
... etc
public class WordCombination {
public static void getComPound(List<String> a) {
int count = 0;
Collections.sort(a);
Set<String> wSet = new HashSet<>(a);
for (int i = 0; i < a.size(); i++) {
for (int j = i + 1; j < a.size(); j++) {
if (!a.get(j).startsWith(a.get(i)))
break;
else {
if (wSet.contains(a.get(j).substring(a.get(i).length()))) {
System.out.println(a.get(i) + " + " + a.get(j).substring(a.get(i).length()) + " = " + a.get(j));
count++;
}
}
}
}
System.out.println("Total Count : " + count);
}
public static void main(String[] args) {
List<String> a = new ArrayList<>();
a.add("end");
a.add("begin");
a.add("start");
a.add("startend");
a.add("endstart");
a.add("be");
a.add("being");
a.add("ing");
a.add("bee");
a.add("e");
getComPound(a);
}
}
remove() repeat item not act as expect: add(1 1 1 2 3 1 1 1 2 3 1 1 1,
remove (1,
print: 2 3 1 2 3 1
If you give as input a tree:
5
/ \
2 x
where x
is a subtree containing 5 million children. The algorithm provided will return 2
33% of the time, 5
33% of the time, and one of the other ~5 million keys the other 33% of the time.
I think the usefulness of this function can be improved: below I provide my Python3 solution that I think is random with a uniform distribution:
def _random_key(self, node):
# We managed to get to a leaf without picking a node.
if (not node.left) and (not node.right):
return node
rand_for_cur = random.uniform(0, 1)
# 1/N chance to pick the current node, this is needed for internal nodes
# to be candidates in the selection.
if rand_for_cur < (1/self.size()):
return node
else:
if node.left is not None:
left_child_size = node.left.subtree_size
else:
left_child_size = 0
rand_for_move = random.uniform(0, 1)
chance_move_left = left_child_size / node.subtree_size
if not node.left:
return self._random_key(node.right)
elif not node.right:
return self._random_key(node.left)
else:
if rand_for_move < chance_move_left:
return self._random_key(node.left)
else:
return self._random_key(node.right)
`public class FourSum {
private static int countFourSum(int[] numbers) {
int count = 0;
for (int j = 0; j < numbers.length; j++) {
for (int i = j + 1; i < numbers.length; i++) {
int front = i + 1, rear = numbers.length - 1;
while (front < rear) {
if (numbers[front] + numbers[rear] + numbers[i] + numbers[j] == 0) {
System.out.printf(String.format("{%d} : {%d} : {%d} : {%d} \n", numbers[front], numbers[rear],
numbers[j], numbers[i]));
front++;
rear--;
count++;
} else {
if (Math.abs(numbers[front]) > Math.abs(numbers[rear])) {
front++;
} else {
rear--;
}
}
}
}
}
return count;
}
public static void main(String[] args) {
int[] numbers = { 1, 2, 3, 4, -4, -5, -6, 2, 4, -1 };
Arrays.sort(numbers);
System.out.println(countFourSum(numbers));
}
}
`
After the search range is switched to [i, i + F(k-2)], next F(k-2) and F(k-1) would be better to be calculated from the new F(k) that is F(k-2) in this case (the length of the range).
Based on the current implementation, we may be able to update fibonacciBeforeN and fibonacciN additionally in this clause:
if (key < array[elementToCheck]) {
high = low + fibonacciBeforeN;
//move fibonacci backward a step
aux = fibonacciBeforeN;
fibonacciBeforeN = fibonacciN - fibonacciBeforeN; //F(k-2)
fibonacciN = aux; //F(k-1)
}
In task description they ask: "Implement a natural mergesort for linked lists. ". In 2.2.16 they describe "natural mergesort" for arrays as finding sorted sub-arrays, but looks like in 2.2.17 solution we just increase size of sublist twice for each iteration, shouldn't we search for sorted sublists?
Thanks.
Add an extra operation catenation that (destructively) concatenates two queues, stacks, or steques (see Exercise 1.3.32). Hint : Use circular linked list, maintaining a pointer to the last item.
The solution uses sort() which is linearithmic. If you want a linear solution avoid sort. Traverse the (non sorted) array to get the smallest two numbers.
I run code given at book site for following input and set the counter to partition method
String[] a = {"Q","S","T","Q","S","T","Q","S","T","T","Q","S","S","Q","Q","Q"};
String[] a = {"Q","S","Q","S","Q","S","Q","S","S","Q","Q","Q"};
so if you observe the count and order of input [no of time elements changes in supplied sequence] are matching.
For N = 5 you produce duplicate tree shapes, for example:
Insertion order: 5 2 1 4 3, 5 2 4 1 3
5
2
1 4
3
and
Insertion order: 5 2 4 3 1
5
2
1 4
3
There should be 42 tree shapes for N = 5
PS: Thanks a lot for these solutions! I use them to check if my answers were correct, they are very well written :)
Thanks a lot for what you've done. Goods Luck!
I think real question here is how you implement Comparable Interface rather than sorting.
enum Suit{
SPADES, HEARTS, CLUBS, DIAMONDS;
}
class Card implements Comparable{
int rank;
Suit suit;
public Card(int rank,Suit suit){
this.rank=rank;
this.suit=suit;
}
@Override
public int compareTo(Card arg0) {
Integer p =this.rank*(this.suit.ordinal()*13);
Integer q =arg0.rank*(arg0.suit.ordinal()*13);
return p.compareTo(q);
}
@Override
public String toString() {
return this.suit.name()+" "+this.rank;
}
}
public class DeckSort {
public static void main(String[] args) {
Card spadeQ=new Card(12, Suit.SPADES);
Card heart5=new Card(5, Suit.HEARTS);
Card diamond10=new Card(10, Suit.DIAMONDS);
Card clubK=new Card(13, Suit.CLUBS);
Card diamond9=new Card(9, Suit.DIAMONDS);
ArrayList<Card> deck=new ArrayList<>();
deck.add(clubK);deck.add(diamond9);deck.add(spadeQ);deck.add(heart5);deck.add(diamond10);
//Use Shell Sort Instead
Collections.sort(deck);
for(Card c:deck) {
System.out.println(c);
}
}
}
I cannot understand the reason why the running time of quicksort becomes quadratic when the algorithm scans over items equal to the partitioning item? Would you please give a theoretical explanation or an example? Thank you very much!
Using a stack, it would result in DFS search. Would it not?
Hello!
There is a lack of size changing in some methods, such as
delete (ln 72, 79)
remove(ln 93, 100)
removeAfter(ln 132)
insertAfter(ln 149)
Thank you!
I was working 5.4.11, and I came up with a different answer for part c. We both agree that we can have one thousand 1's and zero 01's, 998 1's and 2 01's, etc. However, I came out with an answer of 2^500 instead of 500, as the 01's and 11's can be placed in multiple permutations.
To illustrate with a simpler example, if our bitstring had to be 6 bits long instead of 1000 bits long, the following bitstrings would match our regular expression (I use "|" as a separator just for clarity.):
==6 1's and 0 01's==
This answer of 2^3 corresponds to the 2^500 that I calculated for 5.4.11c.
https://stackoverflow.com/questions/43263249/number-of-largest-element-exchanges-for-quicksort
I don't understand it very well but it seems reasonable.
Would you like to specify a license for the code in github repository "reneargento/algorithms-sedgewick-wayne" ?
I can mention that I am particularly interested in your implementation of "k shortest paths".
(i.e. your class "chapter4.section4.KShortestPaths" and its dependencies)
I have done some experimentation with it, comparing it (using the same test data) with the following three other libraries with implementations of "k shortest paths":
https://github.com/yan-qi/k-shortest-paths-java-version
https://github.com/bsmock/k-shortest-paths
https://github.com/jgrapht/jgrapht
Your implementation seem to be faster than those three above, so therefore I would be interested in using your implementation as a new Adapter implementation, i.e. a new implementation in this repository:
https://github.com/TomasJohansson/adapters-shortest-paths
However, the question is if you want to choose a license, to specify if/how others are allowed to use your code?
Hello! First of all, thanks for creating this repository! I've found it very helpful for my development as I work through the book's practice problems.
Second, I just had a quick question for Question 3.2.1. You say that there should be a total of 27 compares to form a binary search tree for E A S Y Q U E S T I O N. However, when I do the problem, I keep coming up with 28. I think the discrepancy is that only one compare is counted for the second "S," whereas two should be counted--one to determine that S > E and a second to determing that S == S and should thus replace the existing S in the tree.
Thanks for your time!
algorithms-sedgewick-wayne/src/chapter1/section4/Exercise10.java
Lines 32 to 54 in ac1dbf2
From SO: https://stackoverflow.com/questions/10148849/find-lowest-index-of-a-given-value-in-a-presorted-array
Your recursive version is indeed very cool! It took me some time to understand the magic. I found a non-recursive version on SO and it's neat and much staightforward. Maybe you could comment that in the original code as another source?
Python code:
def binary_search(x, a):
lo = 0
hi = len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x:
lo = mid + 1
elif a[mid] > x:
hi = mid
elif mid > 0 and a[mid-1] == x:
hi = mid
else:
return mid
return -1
Thank you for all the hard work btw, I am reading this book and visiting your repo frequently. š
int[] array1 = {15,14,13,12,11,10,10,11,12,13,14,15};
Here is the Correct one
Check out following sites for reference :
https://stackoverflow.com/questions/29966730/order-of-growth-of-as-function-of-n
https://softwareengineering.stackexchange.com/questions/253421/running-time-of-simple-for-loops
Hey, I might be wrong here but I believe the first for loop creates the array 9 8 7 6 5 4 3 2 1 0. Then the second for loop reverses the first array, making it 0 1 2 3 4 5 6 7 8 9. I believe this happens because you have to determine the inner bracket first. So during the first round with i=0, a[i]=9, therefore a[a[i]] is really a[a[0]=9]==0, its confusing but I think is what is happening.
For HeapSort call we populate array starting from 0 index:
System.arraycopy(array, 0, heapSortCopy, 0, array.length);
but looks like HeapSort.heapSort / sortdown expects first element at index 1 and 0 element is not processed correctly?
There seems to be a problem with Option D.
Sequence D is possible to generate:
Push 0, Push 1, Push 2, Push 3, Push 4, pop, pop, pop, pop, pop, push(5), pop, push(6), pop, push(7), pop, push(8), pop, push(9), pop
And Sequence F, G seems impossible to generate.
So answer should be B, C, F and G
Hello!
It seems to me, that the shuffle algorithm has a little bug. We should choose random index between 0 and i + 1, not size (see https://youtu.be/54rMYC2pEtw?t=236 or StdRandom.shuffle implementation, or Collections.shuffle implementation).
Thanks)
For the first test case (where all six points are on the same line), why is the expected count 10 instead of C(3, 6) = 6! / (3! * 3!) = 20?
Point2D[] points = new Point2D[6];
for(int i = 0; i < points.length; i++) {
Point2D point = new Point2D(i, i + 1.5);
points[i] = point;
}
int numberOfTriples1 = exercise26_3Collinearity.countTriples(points);
StdOut.println("Number of triples: " + numberOfTriples1 + " Expected: 10");
Notice in countTriplesUsingSlopes() there is a break statement (line 128) in the for loop which is counting the triples.
for (Integer index : pointIndexes) {
if (index > i && index > j) {
triples++;
break; // is this break really necessary?
}
}
Why HashMap is used to check the Duplicate Data. It should use find function of linked list instead of using HashMap.
The union method looks to have some problems.
public void union(int site1, int site2) {
int leader1 = leaders[site1];
int leader2 = leaders[site2];
if (leader1 == leader2) {
return;
}
if (ranks[leader1] < ranks[leader2]) {
leaders[leader1] = leader2;
} else if (ranks[leader2] < ranks[leader1]) {
leaders[leader2] = leader1;
} else {
leaders[leader1] = leaders[leader2];
ranks[leader1]++;
if (ranks[leader1] > maxHeight) {
maxHeight = ranks[leader1];
}
}
components--;
}
Pay attention to line 58, 59 and 69, review if we need to change them as follows:
public void union(int site1, int site2) {
int leader1 = find[site1];
int leader2 = find[site2];
if (leader1 == leader2) {
return;
}
if (ranks[leader1] < ranks[leader2]) {
leaders[leader1] = leader2;
} else if (ranks[leader2] < ranks[leader1]) {
leaders[leader2] = leader1;
} else {
leaders[leader2] = leader1;
ranks[leader1]++;
if (ranks[leader1] > maxHeight) {
maxHeight = ranks[leader1];
}
}
components--;
}
Hello,
On Exercise 4.4.11, 16V bytes instead of 8V bytes are added for the Bag references in the adj[] array. This is corroborated by the booksite and is justified in your file as "resizing array," but best I can see, the array is never resized. Could you please explain this just a little bit more deeply?
Thank you,
LegendaryKokiri
algorithms-sedgewick-wayne/src/chapter2/section2/Exercise6.java
Lines 124 to 156 in ef93b87
When doing a compare a[i] < aux[j]
or assignment a[i] = aux[j]
, this should be counted as twice array access.
So I think the numberOfArrayAccesses
increasement in order should be:
numberOfArrayAccesses += 2;
numberOfArrayAccesses += 4;
numberOfArrayAccesses += 2;
And you can tell from Proposition G of Page 275, 6NlgN at most array access, and 4NlgN at least array access (approximately) . So Exercise6.txt is wrong I think.
The result I get:
The result I get is very close to 6NlogN and I think this should be correct.
related C++ code:
https://gist.github.com/ajfg93/9b55b2f7b1de7f86ed7f9ac5c6c8a56a
0 (source)
/
1 - 2
You said that "Using a stack the distance from 0 to 1 will be 1 and from 0 to 2 will be 2.
Using a queue, the distance from 0 to both 1 and 2 will be 1."
but code in dfs just add all vertices adjacent to 0,so 1,2 will be added to stack.At the same time,calculate distTo[1] and distTo[2],which will be 1 rather than 2.
Things can be different in other cases.like this one:
0 (source)
/
1 - 2
\
\ 3
\
4
Shortest distance from root to 4 is 2(0->1->2),but we may get a wrong answer 0->2->3->4.
Seems 1.5.3 solved with quick union while excersice requested to solve it with weighted quick union. If you check and find my concern is correct please let me know to share my answer with you.
If the graph has a node of degree one, removing it gives a connected graph.
Example: o - o
Otherwise, every path in the graph belongs to a cycle.
I think that it is not correct if you have such graph:
b f
/ \ / \
a c - e g
\d/ \h/
Path c-e is not a part of the cycle
If you have the insertion order: 1 3 2 4 you will get a tree shaped like the reverse of the tree with insertion order 4 2 1 3 or 4 2 3 1. (I can't get Github to format it, so it would shot the tree structure.) P.S. love your work!
The problem ask that the numbers be coprime not that both should be prime.
So just checking that largest does not have a remainder when diving by the smallest should do it.
Hello, I didn't see any logic related to path compression in the find() method.
Section 1.4 Ex 10.
int[] testArray = {4, 4, 4, 4, 4, 4, 15, 20, 20, 20, 20, 21};
it should return 0 but returns 1.
CheckOut this :---
public class BinarySearch {
int binarySearch(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x) {
int findLowest = binarySearch(arr, l, mid - 1, x);
if (findLowest < 0)
return mid;
else
return findLowest;
} else if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
else {
return binarySearch(arr, mid + 1, r, x);
}
}
return -1;
}
// Driver method to test above
public static void main(String args[]) {
BinarySearch ob = new BinarySearch();
int arr[] = { 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 3, 4, 10, 40 };
int n = arr.length;
int x = 1;
int result = ob.binarySearch(arr, 0, n - 1, x);
if (result == -1)
System.out.println("Element not present");
else
System.out.println("Element found at index " + result);
}
}
Your answer to this problem is not right.
My solution for determining whether a given permutation can be generated:
import std.LinkedStack;
import std.StdOut;
public class StackGenerability {
public static boolean permutationGenerability(String[] permutation) {
LinkedStack<Integer> stack = new LinkedStack<>();
int current = 0;
for (String s: permutation) {
int x = Integer.parseInt(s);
if (stack.isEmpty() || x > stack.peek()) {
for (; current < x; ++current) {
stack.push(current);
}
current++;
}
else if (x == stack.peek()) {
stack.pop();
current++;
}
else {
return false;
}
}
return true;
}
public static void main(String[] args) { // examples from 1.3.3
StdOut.println(permutationGenerability("4 3 2 1 0 9 8 7 6 5".split(" ")));
StdOut.println(permutationGenerability("4 6 8 7 5 3 2 9 0 1".split(" ")));
StdOut.println(permutationGenerability("2 5 6 7 4 8 9 3 1 0".split(" ")));
StdOut.println(permutationGenerability("4 3 2 1 0 5 6 7 8 9".split(" ")));
StdOut.println(permutationGenerability("1 2 3 4 5 6 9 8 7 0".split(" ")));
StdOut.println(permutationGenerability("0 4 6 5 3 8 1 7 2 9".split(" ")));
StdOut.println(permutationGenerability("1 4 7 9 8 6 5 3 0 2".split(" ")));
StdOut.println(permutationGenerability("2 1 4 3 6 5 8 7 9 0".split(" ")));
}
}
Otherwise the badShuffle() in 1.1.37 won't show bad results in the end.
private static int countThreeSum(int[] numbers) {
int count=0;
for(int i=0;i<numbers.length;i++) {
int front=0,rear=numbers.length-1;
while(front<rear) {
if(numbers[front]+numbers[rear]+numbers[i]==0) {
System.out.printf(String.format("Front : {%d} Rear : {%d} I : {%d} \n", numbers[front],numbers[rear],numbers[i]));
front++;rear--;
count++;
}else {
if(Math.abs(numbers[front])>Math.abs(numbers[rear])) {
front++;
}else {
rear--;
}
}
}
}
return count;
}
public static void main(String[] args) {
int[] numbers = { 1, 3, 5, 7, 12, 16, 19, 15, 11, 8, -1, -3, -7, -8, -11, -17, -15 };
Arrays.sort(numbers);
System.out.println(countThreeSum(numbers));
}
The correct solution I think is below.
Thanks for the effort to create this repository! It helps a lot to cross check solutions.
Initial - [0,1,2,3,4,5,6,7,8,9]
9-0
[0,1,2,3,4,5,6,7,8,0]
0 1 2 3 4 5 6 7 8
9
3-4
[0,1,2,4,4,5,6,7,8,0]
0 1 2 4 5 6 7 8
9 3
5-8
[0,1,2,4,4,8,6,7,8,0]
0 1 2 4 6 7 8
9 3 5
7-2
[0,1,2,4,4,8,6,2,8,0]
0 1 2 4 6 8
9 7 3 5
2-1
[0,1,1,4,4,8,6,2,8,0]
0 1 4 6 8
9 7 3 5
2
5-7
[0,1,1,4,4,8,6,2,1,0]
0 1 4 6
9 7 3
2
8
5
0-3
[4,1,1,4,4,8,6,2,1,0]
1 4 6
7 3
2
8
5
0
9
4-2
[4,1,1,4,1,8,6,2,1,0]
1 6
7
4
3
2
8
5
0
9
algorithms-sedgewick-wayne/src/chapter1/section3/Exercise48_TwoStacksDeque.java
The problem asks to implement two stacks with a single Deque. Unless I am misunderstanding something here, the solution seems to be using 2 Stacks and implementing a Deque.
4th largest can also appear on position 2 or 3 when 3rd largest is child of 2nd largest.
So in summary, 4th largest can appear on position 2 to 15, cannot appear on 1 and 16-31.
I dont know whether this is correct or not but following your testing in "main" function this turns out to be correct for all of your tests. Proportional to 2*O(log N).
public static int keyGuess(int key,int start,int end) {
if(start > end || start == end) {
return -1;
}
int initGuess = start + (end - start) / 2;
if(initGuess == key) {
return initGuess;
}
int secondGuess = initGuess + 1;
if(secondGuess == key) {
return secondGuess;
}
boolean isHotter = isHotter(initGuess,secondGuess,key);
if(isHotter) {
return keyGuess(key,secondGuess,end);
}else {
return keyGuess(key,start,initGuess);
}
}
public static boolean isHotter(int previous,int current,int key) {
if(Math.abs(current - key) < Math.abs(previous - key)) {
return true;
}else {
return false;
}
}
public static void main(String[] args) {
StdOut.println(keyGuess(4,1,10));
StdOut.println(keyGuess(12,1,20));
StdOut.println(keyGuess(19,1,20));
StdOut.println(keyGuess(20,1,20));
StdOut.println(keyGuess(21,1,20));
StdOut.println(keyGuess(-1,1,100));
}
How are there 2 Qs in 3.4.10 on M=16?
There cannot be duplicate keys in a hashtable?
Thank you
A declarative, efficient, and flexible JavaScript library for building user interfaces.
š Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ššš
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ā¤ļø Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.