1 of 33

CHAPTER 2

Introduction to Data Structures and Algorithm

NOTE: The material in this presentation is a compilation from the Zybook of “Principles of Data Structure”, the book “Data Structures and other objects using C++” by Michael Main and Walter Savitvch, and original content from your professor.

By Prof. Rafael Orta, M.S.

2 of 33

https://quizizz.com/

3 of 33

Last week we covered

NOTE: The material in this presentation is a compilation from the Zybook of “Principles of Data Structure”, the book “Data Structures and other objects using C++” by Michael Main and Walter Savitvch, and original material from your professor.

  • Data / Information
  • Data Structures
  • Software Development Lifecycle (SDLC)
  • Running time Analysis
  • Top-Down Design
  • Big O notation

4 of 33

Agenda for this week

NOTE: The material in this presentation is a compilation from the Zybook of “Principles of Data Structure”, the book “Data Structures and other objects using C++” by Michael Main and Walter Savitvch, and original material from your professor.

  • Data Structures.
  • Introduction to algorithms.
  • Relation between data structures and algorithms.
  • Abstracts Data types
  • Application of Abstract Data types.
  • Algorithm Efficiency.

5 of 33

What is a Data structure

A way of:

          • Organizing
          • Storing
          • Performing operations (What Operations?)

- Accessing

- Updating

- Searching

- Inserting new Data

- Removing Data

6 of 33

Basic Data Structures

7 of 33

Basic Data Structures

Options: Graph – Min heap tree – Max heap tree – Hash table – Binary Tree – Linked List – Array - Record

8 of 33

What C++ Abstract Data Type is very similar to a record

9 of 33

A/ A Struct

10 of 33

Live Demo

(Structs, Arrays & Vectors)

11 of 33

12 of 33

Introduction to Algorithms

“An algorithm describes a sequence of steps to solve a computational problem or perform a calculation. An algorithm can be described in English, pseudocode or a programming language among others.”

13 of 33

14 of 33

Introduction to Algorithms

“A computational problem specifies an input, a question about the input that can be answered using a computer, and the desired output..”

15 of 33

Introduction to Algorithms

Let’s work on this: What would be the gas cost for a trip from Philadelphia to Boston?

See C++ Code on my website

16 of 33

17 of 33

Relation between data structures and algorithms.

18 of 33

Abstracts Data Types

19 of 33

Abstract Data Types

Video

20 of 33

Applications of ADT’s

21 of 33

Can you explain the relationship between data structures and algorithms ?.

22 of 33

Algorithm Efficiency

23 of 33

Different Algorithms have different running times

Time (sec.)

Input size (n)

O(n)

O(n5)

O(log2 n )

24 of 33

Can you think of an algorithm whose �running time complexity is Big O(log n)?

25 of 33

Binary Search

In general, the worst-case scenario of a Binary Search is Log of n + 1. The Big O notation for Binary Search is O(log N). In contrast to O(N) which takes an additional step for each data element, O(log N) means that the algorithm takes an additional step each time the data doubles.

26 of 33

Sometimes you sacrifice efficiency for simplicity, specially if the problem is complex, in that case you select the best algorithm you can find, which may not be the absolute best.

27 of 33

Algorithm Efficiency

Video

28 of 33

29 of 33

30 of 33

What is the name of this data structure?.

31 of 33

A/ Linked List

32 of 33

Data Structures to watch at Home Video

33 of 33