Get Ready

Java is a simple and yet powerful object oriented, platform independent and high level programming language.
Java originated at Sun Microsystems, Inc. in 1991. It was developed by James Gosling, Patrick Naughton, Chris Warth, Ed Frank, and Mike Sheridan at Sun Microsystems, Inc.
The target of Java is to write a program once and then run this program on multiple operating systems.
The first publicly available version of Java (Java 1.0) was released in 1995. Sun Microsystems was acquired by the Oracle Corporation in 2010. Oracle has now the steermanship for Java. In 2006 Sun started to make Java available under the GNU General Public License (GPL). Oracle continues this project called OpenJDK. Over time new enhanced versions of Java have been released. The current version of Java is Java 1.8 which is also known as Java 8.


Content Structure
1. Analyzing Algorithms   [3 Hours]
1.1. Theoretical Foundation 
1.1.1. Algorithms and it’s Specification
1.1.2. Random Access Machine Model
1.1.3. Counting Primitive Operations
1.1.4. Notion of best case, average case and worst case
1.2. Characterizing Run Time
1.2.1. Use of asymptotic notation
1.2.2. Big-Oh Notation, Little-Oh, Omega and Theta Notations
1.3. Correctness of Algorithms
1.4. Analyzing Recursive Algorithms
1.4.1. Recurrence relations
1.4.2. Specifying runtime of recursive algorithms
1.4.3. Solving recurrence equations
1.5. Case Study: Analyzing Algorithms

2. Elementary  Data Structures [2 hours]
2.1. Stacks 
2.1.1. Stack ADT and Implementation
2.1.2. Applications
2.2. Queues
2.2.1. Queue ADT and Implementation
2.2.2. Applications
2.3. List
2.3.1. Notion of position in lists
2.3.2. List ADT and Implementation

3. Non-Linear Data Structures [4 hours]
3.1. Trees
3.1.1. Terms and Definition 
3.1.2. Tree ADT
3.1.3. Applications
3.2. Binary Trees
3.2.1. Properties
3.2.2. Representations (Vector Based and Linked)
3.2.3. Binary Tree traversal (In Order, Pre Order, Post Order)
3.2.4. Applications
3.3. Heaps
3.3.1. Definition and Properties
3.3.2. Representations (Vector Based and Linked)
3.3.3. Insertion and deletion of elements
3.3.4. Heap implementation of priority queue
3.3.5. Heap sort

4. Dictionaries [ as Hash Tables and Search Trees] [3 hours]
4.1. Unordered Dictionary
4.1.1. ADT Specification 
4.1.2. Applications
4.2. Hash Tables
4.2.1. Notion of Hashing and Collision (with a simple vector based hash table)
4.2.2. Hash Functions
4.2.2.1. Properties
4.2.2.2. Simple hash functions 
4.2.3. Methods for Collision Handling
4.2.3.1. Separate Chaining
4.2.3.2. Notion of Load Factor
4.2.3.3. Rehashing
4.2.3.4. Open Addressing [ Linear & Quadratic Probing, Double Hash] 
4.3. Ordered Dictionary
4.3.1. ADT Specification 
4.3.2. Applications
4.4. Binary Search Tree
4.4.1. Motivation with the task of Searching and Binary Search Algorithm
4.4.2. Properties of BST
4.4.3. Searching an element in BST
4.4.4. Insertion and Removal of Elements
4.4.5. Performance
5. Algorithm Design Techniques [ 6 Hours ]
5.1. Greedy Method
5.1.1. Design Principles and Strategy
5.1.2. Fractional Knapsack Problem
5.1.3. Task Scheduling Problem
5.2. Divide and Conquer
5.2.1. Design Principles and Straegy
5.2.2. Analyzing Divide and Conquer Algorithms
5.2.3. Integer Multiplication Problem
5.2.4. Sorting Problem
5.2.4.1. Merge Sort Algorithm
5.2.4.2. Quick Sort Algorithm
5.2.5. Searching  Problem and Binary Search Algorithm [Ref to 4.4.1]
5.3. Dynamic Programming
5.3.1. Design Principles and Strategy
5.3.2. Matrix Chain Product Problem
5.3.3. 0/1 Knapsack Problem
5.4. Graph Algorithms
5.4.1. Introduction to Graphs
5.4.2. Prim's and Kruskal's Algorithms [Greedy]
5.4.3. Dijkstra’s Algorithm [Greedy]
5.4.4. Bellman-ford Shortest Path Algorithm [Greedy]
5.4.5. All Pair Shortest Path Algorithm [Dynamic Programming]

6. Complexity Classes  [4 hours]
6.1. Definition of  P and NP classes and examples
6.2. Understanding NP-Completeness
6.2.1. NP-Hardness
6.2.2. Polynomial time reducibility
6.2.3. Cook-Levin theorem
6.2.4. Problems in NP-Complete and using polynomial time reductions
6.2.4.1. CNF-SAT, 3-SAT
6.2.4.2. Vertex Cover
6.2.4.3. Clique and Set-Cover
6.2.4.4. Subset-Sum and Knapsack
6.2.4.5. Hamiltonian Cycle and TSP