Grade "A+" Accredited by NAAC with a CGPA of 3.46
Placements
Grade "A+" Accredited by NAAC with a CGPA of 3.46
Placements

Advanced Algorithms

Download Course Details
Course ID
BHCS 17C
Level
Undergraduate
Program
B.Sc. CS (Hons.)
Semester
Sixth
Credits
6.0
Paper Type
DSE - 3
Method
Lecture & Tutorial

Unique Paper Code: Update Awaited

This course focuses on the study of advanced data structures and algorithms for solving problems efficiently and their theoretical behavior. The course also includes study of network flow algorithms, NP completeness and backtracking.

Learning Outcomes:

At the end of the course, students should be able to:

  • Implement and empirically analyze advanced data-structures like tries, suffix trees.
  • Apply amortized analysis.
  • Develop more sophisticated algorithms using techniques like divide and conquer, dynamic programming, greedy strategy, and augmentation.
  • Prove that certain problems are too hard to admit fast solutions.
  • Develop algorithms using backtracking for the hard problems.

Course Contents

Unit 1
Unit 2
Unit 3
Unit 4
Unit 5
Unit 6

Unit 1

Advanced Data Structures: Skip Lists, Red-Black trees, Splay Trees, Mergeable heaps (Fibonacci heaps), DS for sets – Union-Find Data Structure, Dynamic Tables, Dictionaries, Data structures for strings – Tries, Suffix trees.

Unit 2

Divide and Conquer: Counting Inversions, Closest pair of points, Integer Multiplication.

Unit 3

Greedy Algorithm: Interval Scheduling, Huffman Code, Correctness and Analysis.

Unit 4

Dynamic Programming: Segmented Least Squares, Shortest Paths, Negative Cycles in Graphs.

Unit 5

Network Flows: Max-flow problem, Ford Fulkerson Algorithm, Maximum flows and Minimum Cuts in a network, Bipartite Matching.

Unit 6

NP Completeness: Polynomial time reductions, Efficient Certification and Definition of NP, NP Complete problems, Sequencing problems, Partitioning problems, co-NP and asymmetry of NP. Backtracking: Constructing All Subsets, Constructing All Permutations, Constructing All Paths in a Graph.

Additional Information

Text Books


Cormen, T.H., Leiserson,C.E., Rivest, R.L., & Stein,C.(2010). Introduction to Algorithms. 3rd edition. Prentice-Hall of India Learning Pvt. Ltd.
Kleinberg, J., & Tardos, E. (2013). Algorithm Design. 1st edition. Pearson Education India.

Additional Readings


Basse, S., & Gleder, A. V. (1999). Computer Algorithm – Introduction to Design and Analysis. 3rd edition. Pearson Education.
Dasgupta, S., Papadimitriou,C., & Vazirani, U. (2017). Algorithms. 1st edition. TataMcGraw Hill.
Skiena, S. S. (2008). The Algorithm Design Manual. 2nd edition. Springer-Verlag London

Teaching Learning Process


Use of ICT tools in conjunction with traditional class room teaching methods
Interactive sessions
Class discussions

Assessment Methods

Written tests, assignments, quizzes, presentations as announced by the instructor in the class.

Keywords

Algorithms, Analysis, Network Flows, NP Completeness.

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.