- Title: Data Structures And Algorithms
- Department: Computer Science and Engineering
- Author: Prof. Naveen Garg
- University: IIT Dehi
- Type: WebLink
- Abstract:
Data Structures
Course objective: The objective of the course is to familiarize students with basic data structures and their use in fundamental algorithms.
Course contents:
Introduction to object oriented programming through stacks,
queues and linked lists.
Dictionaries: skip-lists, hashing, analysis of collision resolution techniques.
Trees, traversals, binary search trees, optimal and average BST/s. 2-4 trees and red-black trees. Tries and pattern matching.
Priority queues and binary heaps. Sorting: merge, quick, radix, selection, heap.
Graphs, Breadth first search and connected components. Depth first search in
directed and undirected graphs and strongly connected components.
Spanning trees: Prim/s and Kruskal/s algorithm, union-find data structure. Dijkstra/s
algorithm for shortest paths, shortest path tree.
Directed acyclic graphs: topological sort and longest path.
Lecture outline with topics
no. of lectures
Introduction to object oriented programming through stacks, queues and linked lists
4
Dictionaries: skip-lists, hashing, analysis of collision resolution techniques
Trees, traversals, binary search trees, optimal and average BST/s
trees and red-black trees
5
6
4
Tries and pattern matching. Priority queues and binary heaps 5
Sorting: merge, quick, radix, selection, heap
3
Introduction to Graphs, Breadth first search and connected components 3
Depth first search in directed and undirected graphs and strongly connected components
3
Spanning trees: Prim/s and Kruskal/s algorithm, union-find datastructure. 4
Dijkstra/s algorithm for shortest path. shortest path tree. Shortest and longest paths in directed acyclic graphs 5