ALGORITHMS AND DATA STRUCTURES
7th Feb, 2013
Lecture No. 1
Books to Follow
Data Structure using C and C++ by Aaron Tanenbaum, Yedidyah Langsam An introduction to Data Structures with Applications by Jean-Paul Tremblay, Paul G. Sorenson. Data Structures and Program Design in C++ by Robert L. Kruse,Alexander J. Ryba Data Structures and Algorithm Analysis in C by Mark Allan Weises.
Grading
Grading
Quiz
/ Assignment 1st Sessional 2nd Sessional Final Exam
25% 10% 15% 50%
Late Policy: Assignments will not be accepted later than the deadline.
Plagiarism Policy
Any assignment found 30% or more copied from the internet will be marked 0 (ZERO). Any assignment copied from the class mate will also be marked 0 (ZERO). No consideration will be made regarding plagiarized assignments.
Attendance Policy
Any student late in class by 15 min shall be marked absent.
Introduction to Data Structure
A data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently
What is Data Structure?
Data structure is a representation of data and the operations allowed on that data. A data structure is a way to store and organize data in order to facilitate the access and modifications. Data Structure is the method of representing logical relationships between individual data elements related to the solution of a given problem.
Fundamental Data Structures
Basic Data Structures Linear Data Structures
Array s Linked Lists Stack s Queue s
Non-Linear Data Structures
Graphs Tree s Hash Tables
Linear Data Structures
A data structure is said to be linear if its elements form a sequence or a linear list. Examples:
Arrays
Linked
Stacks
Lists
Queues
Non-Linear Data Structures
A data structure is said to be non-linear if its elements does not form a sequence or a linear list. Examples:
Trees
Graphs Hash
Tables
Each element may be connected with two or more other nodes or items in a non-linear arrangement.
Diagrammatic Representation of Data Structures
array
Linked list
tree
queue stack
Operations on Data Structures
Traversal: Travel through the data structure Search: Traversal through the data structure for a given element Insertion: Adding new elements to the data structure Deletion: Removing an element from the data structure Sorting: Arranging the elements in some type of order Merging: Combining two similar data structures into one
Linear Data Structures
Arrays Linked List Stacks Queues
Arrays
A sequence of n items of the same data type that are stored contiguously in computer memory and made accessible by specifying a value of the arrays index. Properties: fixed length (need preliminary reservation of memory) contiguous memory locations direct a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[0] access a[9] Insert/delete
1 2 3 4 5 6 7 8 9 10
Array a with 10 integer elements
Linked List
A sequence of zero or more nodes each containing two kinds of information: some data and one or more links called pointers to other nodes of the linked list. Properties
dynamic length arbitrary memory locations access by following links Insert/delete
Stacks
A stack is a data structure that uses last-in, firstout (LIFO) ordering and allows reading and writing on the top element only. Properties
insertion/deletion can be done only at the top LIFO
Two operations
Push Pop
Queues
Collection with access only to the item that has been present the longest Properties
Insertion/enqueue from the rear (back) and deletion/ dequeue from the front. FIFO
Two operations
Enqueue Dequeue
Front
20
30
10
60
57
29
Back
Non-Linear Data Structures
Graphs Trees Hash Tables
Graphs
A graph consists of an interconnected set of data items.
Graph
Trees
A Tree is a way of representing the hierarchical nature of a structure in a graphical form. Properties of trees
Root Node Child Node Parent Node Leave Node
Examples?
Abstract Data Type - ADT
Abstract Data Types (ADTs) stores data and allow various operations on the data to access and change it.
ADT and Data Structure
An ADT is a mathematical model, together with various operations defined on the model
Data Structures
Physical implementation of an ADT
data structures used in implementations are provided in a language (primitive or built-in) or are built from the language constructs (user-defined) Each operation associated with the ADT is implemented by one or more subroutines in the implementation
Abstract Data Type
ADTs support abstraction, encapsulation, and information hiding. Abstraction is the structuring of a problem into welldefined entities by defining their data and operations. The principle of hiding the used data structure and to only provide a well-defined interface is known as encapsulation.
The Core Operations of ADT
Every Collection ADT should provide a way to:
add an item remove an item find, retrieve, or access an item
Many, many more possibilities
is the collection empty make the collection empty give me a sub set of the collection
Algorithm
An algorithm is a well-ordered collection of unambiguous and effectively computable operations that, when executed, produces a result and halts in a finite amount of time.
Important features
well-ordered
unambiguous
and effectively computable produces a result halts in a finite amount
Representation
natural
languages, pseudo code, flowcharts, programming languages
Analysis of algorithm
To analyse an algorithm the most important factors is to calculate resources needed for running the algorithm.
Resources means computer memory, processing time, logic gates, etc
complexity computing time Space complexity storage requirements
Time
Summary
A data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently. Linear Data Structures
Arrays , Linked List Stacks , Queues Graphs , Trees , Hash Tables
Non Linear Data Structures
Abstract data types Algorithm
