DOC/LP/01/28.02.02
/ LESSON PLAN / LP – CP 7102LP Rev. No : 00
Date : 17/9/2013
Page: 01 of 06
Sub Code: CP 7102
Sub Name: ADVANCED DATA STRUCTURES AND ALGORITHMS
Unit : I Branch : ME(CSN) Semester : 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 Algorithms Operations on Integers- Ackermann’s Function- Recursion on Trees-Tree Traversals- Examples- Generalizing the Problem - Heap Sort and Priority Queues-Representing Expressions.
Objectives:
ü To understand the principles of Iteration and Recursion
ü To Develop Iterative algorithms and prove its correctness based on loop invariance
ü To Develop Recursive algorithms and compute its running time using Recurrence relations
SI NO / Topic Discussed / Duration / Reference / Teaching Method1 / Iterative Algorithms / 50 minutes / 1 / Black Board
2 / Loop Invariance – Example / 50 minutes / 1 / Black Board
3 / Sequence of Action Vs Sequence of Assertions / 50 minutes / 1 / Black Board
4 / Steps to develop iterative algorithm ,
types of Iterative Algorithm / 50 minutes / 1 / Black Board
5 / Recursion - Forward and Backward Recursion – Examples / 50 minutes / 1 / Black Board
6 / Tower of Hanoi – Analysis / 50 minutes / 1 / Black Board
7 / Check list for Recursive Algorithms, Stack Frame / 50 minutes / 1 / Black Board
8 / Sorting and Selection Algorithms / 50 minutes / 1 / Black Board
9 / Operation on Integers, Ackermann Function / 50 minutes / 1 / Black Board
10 / Recursion on Trees, Tree Traversals / 50 minutes / 1,9 / Black Board
11 / Binary Heaps / 50 minutes / 7,9 / Black Board
12 / Heap Sort / 50 minutes / 7,10 / Black Board
/ LESSON PLAN / LP – CP 7102
LP Rev. No : 00
Date : 17/9/2013
Page: 02 of 06
Sub Code: CP 7102
Sub Name : ADVANCED DATA STRUCTURES AND ALGORITHMS
Unit : II Branch :ME(CSN) Semester : I
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
Objectives:
ü To learn Graph Search Algorithms
ü To solve Computational Problems using Graphs
ü To study Network Flow and Linear Programming Problems
ü To learn Hill Climbing Techniques and Backtracking algorithms
SI NO / Topic Discussed / Duration / Reference / Mode OfDelivery
13 / Optimization Problems and Graphs – Introduction / 50 minutes / 7 / Black Board
14 / Graph Search- BFS and DFS / 50 minutes / 7 / PPT
15 / Dijkstra's Shortest Weighed Path , Linear Ordering of Partial Order / 50 minutes / 1 / PPT
16 / Network Flows / 50 minutes / 1 / PPT
17 / Linear Programming / 50 minutes / 1 / PPT
18 / Hill climbing - Primal Dual and Steepest Ascent / 50 minutes / 1 / PPT
19 / Backtracking & Recursive Backtracking – Example / 50 minutes / 1 / PPT
20 / Pruning Branches / 50 minutes / 1 / PPT
21 / Satisfiability / 50 minutes / 1 / PPT
/ LESSON PLAN / LP – CP 7102
LP Rev. No : 00
Date : 17/9/2013
Page: 03 of 06
Sub Code: CP 7102
Sub Name: ADVANCED DATA STRUCTURES AND ALGORITHMS
Unit : III Branch : ME(CSN) Semester: I
DYNAMIC PROGRAMMING ALGORITHMS
Developing a Dynamic Programming Algorithm-Subtle Points - Question for the Little Bird Sub-instances and Sub-solutions - 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.
Objectives:
ü To learn Dynamic Programming design technique and apply to solve problems
ü To get an awareness of NP Completeness
ü To get an awareness of Randomized Algorithms
SI NO / Topic Discussed / Duration / Reference / Teaching Method22 / Dynamic Programming Introduction-Example / 50 minutes / 7 / Black Board
23 / Sub instances and Sub Solutions / 50 minutes / 1 / Black Board
24 / Decreasing Time and Space / 50 minutes / 1 / Black Board
25 / Class of Problems - P, NP, NP Complete / 50 minutes / 7 / Black Board
26 / Reduction, Proving NP Completeness / 50 minutes / 1 / Black Board
27 / Graph Coloring / 50 minutes / 1 / Black Board
28 / Bipartite Graphs and Bipartite Matching / 50 minutes / 1 / Black Board
29 / Randomized Algorithm, Randomness to hide Worst cases / 50 minutes / 8 / Black Board
30 / Optimization problem with worst cases / 50 minutes / 1 / Black Board
/ LESSON PLAN / LP – CP 7102
LP Rev. No : 00
Date : 17/9/2013
Page: 04 of 06
Sub Code: CP 7102
Sub Name: ADVANCED DATA STRUCTURES AND ALGORITHMS
Unit : IV Branch : ME(CSN) Semester : I
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 Parallelization Parallel 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 Correctness Sequential Objects-Quiescent Consistency- Sequential Consistency-Linearizability- Formal Definitions- Progress Conditions- The Java Memory Model
Objectives:
ü To learn the principles of shared and Concurrent objects
ü To learn classic Synchronization Problems
ü To get an awareness of Java Memory Model
SI NO / Topic Discussed / Duration / Reference / Teaching Method31 / Concurrency, Mutual Exclusion and Synchronization – Introduction / 50 minutes / 2 / Black Board
32 / Shared Objects, Critical Section and Locks / 50 minutes / 2 / PPT
33 / Producer Consumer Problem / 50 minutes / 2 / PPT
34 / Reader Writer Problem / 50 minutes / 2 / PPT
35 / The Filter Lock, Lamport Bakery Algorithm / 50 minutes / 2 / PPT
36 / Correctness, Quicient Consistency / 50 minutes / 2 / PPT
37 / Sequential Consistency, Linearizability / 50 minutes / 2 / PPT
38 / Progress Conditions / 50 minutes / 2 / PPT
39 / Java Memory Model / 50 minutes / 2 / PPT
/ LESSON PLAN / LP – CP 7102
LP Rev. No : 00
Date : 17/9/2013
Page: 05 of 06
Sub Code: CP 7102
Sub Name: ADVANCED DATA STRUCTURES AND ALGORITHMS
Unit : V Branch : ME(CSN) Semester : I
CONCURRENT DATA STRUCTURES
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
Objectives:
ü To learn Concurrent Data Structures
ü To learn the synchronization concepts involved in operations of concurrent data structures
SI NO / Topic Discussed / Duration / Reference / Teaching Method40 / Concurrent Data Structures - Concurrent Linked Lists / 50 minutes / 2 / PPT
41 / Coarse Grained Synchronization and Fine Grained Synchronization / 50 minutes / 2 / PPT
42 / Optimistic Synchronization, Lazxy Synchronization / 50 minutes / 2 / PPT
43 / Non Blocking Synchronization / 50 minutes / 2 / PPT
44 / Concurrent Queues - Bounded Partial Queue / 50 minutes / 2 / PPT
45 / Unbounded Total Queue / 50 minutes / 2 / PPT
46 / Unbounded Lock Free Queue / 50 minutes / 2 / PPT
47 / Memory Reclamation and ABA Problem / 50 minutes / 2 / PPT
48 / Dual Data Structures / 50 minutes / 2 / PPT
49 / Concurrent Stacks - Unbounded Lock Free Stack / 50 minutes / 2 / PPT
50 / Stack - BackOff Elimination / 50 minutes / 2 / PPT
/ LESSON PLAN / LP – CP 7102
LP Rev. No : 00
Date : 17/9/2013
Page: 06 of 06
Sub Code: CP 7102
Sub Name: ADVANCED DATA STRUCTURES AND ALGORITHMS
Programme: M.E Branch : ME(CSN) Semester : I
Course Delivery Plan
Week / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 10 / 11 / 12 / 13Unit / I / I / I / I / I / II / II / II / II / II / III / III / III / III / III / IV / IV / IV / IV / IV / V / V / V / V / V / V
Outcomes:
Upon completion of the course, the students will be able to:
Design and apply iterative and recursive algorithms and implement optimisation algorithms in specific applications. Design appropriate shared objects and concurrent objects for applications and 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.
Prepared by / Approved bySignature
Name / R.Dhanalakshmi / Dr.D.Balasubramanian
Designation / Asst.Professor / IT / HOD / IT
5