DSA EXAM NOTES (JAVA)
CO1: Algorithm Analysis, Searching & Sorting
1. Algorithm & Problem Analysis
Definition
An algorithm is a finite sequence of well-defined steps to solve a problem.
Algorithm Efficiency
Efficiency is measured using: - Time Complexity → how execution time grows with input size - Space
Complexity → how memory usage grows with input size
2. Asymptotic Notations
Big-O (O) – Upper Bound
Represents worst-case time complexity.
Example:
for(int i=0;i<n;i++){
[Link](i);
}
Time Complexity: O(n)
Big-Omega (Ω) – Lower Bound
Represents best-case time complexity.
Example: Linear search when element found at first index Ω(1)
Big-Theta (Θ) – Tight Bound
Represents average-case complexity.
1
3. Recurrence Relation
Used to express recursive algorithms.
Example (Merge Sort): T(n) = 2T(n/2) + n
4. Searching Algorithms
Linear Search
Definition: Sequentially checks each element.
static int linearSearch(int[] a, int key){
for(int i=0;i<[Link];i++){
if(a[i]==key) return i;
}
return -1;
}
Input: a = {10,20,30}, key=20
Output: 1
Time Complexity: O(n)
Binary Search
Definition: Searches in a sorted array by dividing into halves.
static int binarySearch(int[] a, int key){
int low=0, high=[Link]-1;
while(low<=high){
int mid=(low+high)/2;
if(a[mid]==key) return mid;
else if(a[mid]<key) low=mid+1;
else high=mid-1;
}
return -1;
}
Input: a={10,20,30,40}, key=30
Output: 2
Time Complexity: O(log n)
2
5. Sorting Algorithms
Bubble Sort
Definition: Repeatedly swaps adjacent elements.
static void bubbleSort(int[] a){
for(int i=0;i<[Link]-1;i++){
for(int j=0;j<[Link]-1-i;j++){
if(a[j]>a[j+1]){
int t=a[j]; a[j]=a[j+1]; a[j+1]=t;
}
}
}
}
Time Complexity: O(n²)
Selection Sort
static void selectionSort(int[] a){
for(int i=0;i<[Link]-1;i++){
int min=i;
for(int j=i+1;j<[Link];j++){
if(a[j]<a[min]) min=j;
}
int t=a[min]; a[min]=a[i]; a[i]=t;
}
}
Time Complexity: O(n²)
Insertion Sort
static void insertionSort(int[] a){
for(int i=1;i<[Link];i++){
int key=a[i], j=i-1;
while(j>=0 && a[j]>key){
a[j+1]=a[j]; j--;
}
a[j+1]=key;
}
}
3
Best Case: O(n)
Merge Sort
static void mergeSort(int[] a, int l, int r){
if(l<r){
int m=(l+r)/2;
mergeSort(a,l,m);
mergeSort(a,m+1,r);
merge(a,l,m,r);
}
}
Time Complexity: O(n log n)
Quick Sort
static void quickSort(int[] a, int low, int high){
if(low<high){
int p=partition(a,low,high);
quickSort(a,low,p-1);
quickSort(a,p+1,high);
}
}
Average Case: O(n log n)
CO2: Abstract Data Types (ADT)
6. Arrays as ADT
Operations: Insert, Delete, Search, Traverse
Insert at end:
a[size++] = value;
4
7. Linked List
Singly Linked List
class Node{
int data;
Node next;
Node(int d){data=d; next=null;}
}
Insert at Beginning
Node newNode = new Node(10);
[Link] = head;
head = newNode;
Delete Node
if([Link]==key) head=[Link];
Reverse Linked List
Node prev=null, curr=head;
while(curr!=null){
Node next=[Link];
[Link]=prev;
prev=curr;
curr=next;
}
head=prev;
Detect Cycle (Floyd’s Algorithm)
Node slow=head, fast=head;
while(fast!=null && [Link]!=null){
slow=[Link];
fast=[Link];
if(slow==fast) return true;
5
}
return false;
8. Doubly Linked List
Each node has: - prev - data - next
Better traversal but more memory.
9. Circular Linked List
Last node points to first node. Used in: - Round robin scheduling
EXAM TIPS
• Always write definition + algorithm + complexity
• For 11-mark questions → explanation + code + dry run
• Sorting & Linked List are HIGH priority
MOST EXPECTED EXAM QUESTIONS & READY ANSWERS
SECTION–1 (2 MARKS) – VERY IMPORTANT
1. Define Algorithm.
An algorithm is a finite set of well-defined steps used to solve a problem.
2. Define Time Complexity.
Time complexity measures how the running time of an algorithm grows with input size.
3. Define Big-O notation.
Big-O represents the upper bound (worst-case) time complexity of an algorithm.
4. What is Recurrence Relation?
A recurrence relation expresses the time complexity of a recursive algorithm in terms of smaller
inputs.
5. Define ADT.
An Abstract Data Type defines data and operations without specifying implementation details.
6. Difference between Linear and Binary Search (one point).
Linear search works on unsorted data; binary search requires sorted data.
6
SECTION–2 (4 MARKS) – IMPORTANT QUESTIONS
Q1. Explain Linear Search with algorithm and complexity.
Definition: Linear search checks elements one by one until the key is found.
Algorithm: 1. Start from first element 2. Compare each element with key 3. Stop if found or end
reached
Complexity: O(n)
Q2. Explain Binary Search with example.
Binary search divides the sorted array into halves to search efficiently.
Complexity: O(log n)
Q3. Explain Bubble Sort.
Bubble sort repeatedly swaps adjacent elements if they are in wrong order.
Complexity: O(n²)
Q4. Explain Singly Linked List.
A singly linked list contains nodes where each node has data and a next pointer.
Advantages: Dynamic size, efficient insertion/deletion.
SECTION–3 (11 MARKS) – EITHER QUESTION
Q3(a). Explain Merge Sort with algorithm and complexity.
Merge sort uses divide and conquer technique.
Steps: 1. Divide array into halves 2. Sort each half recursively 3. Merge sorted halves
Time Complexity: O(n log n)
Q3(b). Write a Java program for Binary Search.
(Use code from CO1 section)
7
SECTION–4 (11 MARKS) – EITHER QUESTION
Q5(a). Explain operations on Singly Linked List.
Operations include insertion, deletion, traversal, and reversal.
Q5(b). Write a Java program to reverse a linked list.
(Use reverse code from CO2 section)
HIGH-SCORING TIPS
• Write definition first (guaranteed marks)
• Draw small diagram for linked list
• Always mention time complexity
✅ These notes are exam-oriented + interview-useful