Design and Analysis of Algorithms - Syllabus
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-1This 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-2This 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-3This 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-1This topic covers the implementation and analysis of basic algorithms such as GCD and Fibonacci Number, including their time and space complexity.
-
Searching Algorithms
IT-2This topic focuses on searching algorithms, specifically Sequential Search, and its analysis.
-
Sorting Algorithms
IT-3This topic explores sorting algorithms, including Bubble, Selection, and Insertion Sort, and their analysis.
Key Topics
-
Distributed Database Concepts
DI-1Introduction to distributed database concepts and their advantages.
-
Data Fragmentation, Replication and Allocation
DI-2Techniques for data fragmentation, replication, and allocation in distributed databases.
-
Distributed Database Design Techniques
DI-3Methods and approaches for designing distributed databases.
Key Topics
-
Optimization Problems and Greedy Algorithms
GR-1Introduction to optimization problems and the concept of optimal solutions, with an overview of greedy algorithms and their elements.
-
Greedy Algorithm Applications
GR-2Exploration of various applications of greedy algorithms, including fractional knapsack, job sequencing with deadlines, Kruskal's algorithm, Prim's algorithm, and Dijkstra's algorithm.
-
Huffman Coding
GR-3Introduction to Huffman coding, including its purpose, prefix codes, and the Huffman coding algorithm, along with its analysis.
Key Topics
-
DHCP Principle
DY-1Understanding the fundamental concepts and principles of Dynamic Host Configuration Protocol (DHCP) and its role in network administration.
-
DHCP Server Configuration
DY-2Configuring and setting up a DHCP server to assign IP addresses and other network settings to clients on a network.
-
DHCP Options, Scope, Reservation and Relaying
DY-3Understanding and configuring DHCP options, scope, reservation, and relaying to customize and optimize DHCP services.
-
DHCP Troubleshooting
DY-4Identifying and resolving common issues and problems related to DHCP configuration and operation.
-
String Editing
DY-5Dynamic programming approach to string editing problems, including edit distance and longest common subsequence.
-
Zero-One Knapsack Problem
DY-6Dynamic programming solution to the 0/1 knapsack problem, including its analysis and variations.
-
Floyd Warshall Algorithm
DY-7Dynamic programming algorithm for finding shortest paths in weighted graphs, including its analysis and applications.
-
Travelling Salesman Problem
DY-8Dynamic programming approach to the travelling salesman problem, including its analysis and variations.
-
Memoization Strategy
DY-9Technique of memoization in dynamic programming, including its benefits and trade-offs.
-
Dynamic Programming vs Memoization
DY-10Comparison of dynamic programming and memoization, highlighting their similarities and differences.
Key Topics
-
Concept of Backtracking
BA-1This 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-2This 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.
Key Topics
-
Numerical Differentiation
NU-1Concept of differentiation, differentiating continuous functions using two-point forward and backward difference formulae, and three-point formula. Also, differentiating tabulated functions using Newton's differences.
-
Maxima and Minima of Tabulated Functions
NU-2Finding maxima and minima of tabulated functions using numerical differentiation methods.
-
Numerical Integration
NU-3Concept of integration, Newton-Cote's quadrature formulae including trapezoidal rule, Simpson's 1/3 rule, and Simpson's 3/8 rule.
-
Trapezoidal Rule
NU-4Approximating definite integrals using the trapezoidal rule, including single-segment and multi-segment trapezoidal rule.
-
Simpson's Rules
NU-5Approximating definite integrals using Simpson's 1/3 rule and Simpson's 3/8 rule, including single-segment and multi-segment Simpson's rules.
-
Primality Testing
NU-6Introduction to primality testing, including the Miller-Rabin randomized primality test and its analysis.
-
Miller-Rabin Randomized Primality Test
NU-7The Miller-Rabin randomized primality test, including its algorithm, analysis, and applications.
Key Topics
-
Tractable and Intractable Problems
NP-1Understanding the concept of polynomial time and super polynomial time complexity, and its significance in determining the tractability of problems.
-
Complexity Classes
NP-2Introduction to complexity classes P, NP, NP-Hard, and NP-Complete, and their relationships.
-
NP Complete Problems
NP-3Study of NP Complete problems, including reducibility, Cook's Theorem, and proofs of NP Completeness for CNF-SAT, Vertex Cover, and Subset Sum.
-
Approximation Algorithms
NP-4Concept of approximation algorithms, with a focus on the Vertex Cover Problem and 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.