Scribd Logo
Upload

Welcome to Scribd!

  • 11 views

    Design and Analysis of Algorithms: Course Objectives

    Uploaded by

    techwizseetha
    This document outlines the course objectives, outcomes, units, and content for an algorithms course. The course aims to introduce algorithm design techniques and analyze time and space complexity. It covers fundamental topics like recursion, divide and conquer, greedy algorithms, dynamic programming, backtracking, and branch and bound. Specific problems addressed include the knapsack problem, shortest paths, optimal binary search trees, traveling salesman, and the n-queens problem. Textbooks and websites for further reference are also provided.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Design and Analysis of Algorithms: Course Objectives

    Uploaded by

    techwizseetha
    11 views2 pages
    This document outlines the course objectives, outcomes, units, and content for an algorithms course. The course aims to introduce algorithm design techniques and analyze time and space complexity. It covers fundamental topics like recursion, divide and conquer, greedy algorithms, dynamic programming, backtracking, and branch and bound. Specific problems addressed include the knapsack problem, shortest paths, optimal binary search trees, traveling salesman, and the n-queens problem. Textbooks and websites for further reference are also provided.

    Original Description:

    daa

    Original Title

    aqxwer

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document outlines the course objectives, outcomes, units, and content for an algorithms course. The course aims to introduce algorithm design techniques and analyze time and space complexity. It covers fundamental topics like recursion, divide and conquer, greedy algorithms, dynamic programming, backtracking, and branch and bound. Specific problems addressed include the knapsack problem, shortest paths, optimal binary search trees, traveling salesman, and the n-queens problem. Textbooks and websites for further reference are also provided.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    11 views2 pages

    Design and Analysis of Algorithms: Course Objectives

    Uploaded by

    techwizseetha
    This document outlines the course objectives, outcomes, units, and content for an algorithms course. The course aims to introduce algorithm design techniques and analyze time and space complexity. It covers fundamental topics like recursion, divide and conquer, greedy algorithms, dynamic programming, backtracking, and branch and bound. Specific problems addressed include the knapsack problem, shortest paths, optimal binary search trees, traveling salesman, and the n-queens problem. Textbooks and websites for further reference are also provided.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 2

    DESIGN AND ANALYSIS OF ALGORITHMS

    Course Objectives:

    1. To introduce the fundamental strategies of different algorithm design techniques.


    2. Solving various problems using techniques introduced in this course.
    3. Analyze the algorithm’s / program’s efficiency in terms of time and space complexity.
    Course Outcomes:
    On successful completion of this course students will be able to:
    1. Analyze / compare the given algorithm.
    2. Compute the time complexity/space complexity of any recursive/non recursive algorithms.
    3. Solve any given problem using the fundamental design techniques.

    Unit: I
    Introduction: what is an Algorithm – contradiction- mathematical induction -Efficiency of algorithms – average and worst-case –
    the order of - asymptotic notation.
    Analysis Of Algorithms: Analyzing control structures – solving recurrences – homogeneous recurrences – inhomogeneous
    recurrences.

    Unit: II
    Divide & Conquer Greedy Method
    Divide And Conquer Method: General method -– finding maximum and minimum - Karatsuba algorithm for fast multiplication
    strassen’s matrix multiplication- Search in a Row-wise and Column-wise Sorted 2D Array – Tiling problem

    Greedy Method: General method - Knapsack problem – job sequencing with deadlines– optimal storage on tapes – optimal merge
    patterns - Dijkstra’s algorithm – Huffman coding-water connection problem

    Unit: III
    Brute force and Dynamic Programming
    Brute Force:Closest pair and convex hull problems-Exhaustive search- traveling salesman problem-Assignment problem
    Dynamic Programming: General method –Principle of optimality – multi stage graph - all pairs shortest paths - Warshall’s and
    Floyd’s algorithms – optimal binary search tree – 0 / 1 knapsack problem – traveling salesman problem

    Unit: IV
    Backtracking: General method - n queen’s problem – sum of subsets – graph coloring – Hamiltonian cycle – knapsack problem-
    sudoku-Rat in a maze

    Unit: V
    Branch And Bound: Least Cost search – 15 puzzle – control abstractions for LC search – bounding – FIFO Branch and bound –
    LC branch and Bound - Knapsack problem: LC branch and bound – FIFO branch and bound solutions – Traveling salesman
    problem – assignment problem

    Content beyond Syllabus:


    1. Algebraic problems
    2. NP Hard and NP complete problems
    3. Approximation Algorithms

    Text Books:
    1. Gilles Brassard and Paul Brately, Fundamentals of Algorithmics, Prentice Hall of India, 1997.
    2. AnanyLevitin, Introduction to Design and Analysis of Algorithms, Pearson Education Inc., 2005.
    3. Ellis Horowitz, SartajSahni and S. Rajasekaran, Fundamentals of Computer Algorithms , Galgotia Publications, 2 nd
    Edition, New Delhi, 2003.

    Reference Books:
    1. Aho.A.V, Hopcroft.J.E and Ullman.J.D, Design and analysis of Algorithms, Pearson education, 3rd edition, 2000.
    2. Thomas.H.Cormen, Charles E. Leiserson, Ronald L.Rivest, Introduction to Algorithms, Prentice Hall of India Pvt. Ltd,
    1998.
    Websites:
    1. www.algo-class.org/
    2. http://nptel.iitm.ac.in/video.php?subjectId=106101060
    3. http://www.freetechbooks.com/design-and-analysis-of-algorithms-course-notes-t349.html
    4. http://www.cse.iitd.ernet.in/~ssen/csl356/notes/root.pdf

    REMOVED TOPICS

    Unit II

    Divide & Conquer-Binary search, Merge sort,Quick sort

    Greedy- Prim’s algorithm – Kruskal’s algorithm

    Unit IV
    Tree traversals: Depth first search – articulation points – breadth first search

    ADDED TOPICS

    Unit II

    Divide And Conquer Method: General method - Karatsuba algorithm for fast multiplication Search in a Row-wise and
    Column-wise Sorted 2D Array – Tiling problem

    Greedy- Huffman coding-water connection problem


    Unit III

    Brute Force :Closest pair and convex hull problems-Exhaustive search- traveling salesman problem-Assignment
    problem

    Unit IV

    Sudoku-Rat in a maze

    You might also like