🌱

Dec 15, 20243 min read

UE23CS241B: Design and Analysis of Algorithms

Algorithms play a key role in science and practice of computing. Learning algorithm design technique is a valuable endeavour from practical standpoint and algorithm design techniques have considerable utility as general problem solving strategies, applicable to problems beyond computing. This course includes classic problems of computer science, application of design techniques and analysis in terms of time and space.

Course Objectives

  • Learn various algorithm design techniques and apply appropriate algorithmic design techniques for specific problems.
  • Learn to design and analyze algorithms with an emphasis on resource utilization in terms of time and space
  • Learn to trade space for time in algorithmic design using input enhancement and per-structuring.
  • Learn the limitations of algorithmic power and techniques to handle these limitations

Course Outcomes

  • Identify the design technique used in an algorithm
  • Design and implement efficient algorithms for practical and unseen problems and analyze these algorithms using quantitative evaluation.
  • Analyse time efficiency over trading space
  • Understand the limits of algorithms and the ways to cope with the limitations.

Course Content

U1: Introduction and Brute Force

Algorithms, Fundamentals of Algorithmic Problem Solving, Important Problem Types. Analysis of Algorithm Efficiency: Analysis Framework, Asymptotic Notations and Basic Efficiency Classes, Mathematical Analysis of Non Recursive and Recursive Algorithms. Brute Force: Selection Sort, Bubble Sort, Sequential Search, Brute Force String Matching, Exhaustive Search.

U2: Decrease and Conquer & Divide-and-Conquer

Decrease-and-Conquer: Decrease by constant number algorithms - Insertion Sort, Topological Sorting, Algorithms for Generating Combinatorial Objects, Decrease-by-a-Constant-Factor Algorithms – Fake Coin Problem, Russian Peasant Multiplication, Josephus problem, Decrease-by-Variable-Size Algorithms – Computing a median and the selection problem. Divide-and-Conquer: Master Theorem, Merge Sort, Quick Sort, Binary Search, Binary Tree Traversals, Complexity analysis for finding the height of BST, Multiplication of Large Integers, Strassen’s Matrix Multiplication.

U3: Transform-and-Conquer Space and Time Tradeoffs & Greedy Technique

Transform and Conquer: Pre-sorting, Heap Sort, Red-Black Tree Construction and Time complexity Analysis for insert and search operation, 2-3 Trees and B Tree: insertion, deletion, searching, and time complexity analysis. Space and Time Tradeoffs: Sorting by Counting, Input Enhancement in String Matching - Horspool’s and Boyer-Moore Algorithms. Greedy Technique: Prim’s Algorithm, Kruskal’s Algorithm and union-find algorithm, Dijkstra’s Algorithm, Huffman Trees.

U4: Coping with the Limitations of Algorithm Power & Dynamic Programming, Dynamic Programming

Computing a Binomial Coefficient, The Knapsack Problem and Memory Functions, Warshall’s and Floyd’s Algorithms. Limitations of Algorithm Power: Lower-Bound Arguments, Decision Trees, P, NP, and NP-Complete, NP-Hard Problems. Coping with the Limitations of Algorithm Power: Backtracking, Branch-and-Bound.

prerequisites: UE23CS251B

Graph View

Backlinks