Your Experiment number is:
Saturday, 19 September 2020
Wednesday, 13 May 2020
Particle Swarm Optimization (PSO) : Introduction and Velocity Equation explained
This video explains the Concept of Particle Swarm Optimization. It is part 1 of PSO series and introduces PSO along with the discussion on velocity updation equation.
The particle swarm optimization (PSO) algorithm is a population-based search algorithm based on the simulation of the social behavior of birds within a flock. The initial intent of the particle swarm concept was to graphically simulate the graceful and unpredictable choreography of a bird flock , with the aim of discovering patterns that govern the ability of birds to fly synchronously, and to suddenly change direction with a regrouping in an optimal formation. From this initial objective, the concept evolved into a simple and efficient optimization algorithm.
Friday, 7 December 2018
Design and Analysis of Algorithm (DAA), TE : CE, Savitribai Phule Pune University (SPPU)
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
Thursday, 6 December 2018
Teaching Plan For Design and Analysis of Algorithm (DAA), TE : CE, Savitribai Phule Pune University (SPPU)
|
Unit
|
Topic and sub topics covered
|
Lecture
|
|
I
|
Fundamentals :
The Role of Algorithms in
Computing –
What are algorithms
|
2
|
|
Algorithms as technology
|
1
|
|
|
Evolution of Algorithms
|
1
|
|
|
Design of Algorithm
|
1
|
|
|
Need of Correctness of
Algorithm
|
1
|
|
|
Confirming correctness of
Algorithm – sample examples
|
1
|
|
|
Iterative algorithm design
issues
|
2
|
|
|
II
|
Models and Design : Functional Model – Features, Recursive processes,
Recursive processes, Recursive
processes
|
1
|
|
Scope
rules, Tail recursion
|
1
|
|
|
Checking
correctness of Iterative process
|
1
|
|
|
Imperative
Model – Basics
|
1
|
|
|
Specifications
and Prototyping
|
1
|
|
|
Stepwise
Refinement
|
1
|
|
|
Proof
Rules – Basics, For loops, Goto and Exit loops
|
1
|
|
|
Functions
and Procedures
|
1
|
|
|
Problem
Solving using Greedy strategy - Knapsack problem, Huffman code generation
algorithm
|
1
|
|
|
III
|
Abstract Algorithms: Dynamic Programming
|
1
|
|
Divide
and Conquer
|
1
|
|
|
Greedy
strategy
|
1
|
|
|
Branch-n-Bound
|
1
|
|
|
Natural
Algorithms –Evolutionary Algorithms and Evolutionary Computing
|
2
|
|
|
Introduction
to Genetic Algorithm
|
1
|
|
|
Simulated
Annealing
|
1
|
|
|
Artificial
Neural Network and Tabu Search
|
1
|
|
|
IV
|
Complexity Theory: Complexity theory – Counting Dominant operators
|
|
|
Growth
rate, upper bounds, asymptotic growth, O, Ω, Ɵ, o and ω notations
|
2
|
|
|
polynomial
and non-polynomial problems
|
1
|
|
|
deterministic
and non-deterministic algorithms
|
1
|
|
|
P-class
problems, NP-class of problems
|
2
|
|
|
Polynomial
problem reduction NP complete problems- vertex cover
|
1
|
|
|
Polynomial
problem reduction NP complete problems-
3-SAT
|
1
|
|
|
NP
hard problem - Hamiltonian cycle.
|
1
|
|
|
V
|
Amortized Analysis: Amortized Analysis – Binary, Binomial and Fibonacci
heap
|
2
|
|
Dijkstra‘s
Shortest path algorithm, Splay Trees, Time-Space tradeoff
|
2
|
|
|
Introduction
to Tractable and Non-tractable Problems
|
1
|
|
|
Introduction
to Randomized and Approximate algorithms
|
1
|
|
|
Embedded
Algorithms: Embedded system scheduling (power optimized scheduling algorithm)
|
2
|
|
|
sorting
algorithm for embedded systems
|
1
|
|
|
VI
|
Multithreaded and Distributed Algorithms: Multithreaded Algorithms - Introduction, Performance
measures
|
1
|
|
Analyzing
multithreaded algorithms
|
1
|
|
|
Parallel
loops, Race conditions
|
1
|
|
|
Problem
Solving using Multithreaded Algorithms - Multithreaded matrix multiplication,
|
1
|
|
|
Multithreaded
merge sort
|
1
|
|
|
Distributed Algorithms -
Introduction, Distributed breadth first search
|
1
|
|
|
Distributed Minimum
Spanning Tree
|
1
|
|
|
String Matching- Introduction,
The Naive string matching algorithm
|
1
|
|
|
The Rabin-Karp algorithm
|
1
|
Text books: (T)
T1. Parag Himanshu
Dave, Himanshu Bhalchandra
Dave, ―Design And Analysis of Algorithms‖, Pearson Education, ISBN
81-7758-595-9
T2. Gilles Brassard, Paul Bratley, ―Fundamentalsof Algorithmics‖, PHI, ISBN 978-81-203-1131-2
References
Books: (R)
R1. Michael T.
Goodrich, Roberto Tamassia ,
―Algorithm Design: Foundations, Analysis and Internet Examples‖, Wiley, ISBN
978-81-265-0986-7
R2. Thomas H. Cormen, Charles E. Leiserson,
Ronald L. Rivest and Clifford Stein, ―Introduction to Algorithms‖, MIT Press;
ISBN 978-0-262-03384-8
R3. Horowitz and Sahani, "Fundamentals ofComputer Algorithms", University Press, ISBN: 978 81 7371 6126, 81 7371
61262
R4. Rajeev Motwani and Prabhakar Raghavan,
―Randomized Algorithms‖, Cambridge University Press, ISBN: 978-0-521-61390-3
R5. Dan Gusfield, ―Algorithms on Strings,Trees and Sequences‖, Cambridge University Press,ISBN:0-521-67035-7
Thursday, 16 August 2018
Assignment 1 & 2
Since Assignment -I and II is not properly visible on mobile devices, I am sharing these snapshots.
Friday, 10 August 2018
Rules of Inference
An argument (in propositional logic) is a sequence of
propositions. All but the final proposition are called premises. The last
proposition is the conclusion. The argument is valid iff the truth of all
premises implies the conclusion is true.
In this discussion, we are using a notation where, hypotheses
are written in a column, followed by a horizontal bar, followed by a line that
begins with the therefore symbol with the conclusion.
Addition
P
----------------
∴P∨Q
Disjunctive Syllogism
P∨Q
¬P
----------------
∴Q
Conjunction
P
Q
----------------
∴P∧Q
Hypothetical Syllogism
P→Q
Q→R
----------------
∴ P→R
Simplification
P∧Q
----------------
∴P
Constructive Dilemma
(P→Q)∧(R→S)
P∨R
----------------
∴Q∨S
Modus Ponens
P→Q
P
----------------
∴Q
Destructive Dilemma
(P→Q)∧(R→S)
¬Q∨¬S
----------------
∴¬P∨¬R
Modus Tollens
P→Q
¬Q
----------------
∴¬P
Resolution
P∨Q
¬P∨R
----------------
∴ Q∨R
How to build arguments using the rules of inference
1. I t is
not sunny this afternoon and it is colder than yesterday.
2. If we
go swimming it is sunny.
3. If we
do not go swimming then we will take a canoe trip.
4. If we
take a canoe trip then we will be home by sunset.
5. We
will be home by sunset
Subscribe to:
Posts (Atom)