CP7102 ADVANCED DATA STRUCTURES AND ALGORITHMS Syllabus
OBJECTIVES:
To understand the principles of iterative and recursive algorithms.
To learn the graph search algorithms.
To study network flow and linear programming problems.
To learn the hill climbing and dynamic programming design techniques.
To develop recursive backtracking algorithms.
To get an awareness of NP completeness and randomized algorithms.
To learn the principles of shared and concurrent objects.
To learn concurrent data structures.
UNIT I ITERATIVE AND RECURSIVE ALGORITHMS
Iterative Algorithms: Measures of Progress and Loop Invariants-Paradigm Shift: Sequence of Actions versus Sequence of Assertions- Steps to Develop an Iterative Algorithm-Different Types of Iterative Algorithms--Typical Errors-Recursion-Forward versus Backward- Towers of Hanoi-Checklist for Recursive Algorithms-The Stack Frame-Proving Correctness with Strong Induction- Examples of Recursive Algorithms-Sorting and Selecting AlgorithmsOperations on Integers- Ackermann’s Function- Recursion on Trees-Tree TraversalsExamples- Generalizing the Problem - Heap Sort and Priority Queues-Representing
Expressions.
UNIT II OPTIMISATION ALGORITHMS
Optimization Problems-Graph Search Algorithms-Generic Search-Breadth-First Search Dijkstra’s Shortest-Weighted-Path -Depth-First Search-Recursive Depth-First Search-Linear Ordering of a Partial Order- Network Flows and Linear Programming-Hill Climbing-Primal Dual Hill Climbing- Steepest Ascent Hill Climbing-Linear Programming-Recursive Backtracking-Developing Recursive Backtracking Algorithm- Pruning Branches-Satisfiability
UNIT III DYNAMIC PROGRAMMING ALGORITHMS
Developing a Dynamic Programming Algorithm-Subtle Points- Question for the Little BirdSubinstances and Subsolutions-Set of Substances-Decreasing Time and Space-Number of Solutions-Code. Reductions and NP-Completeness-Satisfiability-Proving NP-Completeness- 3-Coloring- Bipartite Matching. Randomized Algorithms-Randomness to Hide Worst CasesOptimization Problems with a Random Structure.
UNIT IV SHARED OBJECTS AND CONCURRENT OBJECTS
Shared Objects and Synchronization -Properties of Mutual Exclusion-The Mora l- The Producer–Consumer Problem -The Readers–Writers Problem-Realities of ParallelizationParallel Programming- Principles- Mutual Exclusion-Time- Critical Sections--Thread Solutions-The Filter Lock-Fairness-Lamport’s Bakery Algorithm-Bounded Timestamps-Lower Bounds on the Number of Locations-Concurrent Objects- Concurrency and CorrectnessSequential Objects-Quiescent Consistency- Sequential Consistency-Linearizability- Formal Definitions- Progress Conditions- The Java Memory Model
UNIT V CONCURRENT DATA STRUCTURES
Practice-Linked Lists-The Role of Locking-List-Based Sets-Concurrent Reasoning- CoarseGrained Synchronization-Fine-Grained Synchronization-Optimistic Synchronization- Lazy Synchronization-Non-Blocking Synchronization-Concurrent Queues and the ABA ProblemQueues-A Bounded Partial Queue-An Unbounded Total Queue-An Unbounded Lock-Free Queue-Memory Reclamation and the ABA Problem- Dual Data Structures- Concurrent Stacks and Elimination- An Unbounded Lock-Free Stack- Elimination-The Elimination Backoff Stack
OUTCOMES:
Upon completion of the course, the students will be able to
Design and apply iterative and recursive algorithms.
Design and implement optimisation algorithms in specific applications.
Design appropriate shared objects and concurrent objects for applications.
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. 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”,
OBJECTIVES:
To understand the principles of iterative and recursive algorithms.
To learn the graph search algorithms.
To study network flow and linear programming problems.
To learn the hill climbing and dynamic programming design techniques.
To develop recursive backtracking algorithms.
To get an awareness of NP completeness and randomized algorithms.
To learn the principles of shared and concurrent objects.
To learn concurrent data structures.
UNIT I ITERATIVE AND RECURSIVE ALGORITHMS
Iterative Algorithms: Measures of Progress and Loop Invariants-Paradigm Shift: Sequence of Actions versus Sequence of Assertions- Steps to Develop an Iterative Algorithm-Different Types of Iterative Algorithms--Typical Errors-Recursion-Forward versus Backward- Towers of Hanoi-Checklist for Recursive Algorithms-The Stack Frame-Proving Correctness with Strong Induction- Examples of Recursive Algorithms-Sorting and Selecting AlgorithmsOperations on Integers- Ackermann’s Function- Recursion on Trees-Tree TraversalsExamples- Generalizing the Problem - Heap Sort and Priority Queues-Representing
Expressions.
UNIT II OPTIMISATION ALGORITHMS
Optimization Problems-Graph Search Algorithms-Generic Search-Breadth-First Search Dijkstra’s Shortest-Weighted-Path -Depth-First Search-Recursive Depth-First Search-Linear Ordering of a Partial Order- Network Flows and Linear Programming-Hill Climbing-Primal Dual Hill Climbing- Steepest Ascent Hill Climbing-Linear Programming-Recursive Backtracking-Developing Recursive Backtracking Algorithm- Pruning Branches-Satisfiability
UNIT III DYNAMIC PROGRAMMING ALGORITHMS
Developing a Dynamic Programming Algorithm-Subtle Points- Question for the Little BirdSubinstances and Subsolutions-Set of Substances-Decreasing Time and Space-Number of Solutions-Code. Reductions and NP-Completeness-Satisfiability-Proving NP-Completeness- 3-Coloring- Bipartite Matching. Randomized Algorithms-Randomness to Hide Worst CasesOptimization Problems with a Random Structure.
UNIT IV SHARED OBJECTS AND CONCURRENT OBJECTS
Shared Objects and Synchronization -Properties of Mutual Exclusion-The Mora l- The Producer–Consumer Problem -The Readers–Writers Problem-Realities of ParallelizationParallel Programming- Principles- Mutual Exclusion-Time- Critical Sections--Thread Solutions-The Filter Lock-Fairness-Lamport’s Bakery Algorithm-Bounded Timestamps-Lower Bounds on the Number of Locations-Concurrent Objects- Concurrency and CorrectnessSequential Objects-Quiescent Consistency- Sequential Consistency-Linearizability- Formal Definitions- Progress Conditions- The Java Memory Model
UNIT V CONCURRENT DATA STRUCTURES
Practice-Linked Lists-The Role of Locking-List-Based Sets-Concurrent Reasoning- CoarseGrained Synchronization-Fine-Grained Synchronization-Optimistic Synchronization- Lazy Synchronization-Non-Blocking Synchronization-Concurrent Queues and the ABA ProblemQueues-A Bounded Partial Queue-An Unbounded Total Queue-An Unbounded Lock-Free Queue-Memory Reclamation and the ABA Problem- Dual Data Structures- Concurrent Stacks and Elimination- An Unbounded Lock-Free Stack- Elimination-The Elimination Backoff Stack
OUTCOMES:
Upon completion of the course, the students will be able to
Design and apply iterative and recursive algorithms.
Design and implement optimisation algorithms in specific applications.
Design appropriate shared objects and concurrent objects for applications.
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. 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”,