Class
:-T.E. [Computer Engg.]
Subject
Title: Design and Analysis of Algorithms
Subject
Code: 310250
Examination
Scheme:
In
Semester: 30 Marks
End
Semester: 70 Marks
Lectures:
4 Hrs/Week
Introduction:
What are algorithms? Why is the study of algorithms worthwhile? What is
the role of algorithms relative to other technologies used in computers? In
this course we will answer these questions. You will
learn about algorithms that operate on common data structures, for instance
sorting and searching; advanced design and analysis techniques such as dynamic
programming and greedy algorithms; advanced graph algorithms such as minimum
spanning trees and shortest paths; NP-completeness theory; and approximation
algorithms. After completing this course you will be able to design efficient
and correct algorithms using sophisticated data structures for complex
computational tasks.
Course
Outcomes:
On completion
of the course, student will be able to–
1. Formulate the problem.
2. Design
and apply algorithm for given problem.
3. Analyze
the performance of algorithm by asymptotic notation.
4.
Find optimal solution
by applying various algorithmic strategies.
Prerequisites:
Discrete
Mathematics (210241),
Data
Structures (210243, 210252),
Theory
of Computation (310241)
Overview:
1.
Fundamentals
In this unit, we will learn the
significance of algorithms in computer field, various aspects of algorithm
development, qualities of good solution, significance of program correctness
and efficiency. Two important aspects of
algorithm development viz, correctness and efficiency; are introduced.
2.
Models and Design
Development of algorithms by successive refinement for
both iterative and recursive designs are provided. It also introduces the
concepts of specification and prototyping.
3.
Abstract Algorithms
In this unit meta-algorithms / algorithmic strategies
are discussed in detail. We will learn strategies like, ‘divide and conquer’, ‘greedy’,
‘dynamic programming’. Introduction to Genetic algorithms will also be covered.
4.
Complexity Theory
Having
gone into laborious detail for evaluation the running time, now we will learn
the notations that allow us to characterize the main factors affecting an
algorithm’s running time. Concepts like timing analysis, complexity, asymptotic
growth rates. Order notation and manipulation rules for the algorithms will be
discussed. It will also introduce us to various complexity classes.
5.
Amortized Analysis
The concept of amortized analysis, which charted a new
approach to algorithm efficiency calculation is discussed in this unit. Rather than
focusing on each operation separately, it considers the interactions between
all the operations by studying the running time of a series of these
operations.
6.
Multithreaded and Distributed Algorithms
In this unit, we shall extend our algorithmic model to
encompass parallel algorithms, which can run on a multiprocessor computer that
permits multiple instructions to execute concurrently. It introduces the basics
of the model, showing hot to quantify parallelism in terms of the measures of
work and span. It also explores several interesting Distributed algorithms.
Detail
teaching plan is here:
Textbooks
The
main textbooks we use are:
2.
Introduction to Algorithms by Thomas H.
Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein
4.
Algorithm Design: Foundations, Analysis and
Internet Examples by Michael
T. Goodrich, Roberto Tamassia
No comments:
Post a Comment