Tribhuvan University

Institute of Science and Technology

Bachelor of Science in Computer Science and Information Technology

Course Title: System Analysis and Design

Course no: CSC315

Semester: V

Nature of course: Theory + Lab

Full Marks: 60 + 20 + 20

Pass Marks: 24 + 8 + 8

Credit Hours: 3

Course Description : This course covers the basic concepts of computers and information technology including introduction, hardware, software, memory, input/output, data representation, database, networks and data communication, Internet, multimedia, and computer security.

Course Objective : 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.

##### 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.

##### Reference Books:
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, “Introduction to algorithms”, Third Edition.. The MIT Press, 2009.
• Ellis Horowitz, SartajSahni, SanguthevarRajasekiaran, “Computer Algorithms”, Second Edition, Silicon Press, 2007.
• Kleinberg, Jon, and Eva Tardos, “ Algorithm Design” , Addison-Wesley, First Edition, 2005