CSC212

Data Structures
- Section AB
Lecture 1: Introduction
Instructor: Hao Tang
Tao Wang
Department of Computer Science
City College of New York
1

Course Web Page

You can find all the information at

ccvcl.org/~tang/cs212.html
-Come back frequently for updates of lecture schedule,
programming assignments and exam schedule
- Reading assignments & programming assignments

Outline of this lecture

Course Objectives and Schedule

WHAT (Topics)
WHY (Importance)
WHERE (Goals)
HOW (Information and Schedule)

The Phase of Software Development

Basic design strategy

Pre-conditions and post-conditions
Running time analysis
3

Topics (WHAT)

Data Structures

specification, design, implementation and use of

OOP and C++

C++ classes, container classes , Big Three

Standard Template Library (STL)

basic data types (arrays, lists, queues, stacks, trees)

templates, iterators
ADTs in our DS course cut-down version of STL

Recursion, Searching and Sorting Algorithms

important techniques in many applications

4

Importance (WHY)

Data Structures (how to organize data) and

Algorithms (how to manipulate data) are the cores of
todays computer programming

The behavior of Abstract Data Types (ADTs) in our

Date Structures course is a cut-down version of
Standard Template Library (STL) in C++

Lay a foundation for other aspects of real

programming OOP, Recursion, Sorting, Searching
5

Goals (WHERE)
understand the data types inside out

Implement these data structures as classes in C++

Determine which structures are appropriate in
various situations
Confidently learn new structures beyond what is
presented in this class
also learn part of the OOP and software
development methodology

Course Information (HOW)

Objectives
Data Structures, with C++ and Software Engineering

Textbook and References

Texbook: Data Structures and Other Objects Using C++ , Third Edition by Michael Main

Prerequisites

CSc102 C++ (Intro to Computing), CSc 104 (Discrete Math Structure I)

Assignments and Grading

and Walter Savitch

Reference: C++ How to Program by Dietel & Dietel, 3rd Ed., Prentice Hall 2001

6-7 programming assignments roughly per weeks (30%)

3 in-class written exams (60%), several in-class quizzes (10%)

Computing Facilities

PCs: Microsoft Visual C++ ; Unix / Linux : g++; MinGW; codeblocks(free)

also publicly accessible at Computer Science labs
7

Tentative Schedule (HOW)

(28 classes = 22 lectures + 3 reviews + 3 exams + 6-7 assignments)

Lecture 1.
The Phase of Software Development (Ch 1)
Lectures 2-3. ADT and C++ Classes (Ch 2)
Lecture 4-5.
Container Classes (Ch 3)
Lectures 6-8. Pointers and Dynamic Arrays (Ch 4)
Reviews and the 1st exam (Ch. 1-4)
Lectures 9-10. Linked Lists (Ch. 5)
Lectures 11. 11a. Template and STL (Ch 6)
Lecture 12.
Stacks (Ch 7) and Queues (Ch 8)
Lectures 13-14. Recursion (Ch 9)
Reviews and the 2nd exam (Ch. 5-9)
Lectures 15-18. Trees (Ch 10, Ch 11)
Lectures 19-20. Searching and Hashing (Ch 12)
Lectures 21- 22. Sorting (Ch 13)
Lecture 23. Graphs (Ch 15)
Reviews and the 3rd exam (mainly Ch. 10-13, ~July 23 or 24)
8

Tentative Schedule (cont.)

Exams
Whole

class

Quizzes
5-15

minutes in class

Talks

(not directly related to DS, but help

you to broaden your vision)
Guests

from Vision & Robotics lab and outside

CCNY
Topics including Machine Learning, Computer
Vision, HCI, Robotics and Visualization.

Outline

Course Objectives and Schedule

Information
Topics
Schedule

The Phase of Software Development

Basic design strategy

Pre-conditions and post-conditions
Running time analysis
10

Phase of Software Development

Basic Design Strategy four steps (Reading: Ch.1 )

Specify the problem - Input/Output (I/O)
Design data structures and algorithms (pseudo code)
Implement in a language such as C++
Test and debug the program (Reading Ch 1.3)

Design Technique

Decomposing the problem

Two Important Issues (along with design and

Implement)

Pre-Conditions and Post-Conditions

Running Time Analysis
11

Preconditions and Postconditions

An important topic: preconditions and

postconditions.

They are a method of specifying what a

function accomplishes.

Precondition and Postcondition Presentation copyright 1997, Addison Wesley Longman

For use with Data Structures and Other Objects Using C++ by Michael Main and Walter Savitch.

12

Preconditions and Postconditions

Frequently a programmer must communicate
precisely what a function accomplishes,
without any indication of how the function
does its work.

Can you think of a situation

where this would occur ?
13

Example

You are the head of a

programming team
and you want one of
your programmers to
write a function for
part of a project.

HERE ARE
THE REQUIREMENTS
FOR A FUNCTION THAT I
WANT YOU TO
WRITE.

I DON'T CARE
WHAT METHOD THE
FUNCTION USES,
AS LONG AS THESE
REQUIREMENTS
ARE MET.

14

What are Preconditions and

Postconditions?
One

way to specify such requirements is

with a pair of statements about the function.
The precondition statement indicates what
must be true before the function is called.
The postcondition statement indicates what
will be true when the function finishes its
work.

15

Example
void write_sqrt( double x )
// Precondition: x >= 0.
// Postcondition: The square root of x has
// been written to the standard output.

...
16

Example
void write_sqrt( double x)
// Precondition: x >= 0.
// Postcondition: The square root of x has
// been written to the standard output.

The precondition and

postcondition appear as
comments in your program.
They are usually placed after the
functions parameter list.

...

17

Example
void write_sqrt( double x)
// Precondition: x >= 0.
// Postcondition: The square root of x has
// been written to the standard output.

In this example, the precondition

requires that
x >= 0
be true whenever the function is
called.

...
}

18

Example
Which of these function calls
meet the precondition ?
write_sqrt( -10 );
write_sqrt( 0 );
write_sqrt( 5.6 );

19

Example
Which of these function calls
meet the precondition ?
write_sqrt( -10 );
write_sqrt( 0 );
write_sqrt( 5.6 );
The second and third calls are fine, since
the argument is greater than or equal to zero.

20

Example
Which of these function calls
meet the precondition ?
write_sqrt( -10 );
write_sqrt( 0 );
write_sqrt( 5.6 );
But the first call violates the precondition,
since the argument is less than zero.

21

Example
void write_sqrt( double x)
// Precondition: x >= 0.
// Postcondition: The square root of x has
// been written to the standard output.

The postcondition always indicates

what work the function has
accomplished. In this case, when
the function returns the square root
of x has been written.

...

22

Another Example
bool is_vowel( char letter )
// Precondition: letter is an uppercase or
// lowercase letter (in the range 'A' ... 'Z' or 'a' ... 'z') .
// Postcondition: The value returned by the
// function is true if letter is a vowel;
// otherwise the value returned by the function is
// false.

...
23

Another Example
What values will be returned
by these function calls ?
is_vowel( 'A' );
is_vowel(' Z' );
is_vowel( '?' );

24

Another Example
What values will be returned
by these function calls ?
is_vowel( 'A' );
is_vowel(' Z' );
is_vowel( '?' );

true

false

Nobody knows, because the

precondition has been violated.
25

Consequence of Violation
Who is responsible for the crash ?

write_sqrt(-10.0);
is_vowel( '?' );

Bring up Slide Notes!!!

Violating the precondition

might even crash the computer.
26

Always make sure the

precondition is valid . . .

The programmer who

calls the function is
responsible for
ensuring that the
precondition is valid
when the function is
called.
AT THIS POINT, MY
PROGRAM CALLS YOUR
FUNCTION, AND I MAKE
SURE THAT THE
PRECONDITION IS
VALID.
27

. . . so the postcondition becomes

true at the functions end.

The programmer who

writes the function counts
on the precondition being
valid, and ensures that the
postcondition becomes
true at the functions end.

THEN MY FUNCTION
WILL EXECUTE, AND WHEN
IT IS DONE, THE
POSTCONDITION WILL BE
TRUE.
I GUARANTEE IT.

28

A Quiz
The famous skyline was
dark on Aug 14th, 2003.

Suppose that you call a

function, and you neglect to
make sure that the
precondition is valid.
Who is responsible if this
inadvertently causes a 1-day
long blackout in NYC or
other disaster?

You
The programmer who
wrote that Power
Supply function
Mayor Bloomberg

Outside of Penn Station

29

A Quiz
Suppose that you call a
function, and you neglect to
make sure that the
precondition is valid.
Who is responsible if this
inadvertently causes a 1-day
long blackout in NYC or
other disaster?

You
The programmer who
calls a function is
responsible for
ensuring that the
precondition is valid.

Outside of Penn Station

30

On the other hand, careful

programmers also follow these rules:
When

you write a function, you should

make every effort to detect when a
precondition has been violated.
If you detect that a precondition has been
violated, then print an error message and
halt the program.

31

On the other hand, careful

programmers also follow these rules:
When

you write a function, you should

make every effort to detect when a
precondition has been violated.
If you detect that a precondition has been
violated, then print an error message and
halt the program...
...rather than causing
a chaos.

The famous skyline was

dark on Aug 14th, 2003.
32

Example
void write_sqrt( double x)
// Precondition: x >= 0.
// Postcondition: The square root of x has
// been written to the standard output.
{
assert(x >= 0);

...

The assert function

(described in Section 1.1) is
useful for detecting violations
of a precondition.
33

Advantages of Using Pre- and Post-conditions

Concisely

describes the behavior of a

function...
... without cluttering up your thinking with
details of how the function works.
At a later point, you may reimplement the
function in a new way ...
... but programs (which only depend on the
precondition/postcondition) will still work
with no changes.
34

Break

35

Summary of pre- and post-conditions

Precondition
The programmer who calls
a function ensures that the
precondition is valid.
The programmer who
writes a function can bank
on the precondition being
true when the function
begins execution.

Postcondition
The programmer
who writes a
function ensures
that the
postcondition is
true when the
function finishes
executing.

36

Phase of Software Development

Basic Design Strategy four steps (Reading: Ch.1 )

Specify Input/Output (I/O)
Design data structures and algorithms
Implement in a language such as C++
Test and debug the program (Reading Ch 1.3)

Design Technique

Decomposing the problem

Two Important Issues (along with design and

Implement)

Pre-Conditions and Post-Conditions

Running Time Analysis
37

Running Time Analysis Big O

Time

Analysis

Fast enough?
How much longer if input gets larger?
Which among several is the fastest?

38

Example : Stair Counting Problem

How many steps ?

1789 (Birnbaum)
1671 (Joseph Harriss)
1652 (others)
1665 (Official Eiffel Tower Website)

Find

it out yourself !
Eiffel Tower

39

Example : Stair Counting Problem

Find it out yourself !

Method

1: Walk down and keep

a tally
Each time a step down, make a mark
Method

2 : Walk down, but let

Judy keep the tally

There
II
y a are

2689
2689
2689
steps in
marches
this
dan
cet

stairway
escalier
_______
_______
______
!
vraiment!
(really!)

Down+1, hat, back, Judy make a mark

Method

3: Jervis to the rescue

One mark per digit

Eiffel Tower

40

Example : Stair Counting Problem

How to measure the time?

Just measure the actual time

varies from person to person

depends on many factors

Count

certain operations

each time walk up/down, 1

operation
each time mark a symbol, 1
operation

Eiffel Tower

41

Example : Stair Counting Problem

Find it out yourself !

Method

1: Walk down and keep a tally

2689 (down) + 2689 (up) + 2689 (marks)

= 8067
Method

2 : Walk down, let Judy keep tally

Down: 3,616,705 = 1+2++2689

Up:

3,616,705 = 1+2++2689

Marks:
Method

7,236,099 !

2,689 = 1+1++1

3: Jervis to the rescue

only 4 marks !

Eiffel Tower42

Example : Stair Counting Problem

Size

of the Input : n

Method

1: Walk down and keep a tally

3n
Method

2 : Walk down, let Judy keep tally

n+2(1+2++n) = n+(n+1)n = n2+2n

Trick: Compute twice the amount

and then divided by two

Method

3: Jervis to the rescue

The number of digits in n = [log10 n]+1

Eiffel Tower43

Example : Stair Counting Problem

Big-O

Notation the order of the algorithm

Use

the largest term in a formula

Ignore the multiplicative constant
Method

1: Linear time

3n => O(n)
Method

2 : Quadratic time

n2+2n => O(n2)

Method

3: Logarithmic time

[log10 n]+1 => O(log n)

Eiffel Tower44

A Quiz
Number of operations

Big-O notation

n2+5n

O(n2)

100n+n2

O(n2)

(n+7)(n-2)

O(n2)

n+100

O(n)

number of digits in 2n

O(log n)

45

Big-O Notation
The

order of an algorithm generally is more

important than the speed of the processor

Input size: n O(log n)

O (n)

O (n2)

# of stairs: n [log10n]+1

3n

n2+2n

10

30

120

100

300

10,200

1000

3000

1,002,000
46

Time Analysis of C++ Functions

Example- Quiz ( 5 minutes)

Printout all item in an integer array of size N

for (i=0; i< N; i++ )
{
val = a[i];
cout << val;
}

2 C++
operations or
more?

Frequent linear pattern

A loop that does a fixed amount of operations N times

requires O(N) time
47

Time Analysis of C++ Functions

Another example
Printout char one by one in a string of length N
for (i=0; i< strlen(str); i++ )
{
c = str[i];
cout << c;
}

2
O(N )!

What is a single operation?

If the function calls do complex things, then count the
operation carried out there
Put a function call outside the loop if you can!

48

Time Analysis of C++ Functions

Another example

Printout char one by one in a string of length N

N = strlen(str);
for (i=0; i<N; i++ )
{
c = str[i];
cout << c;
}

O(N)!

What is a single operation?

If the function calls do complex things, then count the
operation carried out there
Put a function call outside the loop if you can!

49

Time Analysis of C++ Functions

Worst case, average case and best case

search a number x in an integer array a of size N

for (i=0; (i< N) && (a[i] != x); i++ );

if (i < N) cout << Number << x << is at location << i << endl;
else cout << Not Found! << endl;

Can you provide an exact number of operations?

Best case: 1+2+1
Worst case: 1+3N+1
Average case: 1+3N/2+1

50

Testing and Debugging

Test: run a program and observe its behavior

Choosing Test Data : two techniques

input -> expected output?

how long ?
software engineering issues
boundary values
fully exercising code (tool: profiler)

Debugging find the bug after an error is found

rule: never change if you are not sure whats the error
tool: debugger
51

Summary

Often ask yourselves FOUR questions

WHAT, WHY, WHERE & HOW

Topics DSs, C++, STL, basic algorithms

Data Structure experts
Schedule 21 lectures, 7 assignments, 3 exams
some credits (10) for attending the class
Information website

Remember and apply two things (Ch 1)

Basic design strategy

Pre-conditions and post-conditions
Running time analysis
Testing and Debugging (reading 1.3)
52

Reminder
Lecture 2: ADT and C++ Classes
Reading Assignment before the next lecture:
Chapter 1
Chapter 2, Sections 2.1-2.3
Office Hours: Mon, Wed 12 am 1 pm
(location: NAC 8/210)

53

Question and Survey

No

name!

Once

you finish, fold the paper.

54

THE END

55