Scribd
Upload
28 views3 pages

Foundation of Algorithm Analysis Teaching Hours: 4 Hrs

The document outlines an algorithms course broken into 8 sections, covering topics like asymptotic analysis, iterative algorithms, divide and conquer algorithms, greedy algorithms, dynamic programming, backtracking, number theoretic algorithms, and NP-completeness. Each section includes subtopics and associated teaching hours.

Uploaded by

Anil
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
28 views3 pages

Foundation of Algorithm Analysis Teaching Hours: 4 Hrs

The document outlines an algorithms course broken into 8 sections, covering topics like asymptotic analysis, iterative algorithms, divide and conquer algorithms, greedy algorithms, dynamic programming, backtracking, number theoretic algorithms, and NP-completeness. Each section includes subtopics and associated teaching hours.

Uploaded by

Anil
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/ 3

1.

Foundation of Algorithm Analysis teaching hours: 4 hrs


1.1. Algorithm and its properties, RAM model, Time and Space Complexity,
detailed analysis

of algorithms (Like factorial algorithm), Concept of Aggregate Analysis

1.2. Asymptotic Notations: Big-O, Big-Ω and Big-Ө Notations their Geometrical
Interpretation

and Examples.

1.3. Recurrences: Recursive Algorithms and Recurrence Relations, Solving


Recurrences

(Recursion Tree Method, Substitution Method, Application of Masters Theorem)

2. Iterative Algorithms teaching hours: 4 hrs


2.1. Basic Algorithms: Algorithm for GCD, Fibonacci Number and analysis of their
time and

space complexity

2.2. Searching Algorithms: Sequential Search and its analysis

2.3. Sorting Algorithms: Bubble, Selection, and Insertion Sort and their Analysis

3. Divide and Conquer Algorithms teaching hours: 8 hrs


3.1. Searching Algorithms: Binary Search, Min-Max Finding and their Analysis

3.2. Sorting Algorithms: Merge Sort and Analysis, Quick Sort and Analysis (Best
Case, Worst

Case and Average Case), Heap Sort (Heapify, Build Heap and Heap Sort
Algorithms and

their Analysis), Randomized Quick sort and its Analysis

3.3. Order Statistics: Selection in Expected Linear Time, Selection in Worst Case
Linear Time
and their Analysis.

4. Greedy Algorithms teaching hours: 6 hrs


4.1. Optimization Problems and Optimal Solution, Introduction of Greedy
Algorithms,

Elements of Greedy Strategy.

4.2. Greedy Algorithms: Fractional Knapsack, Job sequencing with Deadlines,


Kruskal’s

Algorithm, Prims Algorithm, Dijkstra’s Algorithm and their Analysis

4.3. Huffman Coding: Purpose of Huffman Coding, Prefix Codes, Huffman Coding

Algorithm and its Analysis

5. Dynamic Programming teaching hours: 8 hrs


5.1. Greedy Algorithms vs Dynamic Programming, Recursion vs Dynamic
Programming,

Elements of DP Strategy

5.2. DP Algorithms: Matrix Chain Multiplication, String Editing, Zero-One


Knapsack

Problem, Floyd Warshwall Algorithm, Travelling Salesman Problem and their

Analysis.

5.3. Memoization Strategy, Dynamic Programming vs Memoization

6. Backtracking teaching hours: 5 hrs


6.1. Concept of Backtracking, Recursion vs Backtracking

6.2. Backtracking Algorithms: Subset-sum Problem, Zero-one Knapsack Problem,


N-queen

Problem and their Analysis.


7. Number Theoretic Algorithms
teaching hours: 5 hrs
7.1. Number Theoretic Notations, Euclid’s and Extended Euclid’s Algorithms and
their

Analysis.

7.2. Solving Modular Linear Equations, Chinese Remainder Theorem, Primility


Testing: Miller-

Rabin Randomized Primility Test and their Analysis

8. NP Completeness
teaching hours: 5 hrs
8.1. Tractable and Intractable Problems, Concept of Polynomial Time and Super
Polynomial

Time Complexity

8.2. Complexity Classes: P, NP, NP-Hard and NP-Complete

8.3. NP Complete Problems, NP Completeness and Reducibility, Cooks Theorem,


Proofs of NP

Completeness (CNF-SAT, Vertex Cover and Subset Sum)

8.4. Approximation Algorithms: Concept, Vertex Cover Problem, Subset Sum


Problem

You might also like