CP7102 ADVANCED DATA STRUCTURES AND ALGORITHMS L T P C 3 0 0 3
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 I TERATIVE AND RECURSIVE ALGORITHMS 9
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 Algorithms- Operations on Integers- Ackermann’s Function- Recursion
on Trees-Tree Traversals- Examples- Generalizing the Problem - Heap Sort and
Priority Queues-Representing Expressions.
UNIT II OPTIMISATION ALGORITHMS 9
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- atisfiability
UNIT III DYNAMIC PROGRAMMING ALGORITHMS 9
Developing a Dynamic Programming
Algorithm-Subtle Points- Question for the Little Bird- Subinstances 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
Cases- Optimization Problems with a Random Structure.
UNIT IV SHARED OBJECTS AND CONCURRENT OBJECTS 9
Shared Objects and
Synchronization -Properties of Mutual Exclusion-The Mora l- The Producer–Consumer
Problem -The Readers–Writers Problem-Realities of Parallelization- Parallel
Programming- Principles- Mutual Exclusion-Time- Critical Sections—Thread Solutions-The
Filter Lock-Fairness-Lamport’s Bakery Algorithm-Bounded Timestamps- ower Bounds
on the Number of Locations-Concurrent Objects- Concurrency and Correctness- Sequential
Objects-Quiescent Consistency- Sequential Consistency-Linearizability- Formal Definitions-
Progress Conditions- The Java Memory Model
UNIT V CONCURRENT DATA STRUCTURES 9
Practice-Linked
Lists-The Role of Locking-List-Based Sets-Concurrent Reasoning- Coarse- Grained
Synchronization-Fine-Grained Synchronization-Optimistic Synchronization- Lazy Synchronization-Non-Blocking
Synchronization-Concurrent Queues and the ABA Problem- Queues-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
TOTAL : 45
PERIODS
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”,
Pearson,2006.
கருத்துகள் இல்லை:
கருத்துரையிடுக