DATA STRUCTURES AND ALGORITHM

Mobile: +92-312-7070895

Instructor: Dr. M. Usman Ashraf

Email: usman.ashraf@gcwus.edu.pk

Web:

https://sites.google.com/site/musmanashrafpk/teaching

Books to Follow

• D.S.Malik, “Data Structures using C++”
• D.Samanta, “Classic Data Structures”, Prentice Hall
• Tenenbaum, M.Augenstein, and Y. Langman, “Data Structures using C and C++”, Prentice Hall.

​

2

Some General Comments

• Encouragement to ask questions during class
• Without your feedback, it is impossible for me to know what you don’t know
•  There is no reason not to ask questions during class
• Of course, you could also send email, or meet in person
•  Encouragement to read course material prior to class

​

3

Introduction to Data Structure

4

A data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently

Need for Data Structures

• Data structures organize data ⇒ more efficient programs.
• More powerful computers ⇒ more complex applications.
• More complex applications demand more calculations.

Organizing Data

• Any organization for a collection of records that can be searched, processed in any order, or modified.
• The choice of data structure and algorithm can make the difference between a program running in a few seconds or many days.

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 of logical relationships between individual data elements related to the solution of a given problem.

7

Fundamental Data Structures

8

Hash Tables

Basic Data Structures

Linear Data Structures

Non-Linear Data Structures

Linked Lists

Stacks

Queues

Trees

Graphs

Arrays

array

Linked list

tree

queue

stack

Linear Data Structures

• A data structure is said to be linear if its elements form a sequence or a linear list.
• Examples:
• Arrays
• Linked Lists
• Stacks
• Queues

​

10

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.

​

11

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

12

Linear Data Structures

• Arrays
• Linked List
• Stacks
• Queues

13

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 array’s index.
• Properties:
• fixed length (need preliminary reservation of memory)
• contiguous memory locations
• direct access
• Insert/delete

​

​

14

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
• Types of Linked List
• Singly linked list (next pointer)

​

• Doubly linked list (next + previous pointers)

​

15

Stacks

• A stack is a data structure that uses last-in, first-out (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 (insertion)
• Pop (removal)

​

16

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

​

17

Non-Linear Data Structures

• Graphs
• Trees
• Hash Tables

18

Graphs

• Formal definition: A graph G = <V, E> is defined by a pair of two sets: a finite set V of items called vertices and a set E of vertex pairs called edges.
• Undirected and directed graphs (digraphs).
• Complete, dense, and sparse graphs

19

Undirected Graph

Directed 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
• Leaf Node
• Types
• Unordered Tree
• Binary Tree is an ordered tree data structure in which each node has at most two children.

20

Unordered Tree

Binary Tree

Hash Tables

• A hash table is a data structure that uses a hash function to map identifying values, known as keys (e.g., a person's name), to their associated values (e.g., their telephone number).

21

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
• Non Linear Data Structures
• Graphs
• Trees
• Hash Tables

​

22

Selecting a Data Structure

Select a data structure as follows:

1. Analyze the problem to determine the resource constraints a solution must meet.
2. Determine the basic operations that must be supported. Quantify the resource constraints for each operation.
3. Select the data structure that best meets these requirements.

Data Structure Philosophy

• Each data structure has costs and benefits.
• Rarely is one data structure better than another in all situations.
• A data structure requires:
• space for each data item it stores,
• time to perform each basic operation,
• programming effort.

Introduction to Algorithms

A precise rule (or set of rules) specifying how to solve some problem.

25

What is an Algorithm?

• An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time.
• Properties
• Can be represented various forms
• Unambiguity/clearness
• Effectiveness
• Finiteness/termination
• Correctness

​

26

What is an Algorithm?

• Recipe, process, method, technique, procedure, routine,… with the following requirements:
• Finiteness
• terminates after a finite number of steps
• Definiteness
• rigorously and unambiguously specified
• Clearly specified input
• valid inputs are clearly specified
• Clearly specified/expected output
• can be proved to produce the correct output given a valid input
• Effectiveness
• steps are sufficiently simple and basic

​

​

27

Why Study Algorithms?

• Algorithms solve problems
• Good choice: more efficient programs
• Bad choice: poor programs performance
• Example:
• Problem: Find the largest element ‘k’ out of ‘N’ integers
• Easy algorithms: sort all integers, then list the first or last element
• Better algorithm: sort first element then read through the list
• Different algorithms perform better on different inputs
• Input size also affect the performance.

28

Notion of Algorithm and Problem

29

“Computer”

Problem

Algorithm

Input

Output

Representation of an Algorithms

• An algorithm may be represented in different forms:
• A description using English/other languages
• A real computer program, e.g. C++
• A pseudo-code, C-like program, program-language-like program.

​

• Program = algorithms + data structures

30

Basic Issues Related to Algorithms

• How to design algorithms

​

• How to express algorithms

​

• Proving correctness

​

• Efficiency (or complexity) analysis
• Theoretical analysis

​

• Empirical analysis

​

• Optimality

​

​

​

31

Analysis of Algorithms

• How good is the algorithm?
• Correctness
• Time efficiency
• Space efficiency

​

• Does there exist a better algorithm?
• Lower bounds
• Optimality

​

32

Algorithm Efficiency

• There are often many algorithms for a given problem. How do we choose the best?
• Goals of program design:
• Algorithm is to be easy to understand, code, debug
• Algorithm makes efficient use of computer’s resources
• How to measure the efficiency?
• Empirical comparison (run the program)
• Asymptotic algorithm analysis (without running the program)
• Critical resources
• Factors affecting running time (size of the input)

​

33

Best, Worst and Average Cases

• Not all inputs of a given size take the same time.
• Each algorithm has three cases:
• Best case:
• Worst Case:
• Average Case:

​

34

Example: Best, Worst and Average Cases

• Sequential search for ‘k’ in an array of ‘n’ integers:
• Best case: ‘k’ is the first element of the array.
• Worst case: the search must visit every element once. This happens when the value being searched for is either the last element in the list, or is not in the list
• Average case: on average, assuming the value searched for is in the list and each list element is equally likely to be the value searched for, the search visits only n/2 elements.

35

Algorithm Analysis

We analyse algorithms, rather than problems. A problem can be solved with several algorithms, some are more efficient than others.

​

36

Quiz-1 Time: 15 Minutes

Write a program in C++, where user get input array arr of length 10 and another input in a variable x.

Define a class named “SearchOpr” containing function named “searchVal”. searchVal takes two parameters including an integer array localArr and integer ‘val’. searchVal will return 0 if localArr contains val.

You are supposed to search input value x from arr by utilizing class SearchOpr.

​

37

Why need algorithm analysis?

• Just writing a syntax-error-free program is not enough. We need to know whether the algorithm is correct or not, i.e. whether it can give correct answers for the inputs.

​

• If the program is run on a large data set, the running time becomes an issue. We want to know how the algorithm performs when the input size is large. The program may be computationally inefficient, or may need lots of memory. We analyze the resources that the algorithm requires: memory, and computation time. We can also compare algorithms without implementations.

How to Analyse an Algorithm?

• To analyse an algorithm; determine the amount of resources (such as time and storage) necessary to execute it.
• Most algorithms are designed to work with inputs of arbitrary length.
• Usually the efficiency or running time of an algorithm is stated as a function relating the input length to the number of steps (time complexity) or storage locations (space complexity).

39

Analysis of Algorithms

• Analysis of Algorithm refers to calculating or guessing resources needful for the algorithm.
• Resources means computer memory, processing time etc.
• In all these factors, time is most important because the program developed should be fast enough.

Analysis of Algorithms

• Time complexity
• The amount of time that an algorithm needs to run to completion
• Space complexity
• The amount of memory an algorithm needs to run
• We will occasionally look at space complexity, but we are mostly interested in time complexity in this course.
• Thus in this course the better algorithm is the one which runs faster (has smaller time complexity)

Any Query?

42

Assignment-1 (Secured Zero marks who ‘ven’t submitted)

​

What are the ways to measure the Time and space complexity of particular scenarios?

Explain each scenario with example code and find its complexity (time and space).

Handwritten.

With cover page.

Deadline: Next class.

43