CP7111 ADVANCED DATA STRUCTURES LABORATORY Syllabus
OBJECTIVES:
To learn to implement iterative and recursive algorithms.
To learn to design and implement algorithms using hill climbing and dynamic programming techniques.
To learn to implement shared and concurrent objects.
To learn to implement concurrent data structures.
LAB EXERCISES:
Each student has to work individually on assigned lab exercises. Lab sessions could be scheduled as one contiguous four-hour session per week or two two-hour sessions per week. There will be about 15 exercises in a semester. It is recommended that all implementations are carried out in Java. If C or C++ has to be used, then the threads library will be required for concurrency. Exercises should be designed to cover the following topics:
Implementation of graph search algorithms.
Implementation and application of network flow and linear programming problems.
Implementation of algorithms using the hill climbing and dynamic programming design techniques.
Implementation of recursive backtracking algorithms.
Implementation of randomized algorithms.
Implementation of various locking and synchronization mechanisms for concurrent linked lists, concurrent queues, and concurrent stacks.
Developing applications involving concurrency.
OUTCOMES:
Upon completion of the course, the students will be able to
1. Design and apply iterative and recursive algorithms.
2. Design and implement algorithms using the hill climbing and dynamic programming and recursive backtracking techniques.
3. Design and implement optimisation algorithms for specific applications.
4. Design and implement randomized algorithms.
5. Design appropriate shared objects and concurrent objects for applications.
6. Implement and apply concurrent linked lists, stacks, and queues.
REFERENCES:
1. Jeff Edmonds, “How to Think about Algorithms”, Cambridge University Press, 2008.
2. M. Herlihy and N. Shavit, “The Art of Multiprocessor Programming”, Morgan Kaufmann, 2008.
3. Steven S. Skiena, “The Algorithm Design Manual”, Springer, 2008.
4. Peter Brass, “Advanced Data Structures”, Cambridge University Press, 2008.
5. S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, “Algorithms” , McGrawHill, 2008.
6. J. Kleinberg and E. Tardos, "Algorithm Design“, Pearson Education, 2006.
7. T. H. Cormen, C.2 E. Leiserson, R. L. Rivest and C. Stein, “Introduction to Algorithms“, PHI Learning Private Limited, 2012.
8. Rajeev Motwani and Prabhakar Raghavan, “Randomized Algorithms”, Cambridge University Press, 1995.
9. A. V. Aho, J. E. Hopcroft, and J. D. Ullman, “The Design and Analysis of Computer Algorithms”, Addison-Wesley, 1975.
10. A. V. Aho, J. E. Hopcroft, and J. D. Ullman,”Data Structures and Algorithms”, Pearson,2006.
ADS HERE !!!