Lab 1: Course Introductions (100 pts)

Due Friday, April 17 at 11:59pm on Canvas



Lab 0.1: Syllabus and Website Treasure Hunt Quiz (20 pts)

  • Read the syllabus and look through the course website and the materials posted for the course on Canvas.
  • Then, complete the Syllabus and Website Treasure Hunt Quiz posted on Canvas.
  • You can take the quiz as many times as you would like until the deadline.
  • The score of the final quiz attempt will be the one entered into the gradebook.

Lab 0.2: Learning and Intelligence Assignment (20 pts)

  • Watch the video by Salman Kahn and read the associated article.
  • Then, answer the questions on the below worksheet
  • Upload your completed assignment to Canvas as a pdf, doc, docx, txt, or odt file

Lab 0.3: Pair Programming Fundamentals (20 pts)

  • Watch Introduction to Pair Programming Video (10 minutes)
  • Then, complete the Pair Programming Video Quiz posted on Canvas
  • You can take the quiz as many times as you would like until the deadline
  • The score of the final quiz attempt will be the one entered into the gradebook
  • Note that we will do pair programming via Zoom this quarter.


Lab 0.4: Post a Clear Headshot Photo of Yourself on Your Canvas Profile (20 pts)

  • On Canvas, go to "Account" -> "Profile" -> Click on the photo and upload a new photo
  • Please select a photo that is a close-up photo of your face to receive full credit.
  • The goal of this assignment is to help me learn your names. If I cannot see your face clearly, the photo will not be helpful.
  • Because the images on my course list are so small, this photo needs to be of your face only -- not your face and shoulders or your face and body -- or the image of your face will be too tiny for me to recognize.
  • For example:

Close Up Photo of Face would receive full credit (20/20)
Photo of face only (Albert Einstein)

Photo of face and shoulders would receive half credit (10/20)

Photo of face and shoulders (Albert Einstein)

Photo of face and body would receive one quarter credit (5/20)



  • Please do not upload a photo that is not of you or you will receive no credit for this assignment
  • Partial credit as described above for a photo of your face and body or if I cannot clearly see your face in the tiny image next to your name on my course list.
  • No profile shots (half credit). Please post a picture of you facing the camera.
  • No credit if I cannot see your face or the photo is not a picture of you.
  • No credit for a photo that I consider to be inappropriate for an academic or professional setting.
  • Feel free to make use of photo editing software to crop your photo. Visit the de Anza computer lab for help using photo editing software.


Lab 0.5: Icebreaker Class Discussion (20 pts)

  • Answer the questions about yourself in each of the 8 categories, and post the answers to the discussion board.
  • Then, find two students who had the same answers as you in at least 2 categories.
  • Respond to those students by introducing yourself and pointing out what you have in common.
  • You will receive 10 points for your post answering the 8 questions, and 5 points each for your responses to 2 classmates.

Additionally, please work through the below tutorial on writing a singly-linked List class, and make sure that you understand it. This information should have been presented as part of your 36B or 35A curriculum. If you did not cover this topic, here is your chance to catch up! If you did cover it, here is a refresher!



Singly-Linked List Tutorial

  • Create a new Java project in Eclipse named List (Please notice the capitalization)
  • Right click on your project and add a new class named List.java.
  • Please refer to the tutorial if you encounter any problems.
  • Copy and paste the following code into List.java file:



/**
 * Defines a singly-linked list class
 * @author
 * @author
 */

import java.util.NoSuchElementException;

public class List<T> {
    private class Node {
        private T data;
        private Node next;
       
        public Node(T data) {
            this.data = data;
            this.next = null;
        }
    }
   
    private int length;
    private Node first;
    private Node last;
   
    /****CONSTRUCTOR****/
   
    /**
     * Instantiates a new List with default values
     * @postcondition
     */
    public List() {
 
    }
   
    /****ACCESSORS****/
   
    /**
     * Returns the value stored in the first node
     * @precondition
     * @return the value stored at node first
     * @throws NoSuchElementException when precondition is violated
     */
    public T getFirst()
throws NoSuchElementException{
        return null;
    }
   
    /**
     * Returns the value stored in the last node
     * @precondition
     * @return the value stored in the node last
     * @throws NoSuchElementException when precondition is violated
     */
    public T getLast() throws
NoSuchElementException{
        return null;
    }
   
    /**
     * Returns the current length of the list
     * @return the length of the list from 0 to n
     */
    public int getLength() {
        return -1;
    }
   
    /**
     * Returns whether the list is currently empty
     * @return whether the list is empty
     */
    public boolean isEmpty() {
        return false;
    }
   
    /****MUTATORS****/
   
    /**
     * Creates a new first element
     * @param data the data to insert at the
     * front of the list
     * @postcondition
     */
    public void addFirst(T data) {
        return;
    }
   
    /**
     * Creates a new last element
     * @param data the data to insert at the
     * end of the list
     * @postcondition
     */
    public void addLast(T data) {
        return;
    }
   
    /**
    * removes the element at the front of the list
    * @precondition
    * @postcondition
    * @throws
NoSuchElementException when precondition is violated
    */
    public void removeFirst() throws
NoSuchElementException{
        return;
    }
   
    /**
     * removes the element at the end of the list
     * @precondition
     * @postcondition
     * @throws NoSuchElementException when precondition is violated
     */
    public void removeLast()
throws NoSuchElementException{
        return;
    }
   
    /****ADDITIONAL OPERATIONS****/
   
    /**
     * List with each value on its own line
     * At the end of the List a new line
     * @return the List as a String for display
     */
    @Override public String toString() {
       return "";
    }
   

}

  • Notice that each method is only a stub.
  • You will fill in the missing method bodies as you complete this tutorial
  • Also notice that the pre and postconditions in the comments are left blank.
  • You will need to write the pre and post conditions as part of Lab 2
    • Remember that preconditions indicate what conditions must be met BEFORE the user calls the method. The method will not work properly unless the preconditions are met.
    • Postconditions indicate what will be the result of the method call. In other words, what conditions will exist after the method is called.
    • See class notes from this week and also watch the lesson videos.


ListTest.java

  • Create a second class inside the List project called ListTest.java (note the capitalization).
  • Add a main method to this class.
  • You will be using this class like scratch paper to test your List as you go along.
  • After you write each method, immediately call the method in ListTest.java, and then compile and run your code.
  • Did you get the expected output?
  • Take a moment now to create ListTest.java so it is ready when you write your methods


Constructor

  • For the default constructor, the goal is simply to initialize the fields inside the List class with a starting value - in this case default values, as the constructor takes no parameters.
  • We have 3 fields inside our List class:
    • Node first
    • Node last
    • int length
  • What are the appropriate default values for each of these fields?

    /**
     * Instantiates a new List with default values
     * @postcondition
     */
    public List() {
        first = null;
        last = null;
        length = 0;
    }
  • Once you have updated this method, please immediately test it inside of ListTest.java
  • Compile and run your code to make sure there are no errors
  • After you are finished, your ListTest.java should look like this:
/**
 * Class to test List.java
 * @author
 */
public class ListTest {
    public static void main(String[] args) {
        List<Integer> L = new List<>();
       
    }

}

Additional List Operations - toString()

  • Any class we write will inherit from the Object class, which has basic methods such as toString() that you can override.
    • For a refresher on this information, see the tutorial here.
  • The toString() method is *very important* and should be one of the very first methods that you write for any data structure.
  • Why?
    • You should be testing your code as you go along, and if you cannot print out the contents of the list, you will be unable to determine whether your methods are working properly.
  • Additionally, toString() determines how you are going to display the List information to the user.
    • For example, are you going to display it with [ ] and a , separating each piece of data, like so: [1,2,3,4]?
    • Are you going to display each piece of data on its own line or simply separated by a blank space?
  • For the purposes of this Lab, we will simply have the data items displayed each on its own line.
  • The idea behind the toString() method is straightforward:
  1. Create an empty String which will ultimately store the List as a String
  2. Create a temporary iterator to point to the first node
  3. Using a loop, concatenate the data for the current node
  4. Advance the temporary iterator
  5. Stop the loop when the iterator has gone off the end of the List
  6. Return the resulting String
     /**
   * List with each value on its own line
   * At the end of the List a new line
   * @return the List as a String for display
   */
    @Override public String toString() {
        String result = "";
        Node temp = first;
        while(temp != null) {
            result += temp.data + " ";
            temp = temp.next;
        }
        return result + "\n";
    }
  • If you do not understand the above code, work through an example on paper, like the one shown below:
linked list containing A, B, C, D

  • Now, write a test for toString() by displaying the empty List we just created. Note that toString should print only a blank line in this case.
/**
 * Class to test List.java
 * @author
 * @author
 */
public class ListTest {
    public static void main(String[] args) {
        List<Integer> L = new List<>();
        System.out.println("Should print nothing (an empty list): " + L);      
       }

   }

Mutator: addFirst

  • Now let's write the addFirst method to start adding data to our list.
  • Remember that addFirst inserts a new Node in front of the first node in the list each time it is called, effectively creating a new front of the list.
  • Therefore, if I were to call addFirst(6); and then call addFirst(4); 4 will be the data at the start of the list after those two calls.
  • We need to consider two cases here:
  1. The list is empty (edge case)
  2. The list has one or more Nodes (general case)
  • Why do I need to treat the empty List differently?
  • Remember: when writing your List procedures, it is very important to take into account the "edge" cases, such as an empty list.
  • In the case the List is empty, we will have to write some additional code to handle this situation.
    • We need to make a new Node and then ensure that both the first and last Nodes point to this new Node.
    • After all, if there is just a single Node in the list, this Node is both first and last Node of the List.
  • However, if there is already one or more Nodes in the List, all we need to worry about is updating first.
  • The pseudocode is as follows:
  1. If the list is empty, <--edge case
    1. Create a new Node 
    2. Set first and last to point to this Node.
  2. Otherwise: <--general case
    1. Create a new Node
    2. Set the next variable of the new Node to point to the beginning of the list
    3. Set first to point to the new Node
  3. Increment the length of the list (this will happen in either case)


   /**
   * Creates a new first element
   * @param data the data to insert at the
   * front of the list
   * @postcondition
   */
    public void addFirst(T data) {
        if (first == null) {
            first = last = new Node(data);
        } else {
            Node N = new Node(data);
            N.next = first;
            first = N;
        }
        length++;
    }
  • Now, test your method.
  • Make sure to test the edge case : insertion when the List is empty
  • Also test the general case: insertion when the List has one or more elements in it
  • When you are finished, your ListTest.java should look like this:
/**
 * Class to test List.java
 * @author
 */
public class ListTest {
    public static void main(String[] args) {
        List<Integer> L = new List<>();
        System.out.println("Should print nothing (an empty list): " + L);
       
        System.out.println("**Testing addFirst**");
        L.addFirst(2); //Testing Edge case: length == 0
        System.out.println("Should print 2: " + L);
        L.addFirst(1); //Testing General case: length >= 1
        System.out.println("Should print 1 2: " + L);

       
    }

}


Mutator: addLast

  • AddLast is similar to addFirst, but not identical. 
  • Try drawing this process out for yourself on a sheet of paper.
  • Re-draw the below diagram and then manually update the important arrows.
  • When you are finished, test your method inside of ListTest.java using the model provided in the section above.
  • Make sure you test both cases - edge case and general case
  /**
   * Creates a new last element
   * @param data the data to insert at the
   * end of the list
   * @postcondition
   */
    public void addLast(T data) {
        if (first == null) {
            first = last = new Node(data);
        } else {
            Node N = new Node(data);
            last.next = N;
            last = N;
        }
        length++;
    }


Mutator: removeFirst

  • Now let's write the removeFirst method to remove data from the list.
  • Remember that removeFirst removes the data at the front of the list.
  • After a call to removeFirst, the second node in the list will have become the first.
  • We will temporarily handle the precondition using a print statement, until we cover assertions next lecture
  • We need to consider three cases here:
  1. The List is empty <-- nothing to remove (precondition)
  2. The List has only one Node (edge case)
  3. The List has more than one Node (general case)
  • Reflection: Why do I need to write different code for the case where the List has only one Node?
  • The pseudocode is as follows:
  1. If the List is empty,
    1. throws a NoSuchElementException
  2. If the List has one node
    1. Return the list to its empty state, where first and last are null and the length is 0
    2. Automatic garbage collection will remove the Node
  3. If the List has more than one Node
    1. Advance the first reference variable to link to the second Node.
  • The below image depicts the third case of removeFirst, where there are multiple Nodes in the list.

  • Below is the code for removeFirst:
     /**
     * removes the element at the front of the list
     * @precondition
     * @postcondition
     * @throws
NoSuchElementException when precondition is violated
     */
    public void removeFirst() throws
NoSuchElementException{
        if (length == 0) {
            throw new
NoSuchElementException("removeFirst(): Cannot remove from an empty List!");
        } else if (length == 1) {
            first = last = null;
        } else {
            first = first.next;
        }
        length--;

       }

  • Now, make sure you test all three cases (if, else if, and else) in ListTest.java.
  • Your ListTest.java should now look something like this:
/**
 * Class to test List.java
 * @author
 */
public class ListTest {
    public static void main(String[] args) {
        List<Integer> L = new List<>();
        System.out.println("Should print nothing (an empty list): " + L);
        
        System.out.println("**Testing addFirst**");
        L.addFirst(2);
        System.out.println("Should print 2: " + L);
        L.addFirst(1);
        System.out.println("Should print 1 2: " + L);
        
        //Code to test addLast goes here!
        
        System.out.println("**Testing removeFirst**");
        L.removeFirst(); //Testing General case: length >1
        System.out.println("Should print 2: " + L);
        L.removeFirst(); //Testing Edge case: length == 1
        System.out.println("Should print an empty List: " + L);
        System.out.println("Should an error message for an empty List: ");
        try { //place in a try-catch so program does not end when exception thrown
            L.removeFirst(); //Testing Precondition: length == 0
        } catch(NoSuchElementException e) {
            System.out.println(e.getMessage());
        }
 
    }

}

Mutator: removeLast

  • RemoveLast is similar to removeFirst, but also trickier.
  • There is no easy way to access the second to last node in the list. Do you see why?
    • You need a loop to advance a temp Node up to the second to last Node.
    • Then, you can remove the last Node and reset the last to point to the second-to-last Node
   /**
   * removes the element at the end of the list
   * @precondition
   * @postcondition 
   * @throws NoSuchElementException when precondition is violated
   */
    public void removeLast throws
NoSuchElementException {
        if (length == 0) {
            throw new NoSuchElementException("removeLast: list is empty. Nothing to remove.");
        } else if (length == 1) {
            first = last = null;
        } else {
            Node temp = first;
            while (temp.next != last) {
                temp = temp.next;
            }
            last = temp;
            last.next = null;
        }
        length--;
    }


  • If you do not understand the above code, work through an example on paper, like the one shown below:
linked list containing A, B, C, D

Writing the List Access Methods

  • Access methods provide information about the current state of the data structure.
  • Access methods typically have preconditions that we must account for as part of the method. We will discuss this concept in more detail during the next class.

Accessor: isEmpty

  • Writing access methods is generally pretty straightforward, involving just a few lines of code at most.
  • For example, let's look at the isEmpty() method, whose purpose is to return whether the list is empty using a boolean.
  • This method doesn't require a precondition. It is thus possible to write this method in a single line of code.
  • Here is the pseudocode:
  1. Return the whether the length is 0

/**
* Returns whether the list is currently empty
* @return whether the list is empty
*/
 public boolean isEmpty() {
     return length == 0;
 }

  • Now test this method.
  • You should test it twice as there are two possible cases.
    • What are they?

/**
 * Class to test List.java
 * @author
 * @author
 */
public class ListTest {
    public static void main(String[] args) {
        List<Integer> L = new List<>();
        System.out.println("Should print nothing (an empty list): " + L);
       
        System.out.println("**Testing addFirst**");
        L.addFirst(2);
        System.out.println("Should print 2: " + L);
        L.addFirst(1);
        System.out.println("Should print 1 2: " + L);
       
        //Code to test addLast goes here!
       
        System.out.println("**Testing removeFirst**");
        L.removeFirst();
        System.out.println("Should print 2: " + L);
        L.removeFirst();
        System.out.println("Should print an empty list: " + L);
        System.out.println("Should an error message for an empty List: ");
        try {
            L.removeFirst();
        } catch(NoSuchElementException e) {
            System.out.println(e.getMessage());
        }
        //Tests for removeLast go here!
       
        System.out.println("**Testing isEmpty**");
        List L2 = new List();
        System.out.println("Should print true: " + L2.isEmpty());
        //add another test for isEmpty() here!

       
    }

}


Accessor: getLength()

  • The getLength method can also be written in just one line of code.
  • Its purpose is to return the current length of the List - i.e. the total number or elements currently being stored.
   /**
     * Returns the current length of the list
     * @return the length of the list from 0 to n
     */
    public int getLength() {
        return length;
    }

  • Now test this method. Try writing a test for when the List is empty and when it is not.
  • Note that when the List is empty, getLength should simply return 0.


Accessor: getFirst()

  • The purpose of the getFirst access method is to return the data that is currently stored at the start of the List.
  • For example, what will getFirst return given the below List?
    linked list containing A, B, C, D
  • Hint: the correct answer is "A".
  • Copy and paste the below code into your List class:
      /**
     * Returns the value stored in the first node
     * @precondition
     * @return the value stored at node first
     * @throws
NoSuchElementException when the precondition is violated
     */
    public T getFirst() throws
NoSuchElementException{
        if (length == 0) {
            throw new
NoSuchElementException("getFirst: List is Empty. No data to access!");
        }
        return first.data; //why do we return first.data and not first?
    }

  • Now test this method. What possible cases might there be?
  • What will happen if the precondition is violated?
  • Add some tests to ListTest.java to test getFirst like those shown below:
/**
 * Class to test List.java
 * @author
 * @author
 */
public class ListTest {
    public static void main(String[] args) {
        List<Integer> L = new List<>();
        System.out.println("Should print nothing (an empty list): " + L);
       
        System.out.println("**Testing addFirst**");
        L.addFirst(2);
        System.out.println("Should print 2: " + L);
        L.addFirst(1);
        System.out.println("Should print 1 2: " + L);

        System.out.println("**Testing getFirst**");
        System.out.println("Should print 1: " + L.getFirst()); //testing general case
        List<String> 2 = new List<>();
        try { //testing precondition
            System.out.println("Should print error: " + L2.getFirst());
        } catch (NoSuchElementException e) {
            System.out.println(e.getMessage());
        }
       
        //Code to test addLast goes here!
       
        System.out.println("**Testing removeFirst**");
        L.removeFirst();
        System.out.println("Should print 2: " + L);
        L.removeFirst();
        System.out.println("Should print an empty list: " + L);
        System.out.println("Should an error message for an empty List: ");
        try {
            L.removeFirst();
        } catch(NoSuchElementException e) {
            System.out.println(e.getMessage());
        }
        //Tests for removeLast go here!
       
        System.out.println("**Testing isEmpty**");
        List L2 = new List();
        System.out.println("Should print true: " + L2.isEmpty());
        //add another test for isEmpty() here!
       
        //add tests for getLength() here!       
    }

}

Accessor: getLast()
  • getLast's purpose is to return the last element currently stored in the List.
  • For example, what will getLast return given the below List?
    linked list containing A, B, C, D
  • Hint: the correct answer is "D".
  • Copy and paste the below code into your List class:
      /**
     * Returns the value stored in the last node
     * @precondition
     * @return the value stored at node last
     * @throws
NoSuchElementException when the precondition is violated
     */
    public T getLast() throws
NoSuchElementException{
        if (length == 0) {
            throw new
NoSuchElementException("getLast: List is Empty. No data to access!");
        }
        return last.data; //why do we return last.data and not last?
    }

  • Now test this method. What possible cases might there be?
  • What will happen if the precondition is violated?

  • Save this List class to help you work through class examples and be ready to complete Lab 2.
  • Note that for Lab 2, we will update the singly-linked List class to be doubly-linked.