Elementary Data Types and Abstract Data Types. Computational model and complexity of algorithms (running time and space metrics), Introduction to Asymptotic notation: Big-O, Big-Omega, Big-Theta notations. Worst-case, Best- case, Average-case and amortized analysis. Arrays, Linear search and Binary search on sorted arrays. List ADT, implementing List ADT using arrays. Pointers, implementing List ADT using Linked Lists. Types of Linked Lists: Single, Double, Circular linked lists and their applications for e.g. in garbage collection. Stack ADT and Queue ADT implementation, applications for parenthesis matching, expression evaluation, implementing recursion, etc. Dynamic set ADT and Dictionary ADT. Hash tables: collisions, open and closed hashing, choosing good hash functions. Trees: Definitions and Representations; Tree traversals and their applications. Binary Search Trees. AVL trees, Red-black trees, Multi-way search trees, B- trees, splay trees; Priority Queue ADT and its implementations using Binary heaps. Applications of Priority Queues. Sorting algorithms: Bubble sort, Selection sort, Insertion sort, Merge sort and Quick sort. Randomized Quick sort and its analysis. Linear-time sorting algorithms like Radix and Counting sort. Lower bound for comparison based sorting.