[go: up one dir, main page]
Scribd
Upload
93 views19 pages

Design & Analysis of Algorithm (CSC-321) : Mona Leeza, Computer Sciences Department Bahria University (Karachi Campus)

This document provides an introduction to the Design & Analysis of Algorithm course. The key points are: - The course will cover mathematical tools for analyzing algorithm time and space complexity, sorting algorithms, dynamic programming, greedy algorithms, and graphs. - Students will learn strategies for designing algorithms like brute force, divide and conquer, dynamic programming, and backtracking. - Algorithms will be analyzed based on their time and space complexity to determine efficiency. The goal is to design efficient algorithms that are in the polynomial time class.

Uploaded by

Abdullah
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
93 views19 pages

Design & Analysis of Algorithm (CSC-321) : Mona Leeza, Computer Sciences Department Bahria University (Karachi Campus)

This document provides an introduction to the Design & Analysis of Algorithm course. The key points are: - The course will cover mathematical tools for analyzing algorithm time and space complexity, sorting algorithms, dynamic programming, greedy algorithms, and graphs. - Students will learn strategies for designing algorithms like brute force, divide and conquer, dynamic programming, and backtracking. - Algorithms will be analyzed based on their time and space complexity to determine efficiency. The goal is to design efficient algorithms that are in the polynomial time class.

Uploaded by

Abdullah
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/ 19

Design & Analysis of Algorithm (CSC-321)

Mona Leeza,
Computer Sciences Department
Bahria University (Karachi Campus)
INTRODUCTION
Lecture No 01
Learning Outcomes
 In this Lecture will learn ......
 To understand the basic definitions and related
terms
 To discuss the scope and objectives of the course
Prerequisites for this course
 Data Structures
 Array
 Tree
 Graph
 Hash
 Heap
 Discrete Mathematics
 Basic mathematics of above listed structures
Grading
 Total marks = 100 (10+20+20+50)
------------------------------------------------------
 Quizzes (4) = 10

 Assignments (3) = 20

 Mid-Term Exam = 20 (Objective-8, Subjective-12)

 Final Exam = 50 (Objective-20, Subjective-30)


Text Book
 Introduction to Algorithms, Thomas H. Cormen,
Leiserson, Rivest, and Stein , 2012. 3rd Edition, MIT
Press.
Course Outline---
 Four major sections
 Study of mathematical tools for analysis of
algorithms (Time and Space Complexity analysis)
 Sorting through different strategies and use this
problem as case study for designing and analyzing
algorithms.
 Dynamic Programming, Greedy strategy and
Graphs
 Intro to NP-Completeness.
Definition: Algorithm
 An algorithm in any well defined computational
procedure that take some value, or set of values as
input and produces some value or set of values as
output
 An algorithm is a sequence of computational steps
that transform the input into output
Sequence of
Input(s) computational Output(s)
steps
Why Algorithm
Why Algorithm
Why Algorithm
Algorithm and Programming

 A correct understanding of algorithms is essential


for correct programming (Designing)
 Algorithm is a mathematical entity (Analysis)
 Algorithm is independent of a specific
programming, machine or compiler
 An algorithm is purely based on mathematical
theory because we always use mathematics as a
tool to analyze the algorithm
Algorithm and Programming---
 An algorithm always based on use of a good
data- structure.
 It is a fact that use of efficient algorithms and good

data structures is the core approach in computer


science.
 Problem solution ----- is called algorithm

 Solution Implementation ---- is called Programming


Analyzing Algorithms
 How to judge an algorithm to be efficient.
 We will measure algorithms in terms of
computational resources
 Running Time---- Time complexity
 Memory---- Space complexity
 An algorithm is understandable by human and not
by machine.
Model of Computation
 A mathematical machine that runs out algorithms
 This machine has a single CPU.
 It is generic machine.
 This model is called RAM (Random Access Machine)
 RAM
 Infinite memory
 Instructions will be executed one-by-one
 Each instructions will perform some mathematical operation on
only two values.
Designing Strategies
 Brute force algorithms
(exhaustive search, try all possibilities)
 Divide and Conquer Algorithms

(break problem into distinct subproblem)


 Dynamic Algorithms

(break problem into overlapping subproblem)


 Back Tracking

To track the best solution)


 Greedy Algorithms
Scope and Objectives
 Scope: We will design and discuss the algorithm of
polynomial time class algorithms and also introduce
the np and np-complete class algorithms

 Objectives:
 To design strategies of p-class algorithms.
 To analyze the p-class algorithms with respect to
time complexity and space complexity
Conclusion
 After this lecture we are able to ......
 Define basic definitions and related terms
 Discuss the scope and objectives of the course

You might also like