Introduction

OOP Using Java – Class and Objects, Variables, Operators, Expressions, Methods, Decision statements, Loops, Arrays, OOP – Concepts – Encapsulation, Inheritance, Polymorphism, Abstraction, Modularity, Exception handling, Input and Output, Java and Pointers, Interfaces, Packages, Abstract classes, Casting in Inheritance hierarchy, Casting with Interfaces, Vectors in java.util, Data structures and OOP, Writing a java program – Design, coding, testing and debugging, Basic concepts (Review) – Abstract data types, Data structures, Algorithms – Characteristics of Algorithms, Performance analysis – Time complexity and Space Complexity, Asymptotic Analysis – Big O, Omega and Theta notations.

introduction
THE JAVA VIRTUAL MACHINE

Linear DS

Linear data structures- The List ADT, Array and Linked Implementations,Singly Linked ListsOperations-Insertion,Deletion,Traversals,DoublyLinkedLists-Operations-Insertion,Deletion,SkipListsimplementation, StackADT,definitions,operations, Array and Linked implementations,applications-infix to postfix conversion, recursion implementation,tail

Non Linear DS

Non Linear data structures-Trees-Basic Terminology, Binary tree ADT,array and linked representations,iterative traversals,threaded binary trees,Applications-Disjoint-Sets,Union and Find algorithms,Huffman coding,General tree to binary tree conversion, Realizing a Priority Queue using Heap

Searching & Sorting

Searching- Linear Search,Binary Search, Hashing-Hash functions,Collision-Handling schemes,Hashing in java.util,Dictionary ADT,Linear list representation,Skip list representation,Hash table representation,Comparison of Searching methods

Graphs

Graphs–Basic Terminology, Graph Representations- Adjacency matrix,Adjacency lists,Adjacency multilists,Graph traversals- DFS and BFS, Spanning trees-Minimum cost spanning trees,Kruskal’s Algorithm for Minimum cost Spanning trees, Shortest paths- Single Source Shortest Path Problem,All Pairs Shortest Path Problem