Welcome to CIS 22C!


Learning Objectives

Upon completion of this lesson, you should know...
  • Important policies and procedures for this class.
  • The names of your instructor and some of your classmates.
  • How to define an Abstract Data Type (ADT).
  • The difference between an ADT and a Data Structure.
  • What are the common ADT operations.
  • How to define preconditions and postconditions.

1. Welcome to the Class!

  • Digital data is all around us! Think about it... How many times a day do you interact with digital data?



  • All of this data must be organized and made easily accessible if people are going to be able to use it in a meaningful way.
  • In this class we will learn how to organize and access digital data.


1.1. CIS 22C: Your First Real Course in Computer Science

  • In fact, CIS 22C will be your first real course in the discipline of Computer Science!
  • Sometimes Computer Science is equated to computers or computer programming.
  • However, Computer Science is no more about programming than astronomy is about telescopes or biology is about microscopes.
  • Computer programming and the Java language are merely a tools that are used in Computer Science.
  • Instead, the field of Computer Science focuses on how to organize, store, retrieve, and process data in an efficient way
  • Thus, it is assumed that you have gained the requisite programming skills by completing CIS 36B or CIS 35A before taking this course.
  • Now, the focus of this class will be on applying your Java skills in new ways - i.e. by writing a variety of data structures.
  • If your goal is a career in the software industry, this course will be your best friend: What you will learn here will be very useful in any future interviews.
  • My goal for this class is for you to work hard, learn a lot and have some fun along the way!


2. Tips for Success

  • Expect this course to be a significant time commitment
    • At least 12-15 hours a week of homework and study time 
    • Expectation: You will be simultaneously doing weekly homework, working on your project and studying for tests and exams.
    • Do not take this course if you are already taking 3 other classes or have an intensive work schedule!
    • Do not take this class if you are looking for an easy class.
  • I will be reviewing your code in detail and testing it!
    • To avoid loss of points, make sure to test your own code before I do so that you discover the mistakes first
    • Test every situation you can think of
    • You should be coding like this: Write a method, test it at least 3 times (3 method calls in main), write a method, test it at least 3 times...
    • No credit for code that doesn't compile. Please make sure ALWAYS to turn in a version that compiles.
  • You will be expected to watch all video lessons and answer the questions in the online discussions.
  • Study for your weekly quizzes
  • Get started on assignments EARLY -- preferably the night they are assigned -- and leave time to get lots of help!
    • Do not wait until the night before or you will not have enough time to complete your labs.
    • The assignments in this class are designed to be challenging.
    • If I give you a week to complete an assignment, it is because I expect it to take you the whole week.
    • Getting started early leaves lots of time to ask for help at multiple steps along the way.
  • UNDERSTAND the code you submit.
    • Don't just copy code off the internet.
    • Don't let someone else write the programs for you. If your partner writes a portion of the code, make sure you understand and agree.
    • Work on your programs together with your partner.
    • On your exams, I will be verifying that you understand and can implement the code from the assignments, as well as the concepts discussed in class.

3. Introductions

  • Midterm 1: Friday, October 19 - 12:00pm to 2:00pm in ATC 204
  • Midterm 2: Friday, November 16 - 12:00pm to 2:00pm in ATC 204
  • Final: Friday, December 14 - 12:00pm to 2:00pm in ATC 204
  • No makeup exams will be offered!
  • Please be prepared to show your valid government-issued photo ID or De Anza student ID to be allowed to take the exam.
    • Build your own social network with a friend recommendation system!
    • Start on Teams of 5-6 people
    • You will choose teams in week 3 using the discussion forum
    • Project due on the Monday of finals week (see course schedule)
    • Deadlines throughout the quarter for project reports (see course schedule)


3.1 How to Navigate this Class

  1. De Anza Canvas: Weekly Summary containing Lesson Videos, Submission of Assignments
  2. Course Website: Lesson Notes, Schedule, Assignment Descriptions, Project Description, Readings, Resources
  3. Piazza: Discussion Forum for Assignment and Lecture Questions
    • Get Help from the Instructor, TA and other students!


4. Steps for Developing Software

  • When writing a program, you should not simply sit down and start typing away on the keyboard.
  • Instead, the best written code starts with a planning phase and ends with significant testing and revision of the program.
  • Let's consider one simple approach to writing software, which involves following the 4 steps below
    1. Specification Phase - Formulating a precise description of the problem
    2. Design Phase - Formulating the steps to be taken to solve the problem
    3. Implementation Phase - Writing the code following your design
    4. Testing and Revision of Code - Considering all possible ways a user might interact with our program. We should test our own code but also watch other people test our code.
  • Note that implementation and testing phases should be implemented concurrently.
  • In other words, after you write each method, you should test it thoroughly before writing the next method.
  • We will be following the above steps when writing software for this class.
  • Before we begin writing a class, we will formulate what is known as the Abstract Data Type (ADT).

5. Abstract Data Types (ADTs) and Data Structures

5.1. Abstract Data Types (ADTs)

  • What comes to mind when you think of the title of this course "Data Abstraction and Structures"?
    • We will be studying a variety of "Abstract Data Types"
  • The definition of an Abstract Data Type or ADT is:
    •  a collection of data
    • a set of operations that can be performed on that data.
  • The word "Abstract" in ADT comes from an important concept in computer science called Abstraction
    • Abstraction is concerned with what you can do, not how you do it.
    • It allows you to think in terms of the "big ideas" without worrying about the specifics of how to implement them
    • A short video explaining abstraction
    • How does the below image relate to the idea of an abstraction? How does the veterinarian see the cat compared to how the cat's companion sees the cat?

mira2

Image source

  • An ADT is defined by the data that it holds and the operations you can perform on the data. It is not defined by any specific implementation.
  • In other words, you or another user could apply operations to data without knowing how the system you are interacting with was built or how it is able to do what it does.
  • For example, consider the address book on your phone.
  • The address book holds a collection of data (the names, numbers and email addresses of friends and family).
  • It also has a set of operations that can be performed, such as adding a new contact, searching for a contact or updating an existing contact.
  • You can use your phone's address book without knowing how the program was written (abstraction).

You can think of your phone's address book as an ADT. Image source.
  • An Abstract Data Type is a theoretical concept - how to understand the data and their operations.
    • Defining an ADT is an important part of the specification and design phases of writing software.
  • Besides the phone address book example, can you think of other examples of ADTs that you might have encountered?
  • A specific implementation of the ADT is called a Data Structure.
  • An ADT is most often embodied in a class.

5.2. Data Structures

  • If you wanted to build the ADT yourself, then you would implement it using what is called a Data Structure. 
  • A Data Structure is an implementation of an ADT that is written using a particular programming language and can store a specific collection of data.
  • Before you implement the data structure, it is important to think first in terms of an ADT:
    • What kind of data will it hold?
    • What will you be able to do with this data?
  • Only then should you begin to think of the implementation details and write the data structure.
  • We will be learning about many common ADTs in this class and you will be writing their data structures in Java, including:
    • Linked Lists
    • Stacks
    • Queues
    • Binary Search Trees
    • Heaps
    • Graphs
    • Hash Tables

5.3. ADT Operations

The operations that ADTs can perform on data typically fall into one of the following categories:
  1. Accessors -- access information about the state of the ADT, but do not alter the state
  2. Mutators -- alter the state of the ADT
  3. Constructors -- create a new instance of the ADT
  4. Additional Operations -- any other operations that do not fall into the above 3 categories (e.g. display)

5.4. Writing a Data Structure - Implementing the ADT Operations as Part of Your Class

  • Just as the embodiment of an ADT is a class, the embodiment of an ADT operation is a method.
  • Each of the above operations can be implemented as one of the following types of methods:

    1. Access Methods: These methods return information about the private variables of the class, but do not alter them.
    • Access methods are often colloquially called "getters" because they "get" information for us.
    • For example, consider the following access method that is part of a class called Student.
    public String getName()
  {
        return name;
  }
    • Notice how the above access function has a return type but no parameters.
    • The "classic" implementation of an access method will have no parameters, although there are exceptions to this general rule.
    2. Mutator Methods: These operations alter the state of the private variables, but do not return anything.
    • Mutators are often colloquially called "setters" because they set the value of a private variable.
    • For example, consider the following manipulation procedure that is part of a class called Student:
    public void setName(String student_name)
  {
      name = student_name;
  }
    • Notice how the above mutator has a parameter, but has a void return type.
    • The "classic" implementation of a mutator method will return nothing, although there are exceptions to this general rule.
    3. Constructors: These operations create a new instance of the class.
    • For example, consider the following constructor for a class called Student:
    public Student(String student_name, int student_id)
  {
        name = student_name;
        id = student_id;
  }
    • Notice how the constructor has NO return type, must be named identically to the name of the class, and can contain zero or more parameters.
    4. Additional Operations: These methods do not fall within one of the above categories.
  • For example, consider a print or display method for a class called Student
      public void printStudentInfo()
      {
          System.out.println("Name: " + name
                + "\nID #: " + id);
      }
  • A better way to do this in Java would be to override the toString() method for the class:
@Override
public String toString() {
        return "Student: " + name + "\nID: " +
                id + "\nGPA: " + gpa;
}



Access functions, mutators and constructors should all be familiar to you from your experience with object oriented programming in your CIS 36B or CIS 35A course.

5.5. ADT Design Summary

  • In Java, an ADT is embodied in a class (often with inner classes).
  • A class contains fields (or member variables) and functions which implement the ADT operations.
  • Thus, ADT design should come naturally from Object Oriented Design.
  • The user of an ADT should never be able to access the private fields or inner classes.
  • Instead, the user should only be allowed to manipulate or access data through the public methods.
  • An ADT should always be fully tested in isolation before it is used within a larger program.

5.6. Specifications: Preconditions and Postconditions

  • Preconditions and post-conditions are specifications or requirements for a method.

Preconditions

  • Preconditions specify under what conditions a method may be executed.
  • For example, consider the below method:
      /**
    * A method to access the name of a student at a specific
    * position on the course roster
    * @param classRoster a list of student names in CIS 22C
    * @param studentNum a numerical position on the roster,
    * from 0 to 44, i.e. an index number in the array
    * @return the name of the student at position studentNum
    */

public String getStudent(String classRoster[], int studentNum)
{
return classRoster[studentNum];
}
  • What must be the precondition for this method?
    • studentNum must be => 0 and also < the length of the array, or there will be an ArrayIndexOutOfBoundsException at runtime.
  • We must make three changes to the method to handle this precondition:
  1. Note the precondition in the comment
  2. Update the signature of the method to throw an exception
  3. Handle the precondition inside the method using an if statement
    /**
    * A method to access the name of a student at a specific
    * position on the course roster
    * @param classRoster a list of student names in CIS 22C
    * @param studentNum a numerical position on the roster,
    * from 0 to 44, i.e. an index number in the array
    * @precondition 0 <= studentNum < classRoster.length
    * @return the name of the student at position studentNum
    * @throws IndexOutOfBoundsException indicating that
    * studentNum is outside the bounds of the classRoster array
    */
    public String getStudent(String classRoster[], int studentNum)
            throws IndexOutOfBoundsException
  {
        if (studentNum < 0 || studentNum >= classRoster.length) {
            throw new IndexOutOfBoundsException(studentNum
                    + " is outside the bounds of the array in getStudent");
        }
        return classRoster[studentNum];
  }
  • What might be a precondition for the following method?

/**
* calculates the square root of a number
* @param x the number of which to take the square root
* @precondition ***You fill in here***
* @return the square root of the number x
* @throws IllegalArgumentException
* ***You fill in here***
*/
public static double square_root(double x)
    throws IllegalArgumentException{
    //implementation of method
}

Postconditions

  • Postconditions are conditions or specifications that must be met after a method has finished executing.
  • Let's consider another method involving the same array of names from a class roster.
  • In this case, the purpose of the method is to update a student name on the roster.
/**
* A method to update the name of a student at a specific
* position on the course roster
* @param classRoster a list of student names in CIS 22C
* @param studentNum a numerical position on the roster,
* from 0 to 44, i.e. an index number in the array
* @param newName the new value to assign at the specific
* index
* @precondition 0 <= studentNum < classRoster.length
* @return the name of the student at position studentNum
* @throws IndexOutOfBoundsException indicates that
* studentNum is outside the bounds of the classRoster array
* @postcondition fill in here
*/
public void updateStudentName(String classRoster[], int studentNum, String newName)
throws IndexOutOfBoundsException {
if (studentNum < 0 || studentNum >= classRoster.length){
throw new IndexOutOfBoundsException(studentNum
+ " is outside the bounds of the array in removeStudent"
}
classRoster[studentNum] = newName;
}
  • Our postcondition in this case is that the element at the specified index has been updated
  • We note the postcondition inside the comments for the method, and then ensure that the method executes as promised in the postcondition
/**
* A method to update the name of a student at a specific
* position on the course roster
* @param classRoster a list of student names in CIS 22C
* @param studentNum a numerical position on the roster,
* from 0 to 44, i.e. an index number in the array
* @param newName the new value to assign at the specific
* index
* @precondition 0 <= studentNum < classRoster.length
* @return the name of the student at position studentNum
* @throws IndexOutOfBoundsException indicates that
* studentNum is outside the bounds of the classRoster array
* @postcondition the class roster at position studentNum
* has been assigned a new value
*/
public void updateStudentName(String classRoster[], int studentNum, String newName)
throws IndexOutOfBoundsException {
if (studentNum < 0 || studentNum >= classRoster.length){
throw new IndexOutOfBoundsException(studentNum
+ " is outside the bounds of the array in removeStudent"
}
classRoster[studentNum] = newName;
}

5.7. Common Java Exceptions

  • Below is a summary of four commonly used exceptions.
  • Click on the name of the exception to see the Oracle documentation.
 Exception When to Use It
 IllegalArgumentExceptionThe argument passed to the method is inappropriate
 IllegalStateExceptionInappropriate to call this method given object's current state
 NullPointerExceptionApplication attempts to use null where an object is required
 IndexOutOfBoundsExceptionIndex parameter value is out of range for a collection
  • How to use exceptions in your code?
    • Update the method signature to indicate the method throws an exception
public static double squareRoot(double x) 
    throws IllegalArgumentException { ... }
  • Throw the exception when the precondition is violated
public static double squareRoot(double x) 
    throws IllegalArgumentException {
    if (x < 0) {
        throw new IllegalArgumentException("x cannot be negative!");
    }
    //rest of method
}
  • Give your own error message to tell user what went wrong inside of the parenthesis of the exception. Make sure it is a descriptive error message.


Wrap Up
  • Answer the review questions on Canvas for today's lesson



Upcoming Assignments
  • Lab 0 due Friday at midnight on Canvas