Design & Analysis of Algorithms

Home

• Announcements Forum
• Course introduction is here.

  Overview

  Prerequisite Courses

  Following courses from second and third year of computer engineering are required to be studied:
  

  Discrete MathematicsData Structures and AlgorithmsAdvanced Data StructuresTheory of Computation

  Course Objectives

  • To develop problem solving abilities using mathematical theories 
  • To analyze the performance of algorithms 
  • To study algorithmic design strategies

  Course Outcomes

  On completion of the course, student will be able to:
  

  • Formulate the problem 
  • Analyze the asymptotic performance of algorithms 
  • Decide and apply algorithmic strategies to solve given problem 
  • Find optimal solution by applying various methods

• Syllabus and Notes

• Unit 1

  Unit 2

  Unit 3

  Unit 4

  Unit 5

  Unit 6

  Unit 1

  ×

  Fundamentals

  • The Role of Algorithms in Computing - What are algorithms, Algorithms as technology, Evolution of Algorithms, Design of Algorithm, Need of Correctness of Algorithm, 
  • Confirming correctness of Algorithm – sample examples, Iterative algorithm design issues

  Close

  Unit 2

  ×

  Models and Design

  • Functional Model – Features, Recursive processes, Scope rules, Tail recursion, Checking correctness of Iterative process. 
  • Imperative Model – Basics, Specifications and Prototyping, Stepwise Refinement
  • Proof Rules – Basics, For loops, Goto and Exit loops, Functions and Procedures
  • Problem Solving using Greedy strategy - Knapsack problem, Huffman code generation algorithm

  Close

  Unit 3

  ×

  Abstract Algorithms

  • Dynamic Programming, Divide and Conquer, Greedy strategy, Branch-n-Bound
  • Natural Algorithms – Evolutionary Algorithms and Evolutionary Computing
  • Introduction to Genetic Algorithm, Simulated Annealing, Artificial Neural Network and Tabu Search

  Close

  Unit 4

  ×

  Complexity Theory

  Complexity theory – Counting Dominant operators, Growth rate, upper bounds, asymptotic growth, O, Ω, Ɵ, o and ω notations, polynomial and non-polynomial problems, deterministic and non-deterministic algorithms, P-class problems, NP-class of problems, Polynomial problem reduction NP complete problems- vertex cover and 3-SAT and NP hard problem - Hamiltonian cycle
  

  Close

  Unit 5

  ×

  Amortized Analysis

  • Amortized Analysis – Binary, Binomial and Fibonacci heaps, Dijkstra‘s Shortest path algorithm, Splay Trees, Time-Space tradeoff, Introduction to Tractable and Non-tractable Problems, Introduction to Randomized and Approximate algorithms, 
  • Embedded Algorithms: Embedded system scheduling (power optimized scheduling algorithm), sorting algorithm for embedded systems.

  Close

  Unit 6

  ×

  Multithreaded and Distributed Algorithms

  • Multithreaded Algorithms - Introduction, Performance measures, Analyzing multithreaded algorithms, Parallel loops, Race conditions. 
  • Problem Solving using Multithreaded Algorithms - Multithreaded matrix multiplication, Multithreaded merge sort. 
  • Distributed Algorithms - Introduction, Distributed breadth first search, Distributed Minimum Spanning Tree. 
  • String Matching - Introduction, The Naive string matching algorithm, The Rabin-Karp algorithm

  Close
• Previous Years' Exams
  

  Question Papers

  April 2019October 2018April 2018

• Have Doubts?

• Forum

  Ask your doubts regarding the subject here. Discuss exam strategies, scores and latest trends in this forum.