Welcome to CIS 22C!

By the end of today's class, you should know...
  1. Important policies and procedures for this class.
  2. The names of your instructor and some of your classmates.
  3. How to define an Abstract Data Type (ADT).
  4. The difference between an ADT and a Data Structure.
  5. What are the common ADT operations.
  6. How to define preconditions and postconditions.

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.


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 C++ 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, while your programming skills will improve greatly over this quarter, the bulk of our time will not be spent on learning more about C++.
  • 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!

Expect this course to be theoretical! This is not a programming course!


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 function, test it at least 3 times (3 function calls in main), write a function, 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.
  • Study for your weekly quizzes
  • Get started on assignments EARLY, preferably the night they are assigned. Do not wait until the night before or you will not have enough time to complete them. 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.



Abstract Data Types (ADTs) and Data Structures

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

  • ADTs are 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.
  • 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.

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 C++, including:
    • Linked Lists
    • Stacks
    • Queues
    • Binary Search Trees
    • Heaps
    • Graphs

ADT Operations

The operations that ADTs can perform on data typically fall into one of three categories:

    1. Access functions: These operations return information about the state of an ADT, but do not alter the state.
    • Access functions are often colloquially called "getters" because they "get" information for us.
    • For example, consider the following access function that is part of a class called Student.
    string Student::getName() const
  {
        return name;
  }
    • Notice how the above access function has a return type but no parameters.
    2. Manipulation procedures: These operations alter the state of the ADT, but do not return anything.
    • Manipulation procedures are often colloquially called "setters" because they set information for us.
    • For example, consider the following manipulation procedure that is part of a class called Student:
    void Student::setName(string student_name)
  {
      name = student_name;
  }
    • Notice how the above manipulation procedure has a parameter, but has a void return type.
    3. Constructors: These operations create a new instance of the ADT.
    • For example, consider the following constructor for a class called Student:
    Student::Student(string student_name, int student_id)
  {
        name = student_name;
        id = student_id;
  }
    • Notice how the constructor has NO return type, but can contain zero or more parameters.

There can be other operations as well.

Access functions, manipulation procedures and constructors should all be familiar to you from your experience with object oriented programming in your CIS 22B course.

Preconditions and Postconditions

  • Preconditions and post-conditions are specifications or requirements for the ADT operations.
  • Preconditions specify under what conditions an operation may be executed.
  • For example, consider a function to print the contents of an array to the console.
  • In order for this operation to be executed, the array must not be empty. 
  • Therefore, we make these specifications preconditions for our function, like so:

//pre: the array must not be empty 
void printArray(int array[], const int SIZE)
{
    if (SIZE == 0)
    {
        cout << "Array is empty! Nothing to print." << endl;
    }
    else
    {
        for (int i = 0; i < SIZE; i++)
        {
            cout << array[i] << " ";
        }
    }
}

  • Notice that we made the precondition into an if statement containing a printed an error message to the user.
  • What might be a precondition for the following function?
    //Calculates the square root of a number
    //pre: ???

    int square_root(int x);


  • Postconditions are conditions or specifications that must be met after a function has finished executing.
  • For example, let's assume we are writing a function that sets all values in an integer array to 0.
  • Our postcondition in this case is that when the function has finished executing, the array contains only 0s.
//pre: the array is not empty
//post: the array must contain only 0s
void zeroOutArray(int array[], const int SIZE)
{
    if (SIZE == 0)
    {
        cout << "Array is empty! Nothing to zero out." << endl;
    }
    else
    {
        for (int i = 0; i < SIZE; i++)
        {
            array[i] = 0;
        }
    }
}

ADT Design

  • In C++, an ADT is embodied in a class (often with inner classes or structs).
  • 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 fields or private inner classes and structs.
  • Instead, the user should only be allowed to manipulate data through the public functions.
  • An ADT should always be fully tested in isolation before it is used within a larger program.



Wrap Up
With a partner, answer the following questions:
  • What is an Abstract Data Type? What is the difference between an Abstract Data Type and a Data Structure?
  • True or false: A manipulation procedure is also known as a setter
  • Write an access function for the following class:

class Movie {

    private:
        string title;
        double price;

};
  • What might be a precondition for the following function?

//Calculates the square root of a number
//pre: ???

int square_root(int x);


~ See You Thursday! ~