Lecture 1

Introduction to Data Structure and Algorithm

 Text Books and Software

 Books
 Data Structures and Algorithm Analysis in C++ by Mark Allen Weiss
 Data Structures and Algorithms in C++ by Adam Drozdek
 Language
 C++
 Software
 Microsoft Visual Studio
 Assessment Criteria (Cr. Hrs. 3+1)

 Theory (3 Cr. Hrs. 100%)

 Quizzes ---------------10%
 Assignments---------10%
 Mid Term------------- 20%
 Final--------------------40%
 Project-----------------20%
 Lab (1 Cr. Hr. 100%)
 Lab Tasks/Exercises ----- 40%
 Mid term--------------------20%
 Final--------------------------40%
 Today’s Agenda

 Module Discussion
 Introduction to DSA
 Arrays & Pointers (Multidimensional Array, Dynamic Memory Allocation)
 Introduction to Vectors
 Overview of different Data Structures
 Abstract Data Type and Data Structure

 Definition:-
 Abstract Data Types (ADTs) stores data and allow various operations on the data to access
and change it.
 A mathematical model, together with various operations defined on the model
 An ADT is a collection of data and associated operations for manipulating that data
 ADTs support abstraction, encapsulation, and information hiding.

 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)
 Introduction

 Data structure is a representation of data and the operations allowed on that data.
 In computer science, a data structure is a particular way of storing and organizing data in a
computer’s memory so that it can be used efficiently.
 Data may be organized in many different ways; the logical or mathematical model of a particular
organization of data is called a data structure.
 There are several basic and advanced types of data structures, all designed to arrange data to
suit a specific purpose.
 Data structures make it easy for users to access and work with the data they need in appropriate
ways.
 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
 3 Steps In The Study Of Data Structures

 Logical or mathematical description of the structure

 Logical means the way data is organized, mathematical means additional operations
performed on the data.

 Implementation of the structure on the computer

 Quantitative analysis of the structure, which includes determining the amount of

memory needed to store the structure and the time required to process the structure.
 Basic Data Structures

Basic Data Structures

Linear Data Structures Non-Linear Data Structures

Arrays Linked Lists Stacks Queues Trees Graphs Hash Tables

 Types of Data Structure

 Linear: In Linear data structure, values are arrange in linear fashion. A DS is said to be linar if its
elements form a sequence.
 Array: Fixed-size
 Linked-list: Variable-size
 Stack: Add to top and remove from top
 Queue: Add to back and remove from front
 Types of Data Structure

 Non-Linear: The data values in this structure are not arranged in order. It is used to
represent data containing hierarchical relationship between elements.

 Hash tables: Unordered lists which use a ‘hash function’ to insert and search
 Tree: Data is organized in branches.
 Graph: A more general branching structure, with less strict connection conditions
than for a tree

No single data structure works well for all purposes, so it is important to know the
strengths and limitations of several of them
 array

Linked list

queue
tree stack
 Array

 Linear array (One dimensional array) : A list of finite number n of similar data elements referenced respectively
by a set of n consecutive numbers, usually 1, 2, 3,…..n. That is a specific element is accessed by an index.
 Let, Array name is A then the elements of A is : a1,a2….. an
 Or by the bracket notation A[1], A[2], A[3],…………., A[n]
 Array Examples

Example:
A linear array A[8] consisting of numbers is pictured in following figure.

Array Examples
 Declaration of the Arrays

 Any array declaration contains: the array name, the element type and the array size.
 int a[20], b[3],c[7];
 float f[5], c[2];
 char m[4], n[20];

 Initialization of an array is the process of assigning initial values. Typically declaration and
initialization are combined.
 float, b[3]={2.0, 5.5, 3.14};
 char name[4]= {‘E’,’m’,’r’,’e’};
 int c[10]={0};
 Pointers and Arrays

 A pointer is a place in memory that points to the address of a variable.

 An array is a single, pre-allocated chunk of contiguous elements (all of the
same type), fixed in size and location.

 https://www.programiz.com/cpp-programming/pointers-arrays
 https://www.geeksforgeeks.org/pointers-vs-array-in-cpp/
 Array (con…)

 Linear arrays are called one dimensional arrays because each MATRICES
1 2 3 4
element in such an array is referenced by one subscript.
1 1 2 3 4
 (Two dimensional array) : Two dimensional array is a
collection of similar data elements where each element is
2 5 6 7 8
referenced by two subscripts. 3 9 10 11 12
 Such arrays are called matrices in mathematics and tables in 4 13 14 15 16
business applications.
 Multidimensional arrays are defined analogously Here, MATRICES[3,3]=11
 Array Data Structure

 It can hold multiple values of a single type.

 Elements are referenced by the array name and an ordinal index.
 Each element is a value
 Indexing begins at zero.
 The array forms a contiguous list in memory.
 The name of the array holds the address of the first array element.
 We specify the array size at compile time, often with a named constant.
 Dynamic Arrays and Vectors

 A dynamic array is quite similar to a regular array, but its size is modifiable during program runtime.
Dynamic Array elements occupy a contiguous block of memory.
 Once an array has been created, its size cannot be changed. However, a dynamic array is different. A
dynamic array can expand its size even after it has been filled.
 During the creation of an array, it is allocated a predetermined amount of memory. This is not the
case with a dynamic array as it grows its memory size by a certain factor when there is a need.
 In data structures, vectors are dynamic arrays that can store elements of the same type. They allow
efficient random access and dynamic resizing.
 Vectors automatically handle memory allocation and deallocation as elements are added or removed.
They are commonly used to implement lists, arrays, or dynamic arrays in programming languages.
 Stacks

 Collection with access only to the last element inserted

 Last in first out
 Data4 Top
insert/push
 remove/pop Data3
 top
Data2
 make empty
Data1
 Queues

 Collection with access only to the item that has been present the longest
 Last in last out or first in first out
 enqueue, dequeue, front
 priority queues and dequeue

Front Back

Data1 Data2 Data3 Data4

 List

 A Flexible structure, because can grow and shrink on demand.

Elements can be:
 Inserted
 Accessed
 Deleted
At any position last
first
edges
 Trees

Root
 A Tree is a collection of elements called nodes.
 One of the node is distinguished as a root, along with a relation
(“parenthood”) that places a hierarchical structure on the nodes.