18CS42: Design and Analysis of Algorithms IS Syllabus for BE 4th Sem 2018 Scheme VTU

Design and Analysis of Algorithms detailed Syllabus for Information Science Engineering (IS), 2018 scheme has been taken from the VTUs official website and presented for the VTU students. For Course Code, Subject Names, Teaching Department, Paper Setting Board, Theory Lectures, Tutorial, Practical/Drawing, Duration in Hours, CIE Marks, Total Marks, Credits and other information do visit full semester subjects post given below. The Syllabus PDF files can also be downloaded from the official website of the university.

For all other VTU IS 4th Sem Syllabus for BE 2018 Scheme, do visit VTU IS 4th Sem Syllabus for BE 2018 Scheme Subjects. The detailed Syllabus for design and analysis of algorithms is as follows.

Course Learning Objectives:

For the complete Syllabus, results, class timetable, and many other features kindly download the iStudy App
It is a lightweight, easy to use, no images, and no pdfs platform to make students’s lives easier.
.

Module 1

Introduction: What is an Algorithm? (T2:1.1), Algorithm Specification (T2:1.2), Analysis Framework (T1:2.1), Performance Analysis: Space complexity, Time complexity (T2:1.3). Asymptotic Notations: Big-Oh notation (O), Omega notation (Q), Theta notation (&), and Little-oh notation (o), Mathematical analysis of Non-Recursive and recursive Algorithms with Examples (T1:2.2, 2.3, 2.4). Important Problem Types: Sorting, Searching, String processing, Graph Problems, Combinatorial Problems. Fundamental Data Structures: Stacks, Queues, Graphs, Trees, Sets and Dictionaries. (T1:1.3,1.4). RBT: L1, L2, L3

Module 2

Divide and Conquer: General method, Binary search, Recurrence equation for divide and conquer, Finding the maximum and minimum (T2:3.1, 3.3, 3.4), Merge sort, Quick sort (T1:4.1, 4.2), Strassen’s matrix multiplication (T2:3.8), Advantages and Disadvantages of divide and conquer. Decrease and Conquer Approach: Topological Sort. (T1:5.3). RBT: L1, L2, L3

Module 3

Module 4

Dynamic Programming: General method with Examples, Multistage Graphs (T2:5.1, 5.2). Transitive Closure: Warshall’s Algorithm, All Pairs Shortest Paths: Floyd’s Algorithm, Optimal Binary Search Trees, Knapsack problem ((T1:8.2, 8.3, 8.4), Bellman-Ford Algorithm (T2:5.4), Travelling Sales Person problem (T2:5.9), Reliability design (T2:5.8). RBT: L1, L2, L3 10

Module 5

Backtracking: General method (T2:7.1), N-Queens problem (T1:12.1), Sum of subsets problem (T1:12.1), Graph coloring (T2:7.4), Hamiltonian cycles (T2:7.5). Programme and Bound: Assignment Problem, Travelling Sales Person problem (T1:12.2), 0/1 Knapsack problem (T2:8.2, T1:12.2): LC Programme and Bound solution (T2:8.2), FIFO Programme and Bound solution (T2:8.2). NP-Complete and NP-Hard problems: Basic concepts, non-deterministic algorithms, P, NP, NP-Complete, and NP-Hard classes (T2:11.1). RBT: L1, L2, L3

Course Outcomes:

Question Paper Pattern:

The question paper will have ten questions.
Each full Question consisting of 20 marks
There will be 2 full questions (with a maximum of four sub questions) from each module.
Each full question will have sub questions covering all the topics under a module.
The students will have to answer 5 full questions, selecting one full question from each module.

Textbooks:

Introduction to the Design and Analysis of Algorithms, Anany Levitin:, 2rd Edition, 2009. Pearson.
Computer Algorithms/C++, Ellis Horowitz, Satraj Sahni and Rajasekaran, 2nd Edition, 2014, Universities Press

Reference Books:

For detail Syllabus of all other subjects of BE 4th Sem Information Science Engineering, visit (IS) 4th Sem Syllabus Subjects.

For all (CBSE & Non-CBSC) BE results, visit VTU BE all semester results direct links.

InI KA