btholt / four-semesters-of-cs Goto Github PK

Dear Brian, I'm the textbook manager at the MIT Press, and I received a query from a customer looking for the free edition of Introduction to Algorithms that you mention here. This book is not freely available within copyright. Can you revise your wording so we don't frustrate readers by leading them to believe that this book is freely available? Thank you for your support of Introduction to Algorithms. Michelle Pullano, Textbook Manager, the MIT Press, [email protected]

First, thank you for creating this course, Brian. I didn't realize how much I would enjoy the study of algorithms and recursion.

Second, I have a question regarding the Big O for Linked Lists, specifically for deletes. On line 429 of the course materials, you say that "LinkedList's adds and deletes are O(1) but the gets are O(n)". However, the delete method we implemented uses the _find method (if we are not deleting the head), which contains a loop. Would this not mean that delete is also (usually) O(n)? Building on that, would this also mean that the LinkedList is really only optimized for adds?

Looking at the Big O cheatsheet, they describe a singly linked list as having O(n) for access and search, while having O(1) for insertion and deletion, so I know I must be misunderstanding something. Could you provide a little more explanation behind this? I would greatly appreciate it 😄

You probably saved them while doing the course.

Please correct me if I am wrong, but I believe the Insertion Sort algorithm on codepen is O(n²) regardless if the array is mostly sorted or not. This can be observed by the fact that if you pass in a completely sorted array, there are still 45 comparisons made. This can also be observed by the fact that it is as performant as an optimized Bubble Sort. Also, as I understand, Array.splice is an O(n) operation and should be avoided if possible. This is a little nit-picky, but I believe it might come up during coding interviews.

Here is my implementation, which is O(n) when the array is mostly sorted. I am sure there is a cleaner way to write it than my implementation, however.

The link to Introduction to Algorithms leads to a page where we can buy the book in various formats or rent the book for a fee. It seems there's no free version. I suggest updating the text or possibly linking to an older, free version of it if there is one available.

There is one typo mistake in second paragraph of set explanation. Allows put two time in second line.

Hi Brian, loved your courses on Frontend masters. I was looking at the solution you provided for bubble sort. While it looks good and readable, I feel the solution bubbles the largest element to the end but considers all the elements in every loop instead of leaving the bubbled elements which is kind of the purpose of bubble sort. We can reduce the time by half if we ignore the bubbled elements.

I have modified your solution by adding an index that is maintained to ignore the bubbled elements.

const bubbleSort = nums => {
  let swapped = false;
  let index = 0;

  do {
    swapped = false;
    for (let i = 0; i < nums.length - index; i++) {
      if (nums[i] > nums[i+1]) {
        let temp = nums[i];
        nums[i] = nums[i+1];
        nums[i+1] = temp;
	swapped = true;
      }
    }
    index++;
 } while(swapped)
 console.log(nums);
};

Sorry if the Front End Masters guys bug you about this, I mentioned it to them not realizing you'd asked for issues and PRs.

The snapshot method that let's you visualize the sorts as you work on them seems not to be defined in the codepens.

Is there a missing dependency, or something else going on?

Looks like the handwritten notes indicate:

[[1,2], [1,3], [2,1][2,3]...

...instead of the expected sequence [[1,1], [1,2], [1,3], [2,1]...]

In the section concerning AVL trees, I would replace the sentence "move node B's right child to its left child" with "move node B's left child to its right child".

What do you think ?

This link on the page http://btholt.github.io/four-semesters-of-cs/ doesnot work.
ForwardJS.

Thanks for the awesome resource.

For the factorial exercise, the output just displays 1 spec, 0 failures, 1 pending spec and it doesn't change. Might be due to a breaking change from Jasmine.

https://codepen.io/btholt/pen/QyMjNa?editors=0011