Course Contents
Unit 1: Introduction 3 hours
What is the subject about? Mathematics review, Brief introduction to Recursion
Unit 2: Algorithm Analysis 3 hours
Mathematical background, Model, What to analyze? Running time calculations
Unit 3: Lists, Stacks, and Queues 5 hours
Abstract data types (ADTs), The list ADT, The stack ADT, The queue ADT
Unit 4: Trees 6 hours
Reliminaries, Binary trees, The search tree ADT – Binary search trees, AVL trees, Splay trees, Tree traversals (revisited), B-trees
Unit 5: Hashing 6 hours
General idea, Hash function, Open hashing (separate chaining), Closed hashing (open addressing), Rehashing, Extendable hashing
Unit 6: Priority Queues 6 hours
Model, Simple implementation, Binary heap, Applications of priority queues, D-heaps, Leftist heaps, Skew heaps, Binomial queues
Unit 7: Sorting 7 hours
Preliminaries, Insertation sort, A lower bound for simple sorting algorithms, Shell-sort, Heap-sort, Merge- sort, Quick-sort, Sorting large objects, A general lower bound for sorting, Bucket sort, External sorting
Unit 8: Graph Algorithm 6 hours
Definitions, Topological sort, Shortest-path algorithm, Network flow problems, Minimum spanning tree Applications of depth-first search, Introduction to NP-completensess
Unit 9 : Algorithm Design Techniques 6 hours
Greedy algorithm, Divide and conquer, Dynamic programming, Randomized algorithms, Backtracking algorithms
Laboratory
There shall be 10 lab exercises based on C or JAVA
- Implementation of stack
- Implementation of linear and circular queue
- Solution of TOH and Finbonacci recursion
- Implementation of Link list: Singly, and doubly linked
- Implementation of Tree: AVL tree, Balancing of AVL
- Implementation of merge sort
- Implementation of search: sequential, Tree and Binary
- Implementation of Graphs: Graph traversals
- Implementation of hashing
- Implementation of heap