Scribd
Upload
4 views13 pages

Lecture 1

The document outlines the syllabus for the Algorithm Design and Strategies course, detailing various units covering topics such as time complexity, sorting algorithms, greedy algorithms, dynamic programming, and NP-completeness. It also includes a course evaluation policy that breaks down the grading components, including lab evaluations, assignments, projects, and end-term assessments. Recommended textbooks for the course are listed for further reading.

Uploaded by

spoc.bu.springboard
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
4 views13 pages

Lecture 1

The document outlines the syllabus for the Algorithm Design and Strategies course, detailing various units covering topics such as time complexity, sorting algorithms, greedy algorithms, dynamic programming, and NP-completeness. It also includes a course evaluation policy that breaks down the grading components, including lab evaluations, assignments, projects, and end-term assessments. Recommended textbooks for the course are listed for further reading.

Uploaded by

spoc.bu.springboard
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/ 13

31 July 2023

L-01
AGENDA:
❑Introduction to Subject

❑Syllabus

❑Evaluation Component
Algorithm
Unit -1
CBCA204
Algorithm Design and Strategies
Course Type - Core L-T-P Format :3-1-4

Credits – 6
Syllabus
Unit 01
• Introduction to algorithm • Amortized analysis
• What is Time Complexity and Space • Analysing control statement
Complexity
• Loop Invariant
• Order of Growth
• Recurrence Relations Introduction
• Approximation
• Back Substitution Method
• Asymptotic Notations :
• Big Oh
• Recursion Tree Method
• Theta • Master’s Theorem
• Omega
Unit 01

• Divide and Conquer Algorithm • Radix Sort


• Multiplying large Integers Problem
• Bucket Sort
• Median of two sorted arrays
• Binary search
• Quick Sort
• Merge Sort
• Max-Min problem
• Strassen's Matrix Multiplication
Unit 02
• Shortest Paths
• Dijkstra's Algorithm
• Greedy Algorithm
• General Characteristics • Applications of DFS
• Knapsack Problem • Bi-connectivity
• Huffman code • Topology Sort
• Activity selection problem • Articulation point
• Connected components
• Minimum Spanning Trees
• Prim’s algorithm
• Kruskal’s algorithm with Disjoint
sets
Unit 02
• Max-Flow • Longest Common Subsequence
• Min-Cut • All Pair Shortest path
• Ford-Fulkerson • Floyd Warshall
• Dynamic Programming • Largest Divisible Subset.
• Introduction
• Principle of Optimality
• Calculating Binomial
Coefficient
• 0-1 Knapsack
• Matrix chain multiplication
Unit 03
• Backtracking • String Matching Algorithm
• State-Space Search Tree • Naive string-matching
• Eight queen’s problem algorithm
• Graph Colouring • Knuth Morris-Pratt algorithm
• Hamiltonian Cycle
• Branch and Bound
Approach
• Travelling Salesman Problem
using
Unit 04
• Randomized Algorithms
• Randomized Quick Sort
• Introduction to NP-Completeness
• P and NP
• Computational Geometry
• NP Complete and NP-Hard • Convex hull

• Approximation algorithms • Online Algorithms


• Travelling Salesman problem • K Server Problem
Books

Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms (3 ed.), The


1. MIT Press, 2010. ISBN 978-0262033848.

Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran, Computer


2. Algorithms/C++ (Second Edition), The Orient Blackswan,2019. ISBN:
9386235145

Narsimha Karumanchi, Algorithm Design Techniques: Recursion,


3. Backtracking, Greedy, Divide and Conquer and Dynamic Program (1 ed.),
Career Monk Publications, 2018. ISBN 978-8193245255.
Course Evaluation Policy
Lab continuous Evaluation: 30%
Assignments: 5%
Project: 15%
Codathon: 15%
End Term : 35%

You might also like