ADVANCED DATA STRUCTURES LABORATORY

-

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: 


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. 

OUTCOMES:
 

Upon completion of the course, the students will be able to
  • Design and apply iterative and recursive algorithms. 
  • Design and implement algorithms using the hill climbing and dynamic programming and recursive backtracking techniques. 
  • Design and implement optimization algorithms for specific applications. 
  • Design and implement randomized algorithms. 
  • 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.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.


CP7111  Advanced Data Structures Laboratory material is available from the following link
.

Comments

  1. UnknownNov 6, 2017, 5:21:00 PM

    Hi.. Need code for the following scenario.. Create a class with the following members:
    Booknumber,title,author,publisher,price
    Use constructor for initializing the data members for any given number of books.
    Implement an avl tree to store book type data and perform the following operations:
    Insert the book based on booknumber.
    For a given book number retrieve the details of the book.
    List the book number using in order traversal.

    ReplyDelete

Post a Comment

Popular posts from this blog

Pentium microprocessors

-
Image
A 32-bit microprocessor introduced by Intel in 1993. It contains 3.3 million transistors. Since 1993, Intel has developed the Pentium III and more recently the Pentium 4 microprocessors.   Pentium III Pentium III Mainboard Layout Intel builds on the technology it developed with the Pentium II microprocessors.  The Pentium III processor comes with a Synchronized Dynamic Random Access Memory (SDRAM), allowing for an extremely fast transfer of data between the microprocessor and the memory. 70 new instructions, called Streaming SIMD Extensions, enhance multimedia and 3D performance.  Launched February 1999 - Available in speed levels of 450, 500, 550, and 600MHz. 32KB of Level 1 Cache (operating at CPU's full core speed). 512KB of Level 2 Cache (operating at ½ of CPU's core speed). 100 MHz bus speed. The branch prediction/recovery pipeline was doubled to include 10-stages from the P-II.   Pentium IV The next generation of microprocessors from Intel. Pe
Read more

Design and Management of Computer Networks Running Notes

-
Architecture and Design Process Hierarchy and Inter-connectivity Network Supportability ------------------------------------------------------------------------------------------- Service Description pdf Service characteristics pdf Service Levels pdf System Components and network services pdf Service Requests and Requirements pdf Service Offerings pdf Service Matrices pdf Performance Characteristics pdf for running notes Download here ------------------------------------------------------------------------------------------- Types of user requirements pdf Timeliness Interactivity Reliability Presentation Quality Adaptability Security Affordability Functionality Supportability Future growth Requirement Analysis pdf The need for Requirement Analysis User Requirements pdf for running notes Download here -------------------------------------------------------------------------------------------  Applic
Read more

ONE DIMENSIONAL RANDOM VARIABLES: Handwritten notes

-
Properties of probability Distribution Function Expectation Value For the following problem by using Find the distribution function of x? What is the smallest value of x? for which probability P(X<=x)>0.5 for more click here ---------------------------------------------------------------------------------------------------------------- Continues Random Variable           We call the distribution function as probability density function f(x). Properties of probability density function.  click here ---------------------------------------------------------------------------------------------------------------- Moment Generating Function (MGF) Properties Additional property in MGF  for notes click here ---------------------------------------------------------------------------------------------------------------- Bernoulli Trial       For a single trail with only two possible results.  Example: Tossing a coin. p=1/2, q=1/2 p + q = 1 p = q
Read more