This course is designed to introduce the students to design and analyse algorithms in terms of efficiency and correctness. The course focuses on highlighting difference between various problem solving techniques for efficient algorithm design.
At the end of the course, students should be able to:
Unit 1
Algorithm Design Techniques: Iterative technique: Applications to Sorting and Searching (review), their correctness and analysis. Divide and Conquer: Application to Sorting and Searching (review of binary search), merge sort, quick sort, their correctness and analysis.
Dynamic Programming: Application to various problems (for reference; Weighted Interval Scheduling, Sequence Alignment, Knapsack), their correctness and analysis. Greedy Algorithms: Application to various problems, their correctness and analysis.
Unit 2
More on Sorting and Searching: Heapsort, Lower Bounds using decision trees, sorting in Linear Time – Bucket Sort, Radix Sort and Count Sort, Medians & Order Statistics, complexity analysis and their correctness.
Unit 3
Advanced Analysis Technique: Amortized analysis.
Unit 4
Graphs: Graph Algorithms – Breadth First Search, Depth First Search and its Applications.
b)Implement Merge Sort(The program should report the number of comparisons)
Kleinberg, J., & Tardos, E. (2013). Algorithm Design. 1st edition. Pearson Education India.
Cormen, T.H., Leiserson,C.E. Rivest, R.L., & Stein, C.(2015). Introduction to Algorithms. 3rd edition. PHI.
Sarabasse & Gleder A. V. (1999). Computer Algorithm – Introduction to Design and Analysis. 3rd edition. Pearson Education.
Use of ICT tools in conjunction with traditional class room teaching methods
Interactive sessions
Class discussions
Written tests, assignments, quizzes, presentations as announced by the instructor in the class
Brute Force Algorithm, divide and conquer, greedy, dynamic programming approaches, inplace algorithm, best / average / worst case running time of algorithms.
Disclaimer: Details on this page are subject to change as per University of Delhi guidelines. For latest update in this regard please refer to the University of Delhi website here.
Cookie | Duration | Description |
---|---|---|
cookielawinfo-checkbox-analytics | 11 months | This cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Analytics". |
cookielawinfo-checkbox-functional | 11 months | The cookie is set by GDPR cookie consent to record the user consent for the cookies in the category "Functional". |
cookielawinfo-checkbox-necessary | 11 months | This cookie is set by GDPR Cookie Consent plugin. The cookies is used to store the user consent for the cookies in the category "Necessary". |
cookielawinfo-checkbox-others | 11 months | This cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Other. |
cookielawinfo-checkbox-performance | 11 months | This cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Performance". |
viewed_cookie_policy | 11 months | The cookie is set by the GDPR Cookie Consent plugin and is used to store whether or not user has consented to the use of cookies. It does not store any personal data. |