15IS41T: Analysis and Design of Algorithms Information Sci 4th Sem Syllabus for Diploma DTE Karnataka C15 Scheme

Analysis and Design of Algorithms detail DTE Kar Diploma syllabus for Information Science And Engineering (IS), C15 scheme is extracted from DTE Karnataka official website and presented for diploma students. The course code (15IS41T), and for exam duration, Teaching Hr/week, Practical Hr/week, Total Marks, internal marks, theory marks, duration and credits do visit complete sem subjects post given below. The syllabus PDFs can be downloaded from official website.

For all other information sci 4th sem syllabus for diploma c15 scheme dte karnataka you can visit Information Sci 4th Sem Syllabus for Diploma C15 Scheme DTE Karnataka Subjects. The detail syllabus for analysis and design of algorithms is as follows.

Pre-requisites:

Basic Knowledge of basic Mathematics ,English comprehension and C Programming.

Course Objectives:

1. Analyze the asymptotic performance of algorithms & Write rigorous correctness proofs for algorithms
2. illustrate with different algorithm design techniques (brute-force, decrease and conquer, divide and conquer)
3. Work with different algorithm design techniques (Greedy, dynamic programming)
4. Acquire basic knowledge of computational complexity.(Branch and bound and Back tracking)

Course Outcomes:

For complete syllabus and results, class timetable and more pls download iStudy Syllabus App. Its a light weight, easy to use, no images, no pdfs platform to make students life easier.

UNIT I: Introduction 12 Hrs

1. Introduction
2. Algorithm Definitions
3. Fundamentals of algorithm problem solving
4. The efficiency of algorithms
5. Best, Average and worst case analysis
6. Methodologies for Analyzing algorithm
7. Pseudo code
8. Counting the primitive operations
9. Algorithm Complexities
1. Space Complexity
2. 1 Analysis of space complexity
3. 2 How to calculate Space complexity?
4. Time Complexity
10. Asymptotic Notations
11. The Big-oh Notation
12. The Big-omega Notation
13. The big-theta notation
14. Ordering functions by their Growth rates

UNIT II: Graphs Optimization Problems 08 Hrs

1. Graphs Optimization Problems
2. Graphs
1. Definitions and Representations
2. Different types of graph
3. Searching Methods: DFS and BFS
4. Introduction to Trees
5. Applications
3. Optimization Problems
1. Feasible Solutions
2. Optimal Solutions
3. Important problem types: Sorting, Searching, string processing, graph problems, combinatorial problems, Geometric problems, Numeric problems.

UNIT III: Brute Force method 06 Hrs

For complete syllabus and results, class timetable and more pls download iStudy Syllabus App. Its a light weight, easy to use, no images, no pdfs platform to make students life easier.

UNIT IV: Divide and Conquer, Decrease and Conquer 10Hrs

1. Divide and Conquer, Decrease and Conquer
2. Divide and Conquer
1. Merge Sort
2. Quick Sort
3. Strassen’s Matrix Multiplication
3. Decrease and Conquer
1. Insertion Sort
2. 1 Analysis of Insertion sort
3. 2 Implementation
4. Topological Sorting

UNIT V: Dynamic Programming, Greedy Technique 10 Hrs

1. Dynamic Programming, Greedy Technique
2. Dynamic Programming
1. Warshall’s algorithm
2. Floyd’s Algorithm
3. 0/1 Knapsack problem
3. Greedy Technique
1. Prim’s Algorithm
2. Kruskal’s Algorithm
3. Dijikstra’s Algorithm

UNIT VI: Backtracking , Branch and Bound 06 Hrs

For complete syllabus and results, class timetable and more pls download iStudy Syllabus App. Its a light weight, easy to use, no images, no pdfs platform to make students life easier.

Text Books:

1. Algorithms Design by Michael T.Good Rich and Roberto Tamassia, WILEY INDIA EDITION 2009
2. Introduction to the design & Analysis of Algorithms by Anany Levitin
3. Analysis And Design of Algorithms by Nandagopalan, Sapna Publications

Reference Books:

1. Fundamentals of computer Algorithms by Ellis Horowitz Sartaj Sahani Sanguthevar Rajasekaran.
2. Design and Analysis of Algorithm by prabhakar gupta,vineet agarwal, monish varshney.
3. Design Methods and Analysis of Algorithms by S.K.Basu by PHI .
4. http://www.personal.kent.edu/~rmuhamma/Algorithms/algorithm.html
5. http://www.slideshare.net/VinayChinnappaReddy/ada-complete-notes

Suggested List of Student Activities:

Note: The following activities or similar activities for assessing CIE (IA) for 5 marks (Any one)

Student activity like mini-project, surveys, quizzes, etc. should be done in group of 1-2 students.

1. Each group should do any one of the following type activity or any other similar activity related to the course and before conduction, get it approved from concerned course coordinator and programme co-ordinator
2. Each group should conduct different activity and no repeating should occur.

1. Implement 4-Queens problem using Back Tracking.
2. Implement 4-Queens problem using Branching and Bounding.
3. Implement Travelling Salesman problem using Back Tracking.
4. Implement Travelling Salesman problem using Greedy Technique
5. Comparative study of all Asymptotic Notations
6. Seminars
7. Quiz etc.

Course Delivery:

• The course will be delivered through lectures and Power point presentations/ Video
• Course co-ordinator can prepare or download presentations of different topic’s.

Model Question Paper:

(CIE)

1. Explain best, worst and average case analysis.
2. f(n)= 100n+5,analyse for best case.
3. Explain adjacency matrix representation of a graph with example
4. Explain DFS and traverse the given graph using DFS.

Model Question Paper:

PART-A

Answer any SIX questions each carries 5 marks.

1. Write an algorithm to find sum and average of three numbers.
2. What is time complexity? Explain with suitable example.
3. Explain node, vertex, edge in a graph with an example.
4. Explain Travelling salesman problem with suitable example using Brute force technique.
5. Explain and write an algorithm using decrease and conquer technique.
6. Sort the following numbers using Insertion sort: 6 5 4 3 2
7. Write the Prim’s algorithm.
8. Write the applications of Dynamic programming.
9. Explain explicit and implicit constraints with example.

PART-B

Answer any SEVEN full questions each carries 10marks.

1. Explain the following with suitable examples
1. Big-oh notation
2. Big-omega notation
2. f(n)= 100n+5,analyse for best, worst and average cases.
3. Explain the following,
1. sorting
2. searching
3. graph problems
4. Write an algorithm of DFS and explain.
5. Write and explain Bubble sort algorithm with suitable example.
6. Write the formulas and apply Strassen’s matrix multiplication for the following,
7. Obtain Topological ordering for the following graph.
8. Solve the following instance for 0/1 knapsack problem using Dynamic programming.

n = 4, p = [4, 2, 1, 8] w = [3, 1, 7, 9] M=10

9. Find the single source shortest path for the following graph
10. Explain n-queens problem and write the solution space tree for 4 queens

For detail syllabus of all other subjects of BE Information Sci, C15 scheme do visit Information Sci 4th Sem syllabus for C15 scheme.

Dont forget to download iStudy Syllabus App for latest syllabus and results, class timetable and more.