JTSTUDY: November 2008

TECH MAX Data Structure & Algorithm in java Syllabus

Table of Contents Data Structure & Algorithms(M)

Chapter 1: Revisiting Java Programming Construct 1-1 to 1-136

1.1 Classes and Objects 1-1

1.1.1 The General Form of a Class 1-1

1.1.2 Declaration of Instance Variables , 1-2

1.1.3 Declaring Objects ~ 1-3

1.1.4 Accessing Instance Variables 1-4

1.1.5 Assigning Object Reference Variables 1-6

1.2 Class Methods 1-7

1.2.1 Returning a Value 1-9

1.2.2 Method that Takes Parameters : 1-11

1.3 Expressions 1-12

......................................................................................•..........................................

1.4 Control Flow ........................................•...•.....................................................................................

1-15

1.4.1 Selection Control Statements 1-15

1.4.1.1 The if statement 1-15

1.4.1.2 The if-else statement 1-17

1.4.1.3 The Switch Statement ; : 1-18

1.4.2 Iteration Statements 1-20

1.4.2.1 The While Statement 1-20

1.4.2.2 The do-while Loop 1-21

1.4.2.3 The for Loop 1-22

1.4.3 Jump Statements 1-24

1.4.3.1 The break Statement 1-25

1.4.3.2 The Continue Statement 1-28

1.4.3.3 The Return Statement 1-29

1.5 Arrays 1-30

1.5.1 One-Dimensional Arrays 1-30

1.5.1.1 Declaring Arrays 1-30

1.5.1.2 Creating Arrays 1-31

1.5.1.3 Initializing Arrays 1-32

1.5.1.4 A Simple Program on One-Dimensional Array 1-33

1.5.1.5 Array Length ; 1-34

1.5.2 Multidimensional Arrays 1-35

1.5.2.1 A Simple Program on Multidimensional Array : 1-36

1.5.2.2 Uneven (or Irregular) Multidimensional Arrays 1-37

1.5.2.3 Programs on Array 1-37

1.6 Input and Output 1-47

1.6.1 Streams 1-47

1.6.2 Predefined Streams 1-49

1.6.3 Reading Input from Console 1-50
Packages ; 1-52

•.7.1 Creating a Package 1-52 __•.
2' Q..ASSPATH Environmental Variable 1-53

Table of Contents
2
Data Structure & Algorithms (M)
1.7.3 Access Protection 1-55
1.7.4 Programs on Packages 1-56
1.7.5 Importing Packages 1-60
1.7.6 Hiding Classes 1-65
1.7.7 Java Application Programming Interface Packages 1-66
1.7.8 The java.lang Package : 1-66
1.8 True/False Questions 1-68
1.9 MuH'iple Choice Questions 1-69
.10 Debugging Exercises 1-73
.11 Programs 1-90
Chapter 2 : Object Oriented Design and Analysis of Algorithms
2-1 to 2-144
2.1 Inheritance 2-1
2.1.1 Defi nition 2-2
2.1.2 Forms of Inheritance ; 2-2
2.1.3 Single inheritance 2-3
2.1.4 Inheritance and Member Accessibility 2-5
2.1.5 A More Practical Example 2-8
2.1.6 Super Class Variable can Reference a Subclass Object 2-11
2.1.7 Using Super 2-13
2.1.7.1 Using Super to Call Superclass Constructors 2-13
2.1.7.2 A second use for Super 2-16
2.1.8 Multilevel Inheritance 2-18
2.1.9 When Constructors are Called 2-22
2.1.10 Method Overriding 2-23
2.1.11 Dynamic Method Dispatch : 2-29
2.1.12 A More Practical Example 2-30
2.2 The Keyword 'final' ..........................•........................................ _ 2-35
2.2.1 final Variables and Methods 2-35
2 .. 2.2 final Class 2 -35
, 3 Abstract Class 2-35
* 4 A Practical Examples 2-36
5 Interfaces : 2 -43
2.5.1 Introduction 2 -43
2.5.2 Defining Interfaces 2-44
2.5.3 Implementing Interfaces 2-45
2.5.4 Accessing Implementations through Interface References 2-47
2.5.5 Partial Implementations 2-48
2.5.6 Extending Interfaces 2-48
2.5.7 Accessing Interface Variables 2-50
2.5.8 A More Practical Example 2-51
Casting '" 2 -5 3
2.6.1 Casting in Expressions 2.:.53

Table of Contents

3

Data Structure & Algorithms (M)

2.7 Exception Handling 2-56
2.7.1 Exception Handling Mechanism 2-56
2.7.2 Exception Types 2-58
2.7.3 Derault Exception Handler 2-59
2.7.4 try and Catch ...................................................................•..•.....•................................. 2-60
2.7.5 Catching Multiple Exceptions , , ..........••..............•.............. 2-62
2.7.6 Nested try Statements 2-65
2.7.7 Throwing Exceptions (throw) 2-67
2.7.8 The throws Keyword 2-69
2.7.9 The rinally Keyword .............................................................................................•...... 2-70
2. 7.10 Java's Exceptions 2-74
2.7.11 Creating Our Own.Exception 2-75
2.8 Recursion and Other Design Patterns : 2-77
2.8.1 Recursive Derinition and Processes 2-77
2.8.2 Desi gn Patterns , 2 -86
2.9 A Igori thm , , , 2 -87
2.1 0 Pseudo Code 2 -89
2.11 Analysis or Algorithm : 2-90
2.11.1 What is Analysis or Algorithm ? 2-90
2.11.1.1 Time Complexity .............................................•........................................................... 2-91
2.11.1.2 Space Complexity 2-91
2.11.2 Types or Analysis ...............•............................................................................•............ 2-91
2.11.3 Order or Magnitude or an Algorithm 2-91
2.11.4 Worst Case, Average Case and Best Case Running Time or an Algorithm 2-93
2.11.5 Mathematical Notation ror Determination or the Running Time of
an Algorithm , 2 -9 3
2.11.5.1 Big-Oh Notation- '0' Notation 2-94
2.11.5.2 Omega Notation- '0' Notation 2-95
2.11.5.3 Theta Notation- 'e' Notation ............................................................•...................... 2-95
2.11.5.4 Properties or the Asymptotic Notations 2-97
2.11.6 Assumption while Finding the Time Complexity 2-98
2.11.7 Case Study or Worst, Best and Average Case Analysis or Algorithms .......•...... 2-98
2.12 Simple Justirication Techniques 2-99
2.12.1 By example , , 2-99
2.12.2 The "Contra" Attack ....................................................................•........................... 2-100
2.12.3 Induction and Loop Invariants 2-101
2 .13 True/False Questi ons 2-102
2.14 Multiple Choice Questions 2-104
2.15 Debugging Exercises 2-109
2.16 Programs 2-120
2.17 Solved Examples , 2-127
2.18 P~evious University Questions and Answers 2-141

Table of Contents 4 Data Structure & Algorithms (M)

Chapter 3 : Stacks, Queues and Recursion 3-1 to 3-160
3J Data Structure 3-1

3.1.1 Types of Data Structure 3-1

3.2 Recursion 3-4

3.2.1 Definition 3-4

3.2.2 Property of Recursive Definitions or Algorithms 3-6

3.2.3 Recursion in Java 3-6

3.2.4 Efficiency of Recursion 3-11

3.2.5 Comparisonbetween Itet'ation and Recursion 3-12

3.3 Stack 3-12

3.3.1 Definition 3-12

3.3.2 Operati ons 3-13

3.3.2.1 Push" and "Pop" : 3-13

3.3.2.2 "Empty" and "Stacktop" 3-14

3.3.3 Array Implementation of the Stack 3-15

3.3.4 Implementation of Stack using Java Built in Class 'Stack' , 3-18

3.3.5 Applications of Stack : 3-20

3.3.5.1 Evaluating a Postfix Expression 3-21

3.3.5.2 Converting an Expression from Infix to Postfix 3-29
Queue 3-39

3.4.1 Definition 3-40

3.4.2 Operations 3-40

3.4.3 Representing Queue in' Java' 3-41

3.4.4 Circular Queue 3-45

3.4.4.1 'Java' Implementation of "Circular Queue" 3-47

3.4.5 Deque 3-51

3.4.5.1 Operations on Deque 3-51

3.4.6 Application of Queue : 3-53
~.5 What is Linked List ? 3-54

3.5.1 Definition 3-54

3.5.2 Operations on Linked Lists 3-55

3.5.3 Linked List as a Data Structure 3-59

3.5.3.1 Attaching Node at the Specified Position 3-60

3.5.3.2 Deleting the Node from Specified Position 3-60

3.5.4 Header Node 3-61

3.5.5 Implementation of Linked Lists 3-62

3.5.5.1 Static Implementation ,.3-62

3.5.5.2 DynamicImplementation 3-72

3.5.6 Linked Implementation of Stack 3-80

3.5.7 Linked Implementation of Queues 3-86

3.5.8 Circular Linked List 3-90

3.5.8.1 Operations on Circular Linked List 3-90

Table of Contents

5 Data Structure & Algorithms (M) li

3.5.8.2 'Stack using Circular Linked List 3-99

3.5.8.3 Queue using Circular Linked List 3-99

3.5.8.4 Application of Circular Linked List 3-99

3.5.8.5 Header Node 3-105

3.5.9 DoublyLinkedList 3-106

3.5.9.1 Operations on DoublyLinked List 3-107

3.6 Previous University Questions and Answers 3-141

4-1 to 4-26

Chapter 4 : Vectors, Lists and Sequences

4.1 Vectors and Array Lists 4-1

4.1.1 Vector ADT 4-1

4.1.2 Simple Array-Based Implementation 4-2

4.1.3 Extendable Array Implementation 4-3

4.1.4 The java.util.ArrayList and java.util.Vector Classes 4-5

4.2 List 4-12

4.2.1 The List Abstract Data Type 4-13

4.2.2 DoublyLinked List Impiementation 4-16

4.3 Sequences 4-19

4.3.1 Implementation of Sequence with a DoublyLinked List 4-20

4.3.2 Implementation of Sequence with an Array 4-22

4.4 Favorite Lists and the Move-to-Front Heuristic 4-22

4.4.1 Introduction 4-22

4.4.2 Using a List with the Move-to-Front Heuristic 4-23

4.4.3 Implementation of a Favorite List using the Move-to-front Heuristic 4-24

5'"1 to 5-60

Chapter 5 : Trees

5.1 Basic Tree Concepts 5-1

5.1.1 Tree 5-1

5.1.2 Different Terms Related to Tree 5-2

5.1.2.1 Leaf 5-2

5.1.2.2 Father and Son 5-2

5.1.2.3 Ancestor and Descendant 5-2

5.1.2.4 Brother 5-2

5.1.2.5 Level ,........•.....................................................................................................................

5-2

5.1.2.6 Depth 5-2

5.1.3 Binary Tree 5-2

5.1.4 Types of Binary Trees 5-3

5.1.4.1 Strictly .......................................•.............................................................

Binary Tree 5-3

5.1.4.2 Complete Binary Tree 5-3

5.1.4.3 Almost Complete Binary Tree 5-4

5.2 Operations on Binary Trees 5-4

5.3 Binary Tree Traversal 5-6

5.3.1 Preorder Traversal 5-6

~able of Contents 6

Data Structure & Algorithms (M)

5.3.2 Inorder Traversal 5-9

5.3.3 Postorder Traversal 5-11

-4

Applications of Binary Trees 5-13

5.4.1 Binary Search Tree 5-13

5.4.2 Expression Tree 5-15
:.5

Binary Tree Representations ; 5-19

5.5.1 Implicit 'Array Representation of Binary Trees ....................•................................5-19

5.5.2 DynamicNode Representation 5-24

5.5.3 Choosinga BinaryTree Representation 5-28
Binary Tree Traversals in 'C' 5-28

5.6.1 Recursive Binary Tree Traversal 5-28

5.6.2 Non Recursive Binary Tree Traversal Algorithms 5-32

5.6.2.1 Non-recursive Method for Inorder Traversal of Binary Tree 5-32

5.6.2.2 Non-recursive Method for Preorder Traversed of Binary Tree 5-40

-7

Threaded Binary Trees 5-47
Previous University Questions and Answers 5-53

apter 6 : Priority Queue 6-1 to 6-27

Priority Queue 6-1

6.1.1 Definition 6-1

6.1.2 Types of Priority Queues 6-1

6.1.2.1 Ascending Priority Queue 6-1

6.1.2.2 Descending Priority Queue 6-2

6.1.3 Implementation of Priority Queue 6-2

6.1.4 1 Java' Implementation of Priority Queue (Third Solution) 6-3
2 Priority Queue using Linked List 6-8

6.2.1 Implementation with An Unsorted Linked List 6-8

6.2.2 Implementation with sorted linked List 6-16

6.2.3 Comparison , : 6-24
3 Adaptable Priority Queue , 6-25

6.3.1 Operations ; 6-25

6.3.2 Location Aware Entries 6-26

6.3.3 Sorted List Implementation 6-26

6.3.4 Heap Implementation 6-26
Heap as A Priority Queue 6-27

apter 7 : Map and Dictionaries 7-1 to 7-47

The Map Abstract Data Type h •••••••7-1

7.1:1 Maps in the java.util Packege 7-3

7.1.2 A Simple List -Based Map Implementant 7-3
2 Hash Tables 7-5

7.2.1 Bucket array 7-5

7.2.2 Hashing 7-6

Table of Contents 7

Data Structure & Algorithms (M)

7.2.2.1 Hash Function , , 7-6

7.2.2.2 Hashing Methods , " 7-8

7.2.2.3 Hash Clashor Hash Collision 7-11

7.2.2.4 Addressi ng 7-11

7.2.2.4.1 Linear Probing , , 7-11

7.2.2.4.2 Quadratic Probe 7-18

7.2.2.4.3 Pseudorandom CollisionResolution 7-19

7.2.2.4.4 KeyOffset , 7-22

7.2.2.5 Chaining :: 7-22

7.2.2.6 Bucket Hashing 7-24

7.2.2.7 Hashing in External Storage 7-24

7.2.2.8 DynamicHashing : 7-26

7.3 The Dictionary Abstract Data Type 7-28

7.3.1 List-Based Dictionaries and Audit Trails 7-29

7.3.2 Hash Table Dictionary Implementation 7-31

7.3.3 Ordered Search Tables and Binary Search 7-32

7.4 Skip Lists , 7-40

7.4.1 Searching in a Skip List 7-42

7.4.2 Insertion in a Skip List 7-43

7.4.3 Removalina Skip List 7-45

7.5 Extensions and Applications of Dictionaries 7-45

7.5.1 Location -Aware Dictionary Entries 7-45

7.5.2 The Ordered Dictionary ADT 7-46

7.5.3 Application of Ordered Dictionaries 7-4-.

8-1 to 8-138

Chapter 8 : Search Trees

8.1 Binary Searc h Tree 8-.

8.1.1 Definition 8-:

8.1.2 Advantages of Binary Search Tree 8-Z

8.1.3 Searching an Element in Binary Search Tree 8-,

8.1.4 Inserting an element into a Binary Search Tree -

8.1.5 Deleting an element from a Binary Search Tree

w_

8.1.6 Program for Binary Search Tree S

8.1.7 Efficiency of Binary Search Tree Operation 8-Z

8.2 AVLTrees 8-2

8.2.1 Definition 8

8.2.2 Height Balanced Tree -.

8.2.3 Balance Factor :;;

8.2.4 Structure of a Node in AVLTree 5

8.2.5 Insertion of a Node into an AVLTree ; 5

8.2.6 Rotate Left , 5

8.2.7 Rotate Right , , .

8.2.8 Single Rotation and Double Rotation , :

Table of Contents 8 Data Structure & Algorithms (M)

8.2.9 'Java' Function for Insertion of an Element

8.2.10 'Java' Function to Find Height of AVL Tree

8.2.11 'Java' Function to Rotate Right

8.2.12 'Java' Function to Rotate Left

8.2.13 'Java' Function for RR

8.2.14 'Java' Function for LL

8.2.15 'Java' Function for LR

8.2.16 ' Java' Function for RL

8.2.17 Program for AVL Tree

8.2.18 Examples

8.3

Splay Tree

8.3.1 Def inition

8.3.2 The Splay Operation

8.3.3 Operations

8.3.4 Examples

8.4 Red Black Trees

8.4.1 Defi nition

8.4.2 Lemma :

8.4.3 Operations

8.4.3.1 Inserti on

8.4.3.2 Removal

< •••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••

8.4.4 Complexity

8.4.5 Example

3. 5

Multi way Searc h Trees

8.5.1 Def initi 0n

8.5.2 Searching a Multiway Tree

8.5.3 Traversing a Multiway Tree

8.5.4 Inserting in a Multiway Tree

8.5.5 B -Trees

8.5.6 Deletion in Multiway Search Trees

8.5.7 Efficiency of Multiway Search Trees

8.5.8 Examples
2-4 tree

8.6.1 Defi nition

8.6.2 Height of a (2,4) Tree

8.6.3 Operations

8.6.3.1 Insertion

8.6.3.2 Deletion

into an AVL Tree 8:..31
8-32
8-32
8-32
8-33
8-33
8-33
8-33
8-33
8-39
8-55
8-5 5
8-55
8-57
8-60
8-73
8-73
8-73
8-74
8-74
8-76
8-80
8-80
8-9 4
8-94
8-97
8-98
8-99
8-107
8-114
: 8-116
8-116
8-124
8-124
8-125
8-126
8-126
8-131

9-1 to 9-116

pter 9 : Sorting, Sets and Selection

Sorting -General Concepts 9-1
Exchange Sort (Bubble, Quick) 9-3

9.2.1 Bubble Sort 9-3

Table of Contents 9

Data Structure & Algorithms (M)

9.2.2 Quick Sort/ Partition Exchange Sort 9-16

9.3 Insertion Sort 9-36

9.3.1 Simple Insertion 9-36

9.3.2 Shell Sort 9-41

9.4 Selection and Tree Sorting 9-49

9.4.1 Straight Selection Sort 9-49

9.4.2 Binary Tree Sort 9-55

9.5 Heap Sort 9-65

9.6 Merge Sort 9-76

9.7 Radix Sort 9-85

9.8 Bucket Sort 9-9 3

9.9 Comparison of Sorting Algorithms 9-97

9.10 The Set ADT and Union/Find Structure 9-98

9.10.1 Set Implementation 9-98

9.10.2 Partition with Union-FindOperations 9-104

9.11 Solved Examples '.9-106

9.12 Previous University Questions and Answers 9-112

10-1 to 10-52

Chapter 10: Text Processing

10.1 Stri ng Operations 10-1

10.1.1 The String Constructors 10-1

10.1.2 String Arrays 10-4

10.1.3 String Concatenation 10-4

10.1.3.1 Concatenation of Strings 10-4

10.1.3.2 String Concatenation with other Data Types ~ 10-5

10.1.3.3 One Practical use of String Concatenation 10-6

10.1.4 Stri ng Methods 10-6

10.1.4.1 String Length 10-9

10.1.4.2 Changingthe Case of Characters within String : 10-9

10.1.4.3 Modifying String 10-10

10.1.4.3.1 substri ng() 10-10

10.1.4.3.2 concat() 10-11

10.1.4.3.3 replace() 10-12

10.1.4.3.4 trim{) 10-13

10.1.4.4 Character Extraction 10-14

10.1.4.4.1 char At() 10-14

10.1.4.4.2 getChars() 10-14

10.1.4.4.3 getBytes() 10-16

10.1.4.4.4 toCharArrayO 10-16

10.1.4.5 String Comparison ; 10-17

10.1.4.5.1 equals( ) and equalsIgnoreCase() 10-17

10.1.4.5.2 reg ion.\\atches() 10-18

10.1.4.5.3 startsWith() and endsWith() 10-19

T::"'e of Contents
10

Data Structure & Algorithms (M)

10.1.4.5.4 equals( ) Versus ==
10-20

10.1.4.5.5 CompareTo() and compareTolgnoreCase()
10-21

10.1.4.6 Searching Strings
10-24

10.1.4.7 String Conversion
10-26

10.1.4.8 Data conversion
: 10-28

10.1.5 Stri ngBuffer
10-29

10.1.5.1 StringBuffer Constructors
10-29

10.1.5.2 StringBuffer Methods 10-29
Pattern Matching Algorithm : 10-36

10.2.1 Brute force Pattern Matching
10-37

10.2.2 The Knuth Morris Pratt Algorithm 10-38
Tries 10-43

Huffman Algorithm
10-44

10.4.1 Huffman Encoding
10-44

10.4.2 Construction of Huffman Tree 10-45
Text Similarity Testing 10-48

10.5.1 Longest Common Subsequence Problem
10-48

10.5.2 Dynamic Programming
10-48

10.5.3
Applying Dynamic Programming to the LCS Problem 10-49
11-1 to 11-135

.er 11 : Graphs

Introduction 11-1
Concepts and Terminology 11-2

11.2.1 Graph :
11-2

11.2.2 Undirected Graph
11-2

11.2.3 Directed Graph
11-3

11.2.4 Connected Graph
".......•....................................... 11-4

11.2.5 Degree of a Node
11-5

11.2.6 Paths in a Graph
11-6

11.2.7 Weighted Graph
11-6

11.2.8 Multi graph
11-7

11.2.9 Subgraph
11-7

11.2.10 Directed Acyclic Graphs
11-8

11.2.11 Spanning .Trees
11-9

11.2.11.1 Minimal Spanning Tree
11-9

11.2.11.2 Applications of Spanning Tree 11-10
Representation of Graphs 11-10

11.3.1 Graph Representation using Adjacf'.ncy Matrix
11-10

11.3.2 Linked Representation of Graph 11-12
Graph Traversal 11-15

11.4.1 Depth-first-Search
11-15

11.4.1.1 Algorithm for Df S
11-19

11.4.1.2 Program to Demonstrate Depth first Search using Adjacency Matrix 11-19

Table of Contents 11

Data Structure & Algorithms (M)

11.4.1.3 Program to Demonstrate Depth First Search using Linked List 11-26

11.4.1.4 DFS Spann'lI'Iglree 11-35

11.4.1.5 Efficiency of DFS · 11-36

11.4.2 Breadth-First Search (BFS) 11-36

11.4.2.1 Algorithm for BFS 11-39

11.4.2.2 Program to Demonstrate Breadth First Search using Adjacency Matrix 11-39

11.4.2.3 Program to Demonstrate Breadth First Search using Linked List 11

11.4.2.4 BFS Spanning Tree 11-5:

11.4.2.5 Efficiency of BFS 11-5

11.5 Shortest Path Problem 11-5

11.5.1 Dijkstra's Shortest Path Algorithm 11-5

11.5.2 ExampIe 11-:0;;

11.5.3 Program for Dijkstra's Shortest Path 11

11.5.4 Efficiency of Dijkstra's Algorithm 11

11.6 Mini mum Spanning Tree 11

11.6.1 Prim's Algorithm 11

11.6.1.1 Algorithm u

11.6.1.2 Example !:

11.6.1.3 Program for Prim's Algol·jthm .; :~

11.6.1.4 Efficiency for Prim's Algorithm :!

11.6.2 Kruskal's Algorithm _ :.~

11.6.2.1 Kruskal's Algorithm .

11.6.2.2 ExampIe _._

11.6.2.3 Program for Kruskal's Algorithm _

11.6.2.4 Efficiency of Kruskal's Algorithm .

11.7 Solved Examples .

11.8 Previous University Questions and Answers .

JTSTUDY

Tuesday, November 11, 2008

ANIMATED DATA STRUCTURE MUST SEE !!!!!

TECH - MAX DATA STRUCTURE & ALGORITHM IN JAVA FOR IT

DATA STRUCTURE & FILES IN JAVA PROGRAM

DATA STRUCTURE IN JAVA PROGRAM

TECH MAX JAVA PROGRAMS

Monday, November 10, 2008

TIME TABLE FOR EXAM (NOT CONFIIRMED)

Sunday, November 9, 2008

TECH MAX Data Structure & Algorithm in java Syllabus

SYLLABUS FOR DBMS & GUI

Tuesday, November 4, 2008

MERIT LIST PROGRAM

LIBRARY MANAGEMENT PROJECT

INVENTORY PROJECT

PAYROLL PROJECT

EXTRA DBMS PRACTICALS TO DOWNLOAD

INCOME TAX PROJECT

JTSEARCH

Labels

Blog Archive

GOOGLE TRANSLATE

Followers

About Me