Transcript Slide 1

Data Structures
Lecture 1: Introduction
Azhar Maqsood
NUST Institute of Information Technology (NIIT)
Administrative

Instructor: Azhar Maqsood
 [email protected]
 Extension: 136
 Academic Block 2, Faculty Office
 Web Address : http://www.niit.edu.pk/~azhar

Consulting hours:
 Tuesdays and Thursdays
 Depends on your schedule

Email me and get in touch if in need
 Regularly check course folder in FileSvr and My
website
Course Contents

Data Types






Overview, Introductory concepts
Data Types, meaning and implementation
Abstract data types (ADT)
Arrays (revisited)
Structures
Linked Lists
 Stacks (recursion)
 Queues
 Trees (traversals, implementation)
Course Contents

Binary Trees
 Indexing Methods
 Hashing

Binary Search Trees
 Balanced Search Trees
 (AVL Tree) Adelson-Velskii-Landis

Heaps
 Splay Trees
 Graphs, adjacency matrices and lists
Text book

“Data structures using C and C++”, Yedidyah
Langsam, Moshe J Augenstein and Aaron M.
Tenenbaum, 2 ed, 2002

Reference Books:
•
•
•
•
D. Wood: “Data structures, algorithms and performance”,
Addison-Wesley, 1993
C++ Data Structures by Nell Dale and David Teague
http://www.brpreiss.com/books/opus4/html/book.html
Any other book on Data Structures
Assignment Policy

DO NOT copy assignments
 Both of the copy cases will be graded zero

Submission time will be 1500 hrs on the due
date
 NO credit on LATE submission of any
deliverable.

No excuse of USB/Floppy/email servers not
working
 Sorry! No Exceptions
Weightage
OHT’s
 Quizzes
 Assignments
 Project
 Final Test


30% (15 +15)
10%
10%
5%
45%
Minimum Quizzes : 5-6 (Unannounced)
 Assignments
: 1 Every 3 weeks
Honor Code

Dishonesty will NOT be tolerated.
 Will result in zero marks in the corresponding
work
Lets start the course!
Why Study?

Designed to develop students understanding
the impact of structuring data to achieve
efficiency of a solution to a problem

After completion you will be familiar with
important and most often used data structuring
techniques.

It will enable you to understand the manner in
which data is organized and presented later.
Objectives of the course

Present in a systematic fashion the most
commonly used data structures, emphasizing
their abstract properties.
 Discuss typical algorithms that operate each
kind of data structure, and analyze their
performance.
 Compare different Data Structures for solving
the same problem, and choose the best
Abstract Data Type ADT

A data type whose properties (domain and
operations) are specified independently of any
particular implementation

ADT is a mathematical model which gives the
a set of utilities available to the user but never
states the details of its implementation.

In OO-Programming a Class is an ADT
Data Structures: Definition

A collection of data elements whose
organization is characterized by accessing
operations that are used to store and retrieve
the individual data elements;

The logical arrangement of data as used by a
system for data management; a representation
of a data model in computer form
Data Structures: More specifically
 A data structure is a way of grouping fundamental
types (like integers, floating point numbers, and
arrays) into a bundle that represents some
identifiable thing.
 For example, a matrix may be thought of as the bundle of
the number of rows and columns, and the array of values
of the elements of the matrix. This information must be
known in order to manipulate the matrix.
 C introduced the struct for declaring and
manipulating data structures. C++ extended the
struct to a class
Goals of Data structures

Identify and develop useful mathematical
entities and operations and to determine what
classes of problems can be solved by using
these entities and operations.

Determine representation of those abstract
entities and to implement the abstract
operation on these concrete representations.
A Real Life Example

Electronic Phone Book
Contains different DATA:
- names
- phone number
- addresses
Need to perform certain OPERATIONS:
- add
- delete
- look for a phone number
- look for an address
How to organize the data so to optimize the
efficiency of the operations








Lisa
Michele
John
110
622-9823
112-4433
75
Bronson
Paola
The first Data Structure

An Array!
Word about Arrays!

Lets Get Started:

Arrays are data structures





Finite
Contiguous
Fast
Direct Access
All elements of same data type
 (Can be based upon primitive or ADT)
 Insertion / Deletion ??? HOW?? 
Arrays

How to Input arrays
 How to process arrays
 How to insert an item in an array
 How to delete an item from an array
 How to pass an array
Array
2
3
7
8
How to add 4
2
3
4
7
8
How to add 1 in the array?
Not possible