[go: up one dir, main page]
Scribd
Upload
62 views29 pages

(Intro To DSA)

This document introduces data structures and algorithms. It discusses that the course objective is to organize data efficiently in programs. The course outline includes assignments, quizzes, projects, exams, and grading. It defines data, data structures, and algorithms. Common data structure applications and a selection of data structures are presented. Properties of algorithms like input, output, definiteness are described. Examples of algorithms to add numbers and types of algorithms are provided. Analysis of algorithms in terms of time efficiency is discussed. Primitive and non-primitive data structures like arrays, stacks, queues, lists, and trees are briefly introduced. It concludes with the relationship between abstract data types and data structures.

Uploaded by

tsidra545
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
62 views29 pages

(Intro To DSA)

This document introduces data structures and algorithms. It discusses that the course objective is to organize data efficiently in programs. The course outline includes assignments, quizzes, projects, exams, and grading. It defines data, data structures, and algorithms. Common data structure applications and a selection of data structures are presented. Properties of algorithms like input, output, definiteness are described. Examples of algorithms to add numbers and types of algorithms are provided. Analysis of algorithms in terms of time efficiency is discussed. Primitive and non-primitive data structures like arrays, stacks, queues, lists, and trees are briefly introduced. It concludes with the relationship between abstract data types and data structures.

Uploaded by

tsidra545
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 29

Data Structures and

Algorithm
INRODUCTION TO DATA STRUCTURES
Course objective

Introduce methods for organizing data so that the data can be accessed
and updated efficiently within a computer program.
COURSE OUTLINE
Course/ Lab Marking

 Assignments 05% (Part of exams)


 Quizzes 10%
 Project 05%
 OHT Exams 30%
 Final Exam 50%
What is Data?
What is Data Structure?
Data Structure Anyway?

It’s an agreement about:


 how to store a collection of objects in memory,
 what operations we can perform on that data,
 the algorithms for those operations, and
 how time and space efficient those algorithms are.
Data Structure Example Applications

 How does Google quickly find web pages that contain a search term?
 How does your Operating System track which memory (disk or RAM) is
free?
 How does the processor handles multitasking
Selection of Data Structure
What is an algorithm?

 Well-defined computational procedure


 Takes set of values as input and produces set of values as output
 Tool to solve well defined computational problems

“An algorithm is a set of step-by-step procedures, or a set of rules to follow, for


completing a specific task or solving a particular problem.”
Common Example [cake backing]

1. Preheat the oven


2. Gather the ingredients
3. Measure out the ingredients
4. Mix together the ingredients to make the batter
5. Grease a pan
6. Pour the batter into the pan
7. Put the pan in the oven
8. Set a timer
9. When the timer goes off, take the pan out of the oven Enjoy!
Data Structures and Algorithms

 Data structures
 Representation and organization of data
 Algorithms
 Methods for implementing operations on data structures
 Data structures and algorithms are closely related
 Data structures are often tuned for certain algorithms
What kind of problems are solved by
algorithms?

 Human Genome Project


 Internet: Routing, searches, security
 Electronic commerce
 Commercial enterprises
 Inflectional disease modeling
Properties of Algorithm

 Input :- Zero or more quantities are supplied.


 Output :- At least one quantity produce.
 Definiteness :- Each instruction is clear and unambiguous.
 Correctness :- An algorithm should produce the correct output values for
each set of input values.
 Finiteness :- Should produce the desired output after a finite number of steps
for any input in the set.
 Effectiveness :- To perform each step of an algorithm exactly and in a finite
amount of time.
 Generality :- The procedure should be applicable for all problems of the
desired form.
Algorithm to add two numbers

Step 1: Start
Step 2: Declare variables num1, num2 and sum
Step 3: Read values num1 and num2
Step 4: Add num1 and num2 and assign the result to sum
sum←num1+num2
Step 5: Display sum
Step 6: Stop
Types of Algorithms

 Divide and conquer algorithms – divide the problem into smaller subproblems of the same type;
solve those smaller problems, and combine those solutions to solve the original problem.
 Brute force algorithms – try all possible solutions until a satisfactory solution is found.
 Randomized algorithms – use a random number at least once during the computation to find a
solution to the problem.
 Greedy algorithms – find an optimal solution at the local level with the intent of finding an
optimal solution for the whole problem.
 Recursive algorithms – solve the lowest and simplest version of a problem to then solve
increasingly larger versions of the problem until the solution to the original problem is found.
 Backtracking algorithms – divide the problem into sub problems, each which can be
attempted to be solved; however, if the desired solution is not reached, move backwards in the
problem until a path is found that moves it forward.
 Dynamic programming algorithms – break a complex problem into a collection of simpler sub
problems, then solve each of those sub problems only once, storing their solution for future use
instead of re-computing their solutions.
Analysis of Algorithm

The purpose of algorithm analysis is to determine:


Time efficiency/Running Time:-Performance in terms of running times for different input
sizes and structure. Running time is dependent on the size of input as well as structure
of input.
Example : Sequential search vs. Binary search
The number of comparisons done by sequential search and binary search of x
(value being searched).
Types of Data Structure
Primitive Data Structure

 Integer
 Float
 Character
 Boolean
Non-Primitive Data Structure
Non-Primitive Data Structure (cot.)
Non-Primitive Data Structure (cot.)
Some Frequently Used DS
Array

 Contagious memory location


 Add items
 Remove item
 Replace item
 Display item
Stack
Queue
List
Tree
Abstract Data Type and Data Structure

You might also like