Skip to Main Content

Design and Analysis of Algorithm course code (CS3613): Course Outlines

The Design and analysis of algorithms is the determination of the amount of resources (such as time and storage) necessary to execute them. Most algorithms are designed to work with inputs of arbitrary length.

Course Objectives

Goals:

Students should be able to Design and Analyze intermediate level

algorithms for correctness, completeness and discuss complexity trade-offs.

Learning Objectives: Students should be able to

  1. Design algorithms using different algorithms design techniques i.e. Brute Force, Divide and Conquer, Dynamic Programming, Greedy Algorithms
  2. Analyze the time and space complexity of different algorithms by using standard analysis techniques for recursive and non-recursive algorithms.
  3. Discuss on Asymptotic notations, standard complexity classes and representation of time complexities in asymptotic notations of standard complexity functions
  4. Describe, compare, analyze, and solve general algorithmic problem types: Sorting, Searching, String Processing, Graph.
  5. Implement the algorithms, compare the implementations empirically, and apply fundamental algorithms knowledge to solve real-world problems.

Understanding of P, NP, NPC, NPH problems, NP-Completeness and Approximate Probl

Course Outlines

Course Policies / Guidelines, Introduction / Overview, Basics of Algorithms, Mathematical Foundation

Growth of Function, Asymptotic Notations, Time and Space Complexity, Iterative Algorithms Analysis, Algorithms Constructs, Fibonacci, and Factorial Algorithms

Sorting (Bubble, Selection, Insertion, Counting, Radix)

Recursive Algorithms, Analysis of Recursive Algorithms, Recurrence Tree, Recurrence Relation

Iterative Substitution, Telescoping Sum, Divide and Conquer Approach, Sorting (Merge Sort, Quick Sort), Fibonacci and Factorial Recursive Algorithms

Analysis of Data Structures (Stack, Queue, Linked List, Hash Table, Binary Tree)

Graph Theory, Graph Terminology, Representation of Graphs, Graph Traversal (BFS & DFS)

Midterm, Midterm Solution

Optimization Problems, Greedy Algorithms, Shortest Path Finding in Graph (Dijkstra’s Algorithm)

Greedy Algorithms: Minimum Spanning Trees (Kruskal’s Algorithm, Prim’s Algorithm), Huffman Coding for Data Compression

Dynamic Programming, Memmoized Algorithms, Tabular Method, Knapsack Problem.

Dynamic Programming: Matrix Multiplication, Matrix Chain Multiplication Problem

String Matching, Longest Common Subsequences

NP Complete Problems and Solutions using Approximation Algorithms

Approximation Algorithms

Revision, Project Presentations

Related Books

Textbooks