Course Content

Other Courses

Tribhuvan university > CSIT - 2065 Syllabus > Design and Analysis of Algorithms

Design and Analysis of Algorithms - Syllabus

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 () within the distinguished Tribhuvan university's CSIT department. Aligned with the 2065 Syllabus, this course (CSC-303) seamlessly merges theoretical frameworks with practical sessions, ensuring a comprehensive understanding of the subject. Rigorous assessment based on a 80+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 Synopsis: Methods and tools for analyzing different algorithms. Different approaches of designing efficient algorithms like divide and conquer paradigm, greedy paradigm, dynamic programming. Algorithms pertaining various problems like sorting, searching, shortest path, spanning trees, geometric problems etc. NP-complete problems.
Goal:   Competency in analyzing different algorithms encountered. Ability to conquer the problem with efficient algorithm using the algorithm development paradigms.

Units

Unit 1

1.1   Algorithm Analysis: worst, best and average cases, space and time complexities. Mathematical background: asymptotic behavior, solving recurrences.

1.2   Data Structures Review: linear data structures, hierarchical data structures, data structures for representing graphs and their properties. Search structures: heaps, balanced trees, hash tables.


Unit 2

2.1   Divide and Conquer: Concepts, applications, sorting problems(quick, merge), searching (binary), median finding problem and general order statistics, matrix multiplications.

2.2   Greedy Paradigm: Concepts, applications, Knapsack problem, job sequencing, Huffman codes.

2.3   Dynamic Programming: Concepts, applications, Knapsack problem, longest common subsequence, matrix chain multiplications.


Unit 3

3.1   Graph Algorithms: breadth-first and depth-first search and their applications, minimum spanning trees (Prim's and Kruskal's algorithms), shortest path problems (Dijkstra's and flyod's algorithms), algorithm for directed acyclic graphs (DAGs).

3.2   Geometric Algorithms: Concepts, polygon triangulation, Convex hull computation.

3.3   NP Completeness: Introduction, class P and NP, cooks theorem, NP complete problems: vertex cover problem.

3.4   Introductions: Randomized algorithms concepts, randomized quick sort, approximation algorithms concepts, vertex cover problem.