CP7111 syllabus - Advanced Data Structures Lab

CP7111                        ADVANCED DATA STRUCTURES LABORATORY                    L T P C

                0 0 4 2

OBJECTIVES:

1. To learn to implement iterative and recursive algorithms.

2. To learn to design and implement algorithms using hill climbing and dynamic

     programming techniques.

3. To learn to implement shared and concurrent objects.

4. 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:

1. Implementation of graph search algorithms.

2. Implementation and application of network flow and linear programming problems.

3. Implementation of algorithms using the hill climbing and dynamic programming

design techniques.

4. Implementation of recursive backtracking algorithms.

5. Implementation of randomized algorithms.

6. Implementation of various locking and synchronization mechanisms for concurrent

linked lists, concurrent queues, and concurrent stacks.

7. Developing applications involving concurrency.

TOTAL :60 PERIODS

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.