[go: up one dir, main page]
Scribd
Upload
40 views3 pages

CS-504 Advanced Data Structures and Algorithms (3 0 0)

The document outlines a course on advanced data structures and algorithms. It discusses course outcomes related to analyzing and designing data structures and algorithms to solve problems. It also covers topics like binary search trees, graphs, string matching algorithms, and analyzing algorithm complexity.

Uploaded by

Om Prakash Suman
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
40 views3 pages

CS-504 Advanced Data Structures and Algorithms (3 0 0)

The document outlines a course on advanced data structures and algorithms. It discusses course outcomes related to analyzing and designing data structures and algorithms to solve problems. It also covers topics like binary search trees, graphs, string matching algorithms, and analyzing algorithm complexity.

Uploaded by

Om Prakash Suman
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

CS-504 Advanced Data Structures and Algorithms [3 0 0]

Course Outcomes: At the completion of the course, students will be able to


CO1: Enhance their expertise in algorithmic analysis and algorithm design techniques.
CO2: Analyze, design, apply and use data structures and algorithms to solve engineering problems
and evaluate their solutions
CO3: Understand and apply amortized analysis on data structures, including binary search trees,
merge able heaps and graphs.
CO4: Have an idea of applications of algorithms in a variety of areas including string matching, and
databases etc

Course Contents
Elementary Data Structures and Complexity Analysis: Overview of Basic Data
Structures: Arrays, Linked List, Stack, Queues. Implementation of Sparse Matrices,
Algorithm Complexity: Average, Best and worst case analysis, asymptotic notations, Simple
Recurrence Relations and use in algorithm analysis
Search Structures: Binary search trees, AVL trees, 2-3 trees, 2-3-4 trees, Red-black trees,
Btrees.
Graph Algorithms: Representation of Graphs, Traversals, Single-source shortest path
Algorithms, All-pairs shortest path algorithms, Sub graphs, Disjoint Graphs, Connected
Components, Articulation Points, Spanning tree, Minimum Spanning Trees Algorithms,
Topological sort
String Matching Algorithms: Introduction, The Brute-Force- Algorithm, Rabin-Karp
Algorithm, String Matching with Finite automata, Knuth-Marries-Pratt Algorithm
Heap Structures: Min-max heaps, Deaps, Leftist heaps, Binomial heaps, Fibonacci heaps,
Skew heaps
Multimedia Structures: Segment trees, k-d trees, Point Quad trees, MX-Quad trees, R-trees.

Text / References:
1. E. Horowitz, S.Sahni and Dinesh Mehta, Fundamentals of Data structures in C++, Galgotia, 1999.
2. Adam Drozdex, Data Structures and algorithms in C++, Second Edition, Thomson learning
vikas publishing house, 2001.
3. G. Brassard and P. Bratley, Algorithmics: Theory and Practice, Printice –Hall, 1988.
4. Thomas H.Corman, Charles E.Leiserson, Ronald L. Rivest, ”Introduction to Algorithms”, PHI.
CS- 514 Advanced Data Structure and Algorithm Laboratory
[0 0 3]
Course Outcomes: After the completion of the course, the students will be able to
CO1: Implement various advance problems using data structures such as stacks, queues, trees, graphs, etc. to
solve various computing problems.
CO2: Understand how several fundamental algorithms work particularly those concerned with Stack, Queues,
Trees and various Sorting algorithms.
CO3: Design new algorithms or modify existing ones for new applications and able to analyse the space & time
efficiency of most algorithms.
CO4: Decide a suitable data structure and algorithm to solve a real-world problem.
Students are required to perform the following list of practicals:

1. Implementation of various algorithms & operations based on Arrays such as Insertion,


Deletion, Sorting (Insertion, Bubble, Selection, Shell, Radix, Merge, Quick), Searching
(Linear, Binary) and Sparse matrices such as addition, multiplication & transpose.
2. Implementation of Stacks & Queues including priority queues along with various
operations on them such as Infix to Postfix conversion, postfix expression evaluation, get
minimum element in O(1) time using O(1) additional space using stacks & calculate no. of
page faults, reversal of the entire or a part of a queue.
3. Implementation of Linked list and doubly linked list along with solving various problems
based on them such as removal of duplicate elements from sorted/Unsorted Linked List,
Swapping of nodes by changing link, Segregating odd & even nodes together, binary Search,
number of elements in a loop, print nth element from the last, finding the middle element.
4. Implementation of binary trees and various operations based on them such as preorder/
inorder/ postorder traversal using stack, level order traversal, level order traversal in spiral
form, left/ right/ top/ bottom view of the tree, vertical order traversal, printing sum of inorder
predecessor & successor for each node.
5. Implementation of binary search tree and various problem solving based on them such as
finding minimum/ maximum element, traversal in ascending/ descending order, kth largest &
kth minimum element, converting binary tree to binary search tree, finding a pair with a
given sum.
6. Implementation of AVL trees and various operations based on them such as insertion,
deletion and traversal.
7. Implementation of Red/Black trees and various operations based on them such as insertion,
deletion and traversal.
8. Implementation of B trees and various operations based on them such as insertion, deletion
and traversal.
9. Implementation of heaps & deaps along with various operations based on them such as
insertion, deletion, extracting minimum/ maximum element, heap sort, priority queues.
10. Implementation of fibonacci & binomial heaps with various operations based on them
such as insertion, union, deletion, extracting minimum/ maximum element.
11. Implementation of various graph based algorithms Dijkstra’s shortest path, Warshall’s all
pair shortest path, breadth & depth first search.
12. Implementation of greedy algorithms like kruskal & prims to find the minimum spanning
tree from a given set of nodes and edges.
13. Implementation of various string matching algorithms like brute force, Rabin-karp,
Knuth_marries-Pratt and using finite automata.
This is only the suggested list of Practicals. Instructor may frame additional Practicals relevant to the course
contents.

You might also like