EC (1270) - 27.07.
2024
DSC10/DSC07/GE7a: DESIGN AND ANALYSIS OF ALGORITHMS
CREDIT DISTRIBUTION, ELIGIBILITY AND PRE-REQUISITES OF THE COURSE
Course title Credits Credit distribution of the course Eligibility Pre-requisite
& Code criteria of the course
Lecture Tutorial Practical/ (if any)
Practice
Design and 4 3 0 1 Pass in Data
Analysis of Class XII Structures
Algorithms
Course Objectives
The course is designed to develop understanding of different algorithm design techniques and
use them for problem solving. The course shall also enable the students to verify correctness of
algorithms and analyze their time complexity.
Learning Outcomes
On successful completion of the course, students will be able to:
● Compute and compare the asymptotic time complexity of algorithms.
● Use appropriate algorithm design technique(s) for solving a given problem.
Syllabus
Unit 1 (8 hours)
Searching, Sorting, Selection: Linear Search, Binary Search, Insertion Sort, Selection Sort,
Bubble Sort, Heapsort, Linear Time Sorting, running time analysis and correctness.
Unit 2 (5 hours)
Graphs: Review of graph traversals, graph connectivity, testing bipartiteness, Directed Acyclic
Graphs and Topological Ordering, Minimum Spanning Trees.
Unit 3 (8 hours)
35
EC (1270) - 27.07.2024
Divide and Conquer: Introduction to divide and conquer technique, Merge Sort, Quick Sort,
Randomised quicksort, Maximum-subarray problem, Strassen’s algorithm for matrix
multiplication.
Unit 4 (5 hours)
Greedy algorithms: Introduction to the Greedy algorithm design approach, application to
minimum spanning trees, fractional knapsack problem, and analysis of time complexity.
Unit 5 (5 hours)
Dynamic Programming: Introduction to the Dynamic Programming approach, application to
subset sum, integer knapsack problems, and analysis of time complexity.
Unit 6 (4 hours)
Hash Tables Hash Functions, Collision resolution schemes.
Essential/recommended readings
1. Cormen, T.H., Leiserson, C.E., Rivest, R. L., Stein C. Introduction to Algorithms, 4th edition,
Prentice Hall of India, 2022.
2. Kleinberg, J., Tardos, E. Algorithm Design, 1st edition, Pearson, 2013.
Additional references
1. Basse, S., Gelder, A. V., Computer Algorithms: Introduction to Design and Analysis, 3rd
edition, Pearson, 1999.
Practical List (If any): (30 Hours)
1. Write a program to sort the elements of an array using Insertion Sort (The program
should report the number of comparisons).
2. Write a program to sort the elements of an array using Merge Sort (The program should
report the number of comparisons).
3. Write a program to sort the elements of an array using Heap Sort (The program should
report the number of comparisons).
4. Write a program to multiply two matrices using the Strassen’s algorithm for matrix
multiplication
5. Write a program to sort the elements of an array using Radix Sort.
6. Write a program to sort the elements of an array using Bucket Sort.
36
EC (1270) - 27.07.2024
7. Display the data stored in a given graph using the Breadth-First Search algorithm.
8. Display the data stored in a given graph using the Depth-First Search algorithm.
9. Write a program to determine a minimum spanning tree of a graph using the Prim’s
algorithm.
10. Write a program to implement Dijkstra's algorithm to find the shortest paths from a
given source node to all other nodes in a graph.
11. Write a program to solve the weighted interval scheduling problem.
12. Write a program to solve the 0-1 knapsack problem.
For the algorithms at S.No 1, 2 and 3 , test run the algorithm on 100 different input sizes varying
from 30 to 1000. For each size find the number of comparisons averaged on 10 different input
instances; plot a graph for the average number of comparisons against each input size.
Compare it with a graph of nlogn.
DSC-A3/DSE: DATA MINING-I
CREDIT DISTRIBUTION, ELIGIBILITY AND PRE-REQUISITES OF THE COURSE
Course Credits Credit distribution of the course Eligibility Pre-requisite
title & criteria of the course
Code (if any)
Lecture Tutorial Practical/
Practice
Data 4 3 0 1 Programming
Passed
Mining - using Python
12th class
I with
Mathema
tics
Course Objectives
This course aims to introduce data mining techniques and their application on real-life datasets.
The students will learn to pre-process the dataset and make it ready for application of data
mining techniques. The course will focus on three main techniques of data mining i.e.
Classification, Clustering and Association Rule Mining. Different algorithms for these techniques
37
