Introduction

CSC-114 Data Structures and Algorithms

Outline
 Information about course & class
 Introduction
 Data Type
 Abstract Data Type (ADT)
 Data Structures
 Algorithm
 Approaches to Allocate Memory

2 Saba Anwar, Computer Science Department- CIIT Lahore 15/09/2024

Course Website & Information
 Course Website
 Section wise
 https://piazza.com/ciitlahore.edu.pk/spring2017/csd202c/home
 https://piazza.com/ciitlahore.edu.pk/spring2017/csd202d/home
 Text and Reference Books
 No Strict requirement, notes will be provided if needed
 Just follows class notes and any additional material, if provided
 Language/IDE
 Java
 Eclipse
 Resource Person
 Saba Anwar
 Email: sabaanwar@ciitlahore.edu.pk
 Office: C11-1
3 Saba Anwar, Computer Science Department- CIIT Lahore 15/09/2024
Introduction
 In this course, we will look at:
 Data Structures
 Different ways for organizing data, so that it can be accessed efficiently?
 Access for?
 Operations that can be performed on it
 Insert, delete, search/find
 Algorithms
 Logic to perform those operations
 Dependent on data structures
 Data structures have trade-offs
 There is no ultimate data structure and resources are limited
 The choice depends on our requirements
 Time vs. Space

4 Saba Anwar, Computer Science Department- CIIT Lahore 15/09/2024

Data and Data Type
 Data
 Facts, figures, numbers
 Data Type
 Specifies properties of a certain category of data values
 Domain: What kind of values it can hold
 Operations: What kind of operations it support
 Data Type can be:
 Scalar/Atomic: also called primitive data types, no further sub-parts
 int, float, double
 Composite/Structured: have further sub-parts
 struct, arrays, classes, interfaces, enums

5 Saba Anwar, Computer Science Department- CIIT Lahore 15/09/2024

Data Structure
 Collection of data elements with a set of rules which defines the logical
relationship of these elements.
 Data elements
 Can be atomic as well as composite, even another data structure too
 Structure
 Set of rules to hold data together
 How you will organize your music collection?
 How books are arranged in library?
 A specific structure can be helpful for certain operations.
 Finding a number in an unordered list vs finding it in an ordered list

6 Saba Anwar, Computer Science Department- CIIT Lahore 15/09/2024

Data Structure
 How easy would be the following operations
in all three scenarios mentioned in figure?
 Finding a book whose name starts with a specific
word?
 Finding all books of a particular subject?
 Adding a new book to existing stock?
 How to choose structure?
 Which operations are more important?
 Does the structure would help to perform those
operations more efficiently than some other
structure?

7 Saba Anwar, Computer Science Department- CIIT Lahore 15/09/2024

Different Types and Applications
 Stack - undo\redo operation in word
processors, Expression evaluation and
syntax parsing, JVM is stack oriented.
 Queues - Transport and operations
research where various entities are stored
and held to be processed later, buffer.
 Priority queues - process scheduling in
the kernel
 Hash Table - used for fast data lookup -
symbol table for compilers, database
indexing, cache, dictionary
 Trees - Parsers, File system, dictionary,
such as one found on a mobile for auto-
completion and spell-checking
 Heap - Dynamic memory allocation
 Graphs - Connections/relations in social
networking sites, Routing ,networks of
communication, data organization

8 Saba Anwar, Computer Science Department- CIIT Lahore 15/09/2024

Trade-offs
 Common operations for a data collection
 Add, Delete, Search, Update
 How to decide that which data structure we need?
 Structure of data affects efficiency of data operations
 Time vs Space
 Generality vs. simplicity vs. performance
 One operation is more efficient if another less efficient

 So there are trade-offs with each data structure

 There is no one ultimate data structure, you have to choose according to your priorities
 Does this support the operations I need? efficiently?
 Will it be easy to use (and reuse), implement, and debug?
 What assumptions am I making about how my software will be used? (E.g., more searching or more
inserts?)
 Does ordering is more important than anything
9 Saba Anwar, Computer Science Department- CIIT Lahore 15/09/2024
Abstraction
Logical view of data vs physical implementation

Binary form
Movies Images

Abstraction has hidden

the actual or physical
representation of data

Maps Music

10 Saba Anwar, Computer Science Department- CIIT Lahore 15/09/2024

Abstraction
 The idea behind abstraction is to focus on what something can do(operations) rather than how it
does (implementation).
 Float and integer both takes 4 bytes but their physical implementation is different
Integer
Values: -2147483648 to +2147483647
Operations: +, -, /, *, +, relational operators
+ and – can be use as prefix, but all other operators would be use as infix
Abstraction:
Physical implementation of values and operations is hidden from user. User does not need to know how integer has been implemented in
particular language? He just needs to know what it does?
Logical meaning of integer is same for different programming languages, but implementation may vary.

 Abstraction makes the logical view of a data type important than it’s physical implementation
complexities.
 int, float, Account, Point, Rectangle, 2D array
 The advantages of using the ADT approach:
 Implementation of ADT can be changed without affecting those method that use the ADT
11 Saba Anwar, Computer Science Department- CIIT Lahore 15/09/2024
Abstract Data Type (ADT)
 Abstraction has made the use of data structures more easy with concept of Abstract Data Type (ADT).
 ADT is a data type whose internal implementation is hidden from user. In other words an ADT specifies set of
data values and associated operations independent of any particular implementation.
Stack ADT
Values: would follow last in first out order
Operations:
Push(E): will add element E on top of existing elements
Pop(): will remove top element
Peek(): will return top element, without removing
Abstraction:
This ADT does not explain how it would be implemented? as a class, struct, simple structured programming, using array or linked list, would it work for integers? Or
strings?
There is no assumption about types and there is no logic given for operations.

User just needs to know what a stack does? what push and pop will do?

 Now when a programming language implements an ADT, it adopts a certain implementation logic which can vary from
other languages, but their implementation does not change the definition of ADT
12 Saba Anwar, Computer Science Department- CIIT Lahore 15/09/2024
Data Structure and ADT
 ADT is the logical view
 Stack ADT does not specify anything about implementation. It just describes the
expected behaviors.
 Data structure is the physical implementation
 To implement Stack ADT you have to choose your container, and describe your
algorithms for operations which greatly depends upon your choice.
 In OO world interface and classes serve as an encapsulating units which can
hide the implementation from user. User is only concerned about what methods
are available and what they do?

13 Saba Anwar, Computer Science Department- CIIT Lahore 15/09/2024

What is algorithm?
 To perform supported operations on data structure, we write algorithms.
 An Algorithm is a finite set of ordered instructions which solves a particular problem.
 Transforms input of a problem to output
Algorithm = Input + Process + Output
 A good algorithm must be:
 Correct
 Finite
 Unambiguous
 Efficient
Data
Algorithms Program
Structures

14 Saba Anwar, Computer Science Department- CIIT Lahore 15/09/2024

Algorithm development: Basics
 Clearly identify:
 Purpose
 What it will do?
 What is the input?
 What is needed?
 What output is required?
 What has to be produced?
 What is Precondition?
 Conditions must be true before algorithm runs
 What is Postcondition?
 Conditions must be true after it has been run
 What steps are required to transform input into output
 Needs problem solving skills
 A problem can be solved in many different ways
 Algorithm Analysis
 Which solution, amongst the different possible solutions is optimal?
15 Saba Anwar, Computer Science Department- CIIT Lahore 15/09/2024
Memory Allocation
 Every data structure needs memory to store data according to its structure.
 Memory is allocated to each data element, and structure tells us how each
element is connected to other
 Data structures can be classified into two categories depending upon memory
allocation
 Contiguous
 Single block of memory
 Linked
 Multiple blocks linked through pointers

16 Saba Anwar, Computer Science Department- CIIT Lahore 15/09/2024

Contiguous Allocation
 Single block of memory, divided into uniform sized cells to store n
number of data elements, also known as array
 Each cell is accessed using its index
 We need to know address to first cell and total number of cells to use the block

 Application:
 Hashtables, Adjacency Matrices, Stacks, Queues

17 Saba Anwar, Computer Science Department- CIIT Lahore 15/09/2024

Contiguous Allocation
 Easy to use
 Using index
 Memory Wastage
 If actual number of data elements is less than actual capacity
 Not Dynamic
 if more memory is required on run time, a request for new memory usually requires
copying all information into the new memory
 Allocation in not guaranteed
 If big enough block is not available but only small blocks

18 Saba Anwar, Computer Science Department- CIIT Lahore 15/09/2024

Linked Allocation
 Linked storage associates two pieces of data using pointers, each data
element is wrapped in an object normally called node, node contains two
parts:
 Data itself
 Pointer
 Reference to the next node/object in memory

 Reference to first node is required, so all that nodes can be traversed

 Known as Linked List
 Applications:
 Lists, Trees, Adjacency Lists
19 Saba Anwar, Computer Science Department- CIIT Lahore 15/09/2024
Linked Allocation
 Node Representation
C/C++ Java
struct Node{ class Node{
data declarations ; data declarations;
Node* next; Node next;
} }

 The operations for a node must include:

 Constructing a new node
 Accessing the data values
 Accessing the next pointer

20 Saba Anwar, Computer Science Department- CIIT Lahore 15/09/2024

Linked Allocation
 Not Simple
 Involves pointers
 No Memory Wastage
 Create node when required
 Dynamic
 if more memory is required on run time, just create node
 If not, then delete node
 Allocation is guaranteed
 As far as there are free blocks, they can be claimed using nodes

21 Saba Anwar, Computer Science Department- CIIT Lahore 15/09/2024

Summary
 In this lecture, we have discussed:
 What are data structures
 What are algorithms
 Why we need data structures & algorithms
 How memory is allocated to data structures

22 Saba Anwar, Computer Science Department- CIIT Lahore 15/09/2024