Course Content

Other Courses

Tribhuvan university CSIT 2074 Syllabus Design and Analysis of Algorithms

Design and Analysis of Algorithms - Syllabus

Course Overview and Structure
Syllabus Notes Old Questions Unit Wise Questions Question Bank

Embark on a profound academic exploration as you delve into the Design and Analysis of Algorithms course (DAA) within the distinguished Tribhuvan university's CSIT department. Aligned with the 2074 Syllabus, this course (CSC314) seamlessly merges theoretical frameworks with practical sessions, ensuring a comprehensive understanding of the subject. Rigorous assessment based on a 60 + 20 + 20 marks system, coupled with a challenging passing threshold of , propels students to strive for excellence, fostering a deeper grasp of the course content.

This 3 credit-hour journey unfolds as a holistic learning experience, bridging theory and application. Beyond theoretical comprehension, students actively engage in practical sessions, acquiring valuable skills for real-world scenarios. Immerse yourself in this well-structured course, where each element, from the course description to interactive sessions, is meticulously crafted to shape a well-rounded and insightful academic experience.


Course Description: This course introduces basic elements of the design and analysis of computer algorithms. Topics include asymptotic notations and analysis, divide and conquer strategy, greedy methods, dynamic programming, basic graph algorithms, NP-completeness, and approximation algorithms. For each topic, beside in-depth coverage, one or more representative problems and their algorithms shall be discussed. Course Objectives: 

  •    Analyze the asymptotic performance of algorithms.
  •    Demonstrate a familiarity with major algorithm design techniques 
  •    Apply important algorithmic design paradigms and methods of analysis. 
  •    Solve simple to moderately difficult algorithmic problems arising in applications.
  •    Able to demonstrate the hardness of simple NP-complete problems

Units

Key Topics

  • Algorithms and Their Properties
    FO-1

    This topic covers the definition and properties of algorithms, including the RAM model, time and space complexity, and detailed analysis of algorithms such as the factorial algorithm. It also introduces the concept of aggregate analysis.

  • Asymptotic Notations
    FO-2

    This topic explores the different asymptotic notations, including Big-O, Big-Ω, and Big-Ө, their geometrical interpretation, and examples of their application.

  • Recurrences and Recursive Algorithms
    FO-3

    This topic covers recursive algorithms and recurrence relations, including methods for solving recurrences such as the recursion tree method, substitution method, and application of the master theorem.

Key Topics

  • Basic Algorithms
    IT-1

    This topic covers the implementation and analysis of basic algorithms such as GCD and Fibonacci Number, including their time and space complexity.

  • Searching Algorithms
    IT-2

    This topic focuses on searching algorithms, specifically Sequential Search, and its analysis.

  • Sorting Algorithms
    IT-3

    This topic explores sorting algorithms, including Bubble, Selection, and Insertion Sort, and their analysis.

3.1. Searching Algorithms: Binary Search, Min-Max Finding and their Analysis

3.2. Sorting Algorithms: Merge Sort and Analysis, Quick Sort and Analysis (Best Case, Worst

Case and Average Case), Heap Sort (Heapify, Build Heap and Heap Sort Algorithms and

their Analysis), Randomized Quick sort and its Analysis

3.3. Order Statistics: Selection in Expected Linear Time, Selection in Worst Case Linear Time

and their Analysis.


4.1. Optimization Problems and Optimal Solution, Introduction of Greedy Algorithms,

Elements of Greedy Strategy.

4.2. Greedy Algorithms: Fractional Knapsack, Job sequencing with Deadlines, Kruskal’s

Algorithm, Prims Algorithm, Dijkstra’s Algorithm and their Analysis

4.3. Huffman Coding: Purpose of Huffman Coding, Prefix Codes, Huffman Coding

Algorithm and its Analysis


5.1. Greedy Algorithms vs Dynamic Programming, Recursion vs Dynamic Programming,

Elements of DP Strategy

5.2. DP Algorithms: Matrix Chain Multiplication, String Editing, Zero-One Knapsack

Problem, Floyd Warshwall Algorithm, Travelling Salesman Problem and their

Analysis.

5.3. Memoization Strategy, Dynamic Programming vs Memoization


Key Topics

  • Concept of Backtracking
    BA-1

    This topic introduces the concept of backtracking, a problem-solving strategy that involves recursively exploring all possible solutions and backtracking when a dead end is reached. It also compares and contrasts backtracking with recursion.

  • Backtracking Algorithms
    BA-2

    This topic covers various backtracking algorithms, including those for solving the subset-sum problem, zero-one knapsack problem, and N-queen problem, along with their analysis.

7.1. Number Theoretic Notations, Euclid’s and Extended Euclid’s Algorithms and their

Analysis.

7.2. Solving Modular Linear Equations, Chinese Remainder Theorem, Primility Testing: Miller-

Rabin Randomized Primility Test and their Analysis


8.1. Tractable and Intractable Problems, Concept of Polynomial Time and Super Polynomial

Time Complexity

8.2. Complexity Classes: P, NP, NP-Hard and NP-Complete

8.3. NP Complete Problems, NP Completeness and Reducibility, Cooks Theorem, Proofs of NP

Completeness (CNF-SAT, Vertex Cover and Subset Sum)

8.4. Approximation Algorithms: Concept, Vertex Cover Problem, Subset Sum Problem


Lab works

Laboratory Works:

This course can be learnt in effective way only if we give focus is given in practical

aspects of algorithms and techniques discussed in class. Therefore student should be able

to implement the algorithms and analyze their behavior.

For the laboratory work, students should implement the following algorithms in C/ C++

and perform their analysis for time and space complexity.

1. Basic iterative algorithms GCD algorithm, Fibonacci Sequences, Sequential and Binary

Search.

2. Basic iterative sorting algorithms: Bubble Sort, selection Sort, Insertion Sort.

3. Binary Search with Divide and conquer approach.

4. Merge Sort, Heap sort, Quick Sort, Randomized Quick Sort.

5. Selection Problem with divide and Conquer approach

6. Fractional Knapsack Problem, Job sequencing with deadline, Kruskal’s algorithm, Prims

algorithm, Dijkstra’s Algorithm

7. Implement the dynamic programming algorithms.

8. Algorithms using Backtracking approach.

9. Implement approximation Algorithm.