Data Structures & Algorithms in Java

Robert Lafore

Mentioned 6

Designed to be easy to read and understand although the topic itself is complicated, this book explains that algorithms are the procedures that software programs use to manipulate data structures. Besides clear and simple example programs, Lafore includes a workshop as a small demonstration program executable on a Web browser.

More on Amazon.com

Mentioned in questions and answers.

Greetings, everyone. I'm new to the wonderful world of Programming, and just came upon this site here. I'm very excited to get into programming as a whole, as I have met tons of other eager people at the business that I am interning at this summer. It's a great community, and I'm excited to become a part of that community!

I'm going into my Sophomore year in college studying Computer Science. Last semester, I took a beginners course in Java programming. I really like the language, however my teacher did not explain the language very well, and I (and the rest of the class) fell behind.

At the business that I have an internship with this summer, I discovered that they have a corporate subscription to Safari Books. I've been pouring through the site looking at various text books, when I stumbled upon Head First Java. I've been reading through it pretty much every day, and I'm slowly getting the hang of the language once again.

I would like to test out my knowledge and skill by completing beginner projects or problems, such as the ones that you find in the back of a text book. Head First provides a lot of sample code to complete relating to the project detailed within the chapters, however I want to do some other projects where I don't have a reference; where I can fully apply myself to without any added help.

I've done the cursory Google searches, and I can't seem to find any websites or webpages that have a list of beginner programming problems to solve. Does anyone here have a list that they know of, or a page that they bookmarked, or even ideas of some problems that I can solve!

Thank you very much in advance, and I look forward to learning and applying myself further!

I've used this book (or earlier editions thereof) to teach a couple of people java / writing actual code in java. The problems in the book are pretty well thought out, and it's good for getting used to doing actual tasks. I've linked to amazon for the detail, but you can get the book at many college/university libraries (find yours through worldcat to see if your library or one nearby has it)

Good luck!

In the depicted 2-3-4 tree below (from Data Structures & Algorithm in Java, 2nd ed), why does inserting 99 cause the node split of 83/92/104 when it seems like 99 could've been inserted into the right child (the C child, into the spot immediately after 97) without any splitting done?

enter image description here

Inserting 99 into C would be OK in that it would maintain all the invariants, but the algorithm is simpler in general if insert always expands 4-nodes on the way down. Then there will always be room for any needed lifting and rotations. It may help to compare the case where C is already a 4-node itself.

For my test tomorrow, I will need to be able to:

explain how stack and queue are special cases of a list.

Does anyone know a good place where I can read about this? A Google searches can't help me with this one, it's one of those "We discussed this in class, don't ask me again" type of questions.

Yes there is a book by Robert Lafore called Data Structures and Algorithms in java.

Read first six chapters (I might be wrong, maybe more) and you should be pretty good with all data structures(most commonly used).

Wondering why for red black tree insert, we mark the new node as Red first, then do some adjustment? Why not mark it as Black and do some appropriate adjustment? Thanks.

I think the only reason is, adding a Red node will not break any rules of Red-Black tree on black node related rules (e.g. path from root to leaf contains the same number of black nodes), which only needs to adjust any violation of red rules (i.e. cannot be consecutive two red nodes for parent/child), which makes code simple. I do not think add a black node and adjust violations on number of black nodes (on different path) is impossible. In short, adding red node other than black is only for the purpose of code simplicity, no other reasons. If I am wrong, please feel free to correct me.

  1. Inserting a red node is less likely to violate the red-black rules than inserting a black one. This is because, if the new red node is attached to a black one, no rule is broken. It doesn’t create a situation in which there are two red nodes together which breaks rule of red parent black children, and it doesn’t change the black height(number of black nodes from root to leaf) in any of the paths.
  2. Of course, if you attach a new red node to a red node, the rule of red parent-black children will be violated. However, with any luck this will happen only half the time. Whereas, if you add a new black node, it would always change the black height for its path, violating the black height rule.

  3. Also, it’s easier to fix violations of red parent-black children rule than black height rule.

Source: Data Structures & Algorithms in Java Second Edition - Robert Lafore page 437.

Possible Duplicate:
Learning Algorithms and Data Structures Fundamentals

I am very weak in Data Structures and Algorithms especially in trees,Linked List etc. How to improve the skills. Can you please suggest some sites also where I can find lots of Questions to prepare for interviews.

Data Structures and Algorithms in Java by Robert Lafore
Algorithms by Herb Sutter & Andrei Alexandrescu

The former is written in Java but it gives you a very clear understanding of many basic data structures (lists, hashtables, lists, graphs, sorting etc). I consider it a well written book with many code examples. Also, the price is very "attractive".
However, do not copy paste the code samples but rather understand what they do (he gives a clear explanation of what happens in difficult points).
I also do encourage you to study those DS by programming them in C/C++ as they give you a better idea of how things work (in my opinion). The latter book may help although I haven't read it (they suggested it to me).

Have fun :)

I am trying to get two links to render side by side such as: amazon/chegg or something to that affect. I know how I can do this in html but I am having the hardest time to get this to work in rails slim. I was trying to use something along the lines of this:

a href="#{@group.amazon_link}" title="Amazon"
                    | /awesome-book

But it shows up like this

Where to buy: a href="https://amazon.com/dp/0672324539/?tag=devbookscom20-20" title="Amazon" | /awesome-book

I did not get the second link implemented at all but that is because I cannot get the first one to show up as a clickable link. I have looked at the slim documentation but I did not find it too helpful. What is the syntax I should be using?

I have the code below that I have found. I am trying to learn which sorting method is the fastest and which ones use the most and least comparisons. Anyone have any idea how I can add some code in here to do that? I want to tally the total number of comparisons of each sort.

//***********************************************************************************
//  Sorting.java
//
//  Contains various sort algorithms that operate on an array of comparable objects.
//
//************************************************************************************

public class Sorting

{

//------------------------------------------------------------------------------------
//  Sorts the specified array of integers using the selection sort algorithm.
//------------------------------------------------------------------------------------

public static void selectionSort (Comparable[] data)
{
  int min;

  for (int index = 0; index < data.length-1; index ++)
  {
     min = index;
      for (int scan = index+1; scan < data.length; scan++)
        if (data[scan].compareTo(data[min]) < 0)
            min = scan;

      swap (data, min, index);

  }
}
//---------------------------------------------------------------------------------------
//  Swaps to elements in the specified array.
//---------------------------------------------------------------------------------------

private static void swap (Comparable[] data, int index1, int index2)
{
   Comparable temp = data[index1];
    data[index1] = data[index2];
    data[index2] = temp;

}

//---------------------------------------------------------------------------------------
//  Sorts the specified array of objects using an insertion sort algorithm.
//---------------------------------------------------------------------------------------

public static void insertionSort (Comparable[] data)
{
  for (int index = 1; index < data.length; index++)
  {
    Comparable key = data[index];
     int position = index;

     // shift larger values to the right
     while (position > 0 && data[position-1].compareTo(key) > 0)
     {
       data[position] = data[position-1];
        position--;
     }

     data[position] = key;

    }
}

//---------------------------------------------------------------------------------------
//  Sorts the specified array of objects using a bubble sort algorithm.
//---------------------------------------------------------------------------------------

public static void bubbleSort (Comparable[] data)
{
  int position, scan;

  for (position = data.length - 1; position >= 0; position--)
  {
     for (scan = 0; scan <= position - 1; scan ++)
       if (data[scan].compareTo(data[scan+1]) >0)
          swap (data, scan, scan+1);

    }
}

//---------------------------------------------------------------------------------------
//  Sorts the specified array of objects using the quick sort algorithm.
//---------------------------------------------------------------------------------------

public static void quickSort (Comparable[] data, int min, int max)
{
  int pivot;

  if (min < max)
  {
    pivot = partition (data, min, max); // make partitions
     quickSort(data, min, pivot-1);  //sort left paritions
     quickSort(data, pivot+1, max);  //sort right paritions
  }
}
//---------------------------------------------------------------------------------------
//  Creates the partitions needed for quick sort.
//---------------------------------------------------------------------------------------

public static int partition (Comparable[] data, int min, int max)
{
  //Use first element as the partition value
  Comparable partitionValue = data[min];

  int left = min;
  int right = max;

  while (left < right)
  {
    // Search for an element that is greater than the partition element
     while (data[left].compareTo(partitionValue) <= 0 && left < right)
       left++;

    // Search for an element that is less than the partition element
    while (data[right].compareTo(partitionValue) > 0)
      right--;

    if (left < right)
      swap (data, left, right);

    }

    // Move the partition element to its final position
    swap (data, min, right);

    return right; 
  }

//---------------------------------------------------------------------------------------
//  Sorts the specified array of objects using the merge sort algorithm.
//---------------------------------------------------------------------------------------

public static void mergeSort (Comparable[] data, int min, int max)
{
  if (min < max)
  {
    int mid = (min + max) / 2;
     mergeSort(data, min, mid);
     mergeSort(data, mid+1, max);
     merge (data, min, mid, max);

  }
 }

//---------------------------------------------------------------------------------------
//  Sorts the specified array of objects using the merge sort algorithm.
//---------------------------------------------------------------------------------------

public static void merge (Comparable[] data, int first, int mid, int last)
{
  Comparable[] temp = new Comparable[data.length];

  int first1 = first, last1 = mid; //endpoints of first subarray
  int first2 = mid + 1, last2 = last; //endpoints of second subarray
  int index = first1; // next index open in temp array

  // Copy smaller item from each subarry into temp until one of the subarrays is exhausted

  while (first1 <= last1 && first2 <= last2)
  {
    if (data[first1].compareTo(data[first2]) < 0)
     {
       temp[index] = data[first1];
        first1++;
     }
     else
     {
       temp[index] = data[first2];
        first2++;
     }
    index++;
  }
 //  Copy remaining elements from first subarray, if any
 while (first1 <= last1)
 {
   temp[index] = data[first1];
    first1++;
    index++;
 }

 //  Copy remaining elements from second subarray, if any
 while (first2 <= last2)
 {
   temp[index] = data[first2];
    first2++;
    index++;
 }

 // Copy merged data into original array
 for (index = first; index <= last; index++)
   data[index] = temp[index];
 }
 }

Rather learn about O-notation from a good book like:

http://www.amazon.com/Data-Structures-Algorithms-Java-2nd/dp/0672324539