1.

Basic and Advanced Data Structures

Theoretical Explanation

Data structures are specialized formats for organizing, processing, retrieving, and
storing data. They are fundamental to algorithm design because the choice of data
structure directly impacts the efficiency and complexity of an algorithm.

 Basic Data Structures:

o Arrays: A contiguous block of memory storing elements of the same type. Provides
O(1) access by index but O(n) for insertion/deletion in the middle.
o Linked Lists: A sequence of nodes, where each node points to the next. Allows O(1)
insertion/deletion at the head, but O(n) access by index.
o Stacks: A LIFO (Last-In, First-Out) structure. Operations: push (add), pop (remove).
o Queues: A FIFO (First-In, First-Out) structure.
Operations: enqueue (add), dequeue (remove).
o Hash Tables: A structure that maps keys to values using a hash function. Provides
average-case O(1) time for insert, delete, and search.
 Advanced Data Structures (as covered in CLRS):
o Binary Search Trees (BST): A tree where each node has at most two children, and
for any node, all left descendants are less than the node, and all right descendants
are greater. Average-case O(log n) for search, insert, delete.
o Balanced BSTs (e.g., Red-Black Trees): BSTs that automatically maintain a
balanced height after insertions and deletions, guaranteeing O(log n) time for core
operations in the worst case. This is a crucial data structure used in
Java's TreeMap and TreeSet.
o Heaps (Priority Queues): A complete binary tree where each node is greater than
or equal to (max-heap) or less than or equal to (min-heap) its children. Provides
O(log n) for insert and extract-max/min, and O(1) for find-max/min.
o Graphs: A collection of nodes (vertices) and connections (edges). Can be
represented via Adjacency Matrices (O(1) edge lookup, O(V²) space) or Adjacency
Lists (O(V+E) space, efficient for sparse graphs).
o Tries (Prefix Trees): A tree-like structure for storing strings. Each node represents
a common prefix. Excellent for autocomplete and dictionary implementations with
O(L) search/insert, where L is the length of the string.
o Disjoint-Set (Union-Find): A structure that keeps track of a partition of a set into
disjoint subsets. It supports two main operations: union (merge two sets)
and find (determine which set an element is in). Crucial for algorithms like Kruskal's.

Java Code Example: Red-Black Tree (Balanced BST)

Java's TreeMap is implemented using a Red-Black Tree. Here's a simplified

demonstration.
java
Copy
Download
import [Link];

public class RedBlackTreeExample {

public static void main(String[] args) {
// TreeMap is implemented as a Red-Black Tree in Java
TreeMap<Integer, String> studentMap = new TreeMap<>();
 // Insertion - O(log n)
[Link](101, "Alice");
[Link](102, "Bob");
[Link](100, "Charlie");
[Link](105, "Diana");

// The tree automatically remains balanced

[Link]("Student with lowest ID (first entry): " + [Link]());

// Search - O(log n)
int searchKey = 102;
if ([Link](searchKey)) {
[Link]("Student with ID " + searchKey + ": " +
[Link](searchKey));
}

// In-order traversal provides sorted order - O(n)

[Link]("\nAll students in sorted order:");
for (var entry : [Link]()) {
[Link]("ID: " + [Link]() + ", Name: " + [Link]());
}

// Delete - O(log n)
[Link](100);
[Link]("\nAfter removing ID 100: " + studentMap);
}
}

2. Algorithm Analysis
Theoretical Explanation

Algorithm analysis provides a theoretical framework for predicting the resource

consumption of an algorithm, primarily its time complexity (running time)
and space complexity (memory usage). The goal is to understand how an
algorithm scales with the input size, *n*.

 Asymptotic Analysis: We focus on the growth rate as *n* approaches infinity,

ignoring machine-dependent constants and lower-order terms. This is described
using Asymptotic Notation.
o Big-O Notation (O): Describes the upper bound or worst-case growth rate. E.g.,
"The algorithm runs in O(n²) time."
o Big-Omega Notation (Ω): Describes the lower bound or best-case growth rate.
o Big-Theta Notation (Θ): Describes a tight bound, meaning both the upper and
lower bounds are the same. This is the most precise description of an algorithm's
growth rate.
 Common Complexity Classes:
o O(1): Constant time. (e.g., accessing an array element by index).
o O(log n): Logarithmic time. (e.g., binary search in a sorted array).
o O(n): Linear time. (e.g., finding the maximum element in an unsorted array).
o O(n log n): Linearithmic time. (e.g., efficient sorting algorithms like Merge Sort and
Heap Sort).
o O(n²): Quadratic time. (e.g., simple sorting algorithms like Bubble Sort, checking all
pairs in a list).
o O(2ⁿ): Exponential time. (e.g., the naive recursive solution for the Fibonacci
sequence).
 Methodology (as in CLRS): Analysis often involves setting up a recurrence
relation, especially for divide-and-conquer algorithms, and then solving it using
methods like the Master Theorem.

Java Code Example: Empirical vs. Theoretical Analysis

We can compare a linear O(n) algorithm with a quadratic O(n²) algorithm empirically.
java
Copy
Download
public class AlgorithmAnalysis {

// O(n) Linear Algorithm: Find sum of an array

public static long findSumLinear(int[] arr) {
long sum = 0;
for (int num : arr) {
sum += num;
}
return sum;
}

// O(n^2) Quadratic Algorithm: Find all pairs of elements

public static void printAllPairs(int[] arr) {
int n = [Link];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// [Link]("(" + arr[i] + ", " + arr[j] + ")");
// Commented out to avoid flooding the console, we just do the work.
int dummy = arr[i] + arr[j]; // Simulating some work
}
}
}

public static void main(String[] args) {

// Create a large input
int n = 10000;
int[] testArray = new int[n];
for (int i = 0; i < n; i++) {
testArray[i] = i + 1;
}

// Time the O(n) operation

long startTime = [Link]();
long sum = findSumLinear(testArray);
long endTime = [Link]();
long linearTime = endTime - startTime;
[Link]("O(n) Sum: " + sum + ", Time taken: " + linearTime / 1e6 + "
ms");

// Time the O(n^2) operation

startTime = [Link]();
printAllPairs(testArray);
endTime = [Link]();
long quadraticTime = endTime - startTime;
 [Link]("O(n^2) Pairs printed. Time taken: " + quadraticTime / 1e6 + "
ms");

[Link]("\nThe O(n^2) algorithm was " + (quadraticTime / linearTime) +

" times slower for n=" + n);
}
}

Output Insight: You will observe that the O(n²) algorithm takes thousands of times
longer than the O(n) algorithm for n=10,000, demonstrating the dramatic impact of
time complexity.

3. Sorting and Searching

Theoretical Explanation

These are perhaps the most studied classes of algorithms.

 Sorting:
o Comparison Sorts: Algorithms that sort by comparing elements.
 Merge Sort: A divide-and-conquer algorithm. It recursively splits the list, sorts the
halves, and then merges them. Guarantees O(n log n) time and is stable, but
requires O(n) auxiliary space.
 Quicksort: Another divide-and-conquer algorithm. It picks a 'pivot', partitions the
array around the pivot, and recursively sorts the sub-arrays. Average-case O(n log
n), but worst-case O(n²). However, it is often faster in practice due to cache
efficiency and uses O(log n) space (for the call stack).
 Heapsort: Builds a max-heap and repeatedly extracts the maximum
element. Guarantees O(n log n) time and is in-place, but is not stable and is often
slower than Quicksort on average.
o Non-Comparison Sorts: For data with specific properties (e.g., integers in a limited
range).
 Counting Sort: Counts the occurrences of each element. Runs in O(n + k) time,
where k is the range of input.
 Searching:
o Linear Search: Sequentially checks every element. O(n) time.
o Binary Search: Repeatedly halves the search interval in a sorted array. O(log n)
time. A classic example of a decrease-and-conquer strategy.

Java Code Example: Quicksort and Binary Search

java
Copy
Download
import [Link];

public class SortingSearching {

// QUICKSORT - O(n log n) average, O(n^2) worst-case

public static void quicksort(int[] arr, int low, int high) {
if (low < high) {
 // pi is partitioning index, arr[pi] is now at right place
int pi = partition(arr, low, high);
// Recursively sort elements before and after partition
quicksort(arr, low, pi - 1);
quicksort(arr, pi + 1, high);
}
}

private static int partition(int[] arr, int low, int high) {

int pivot = arr[high];
int i = (low - 1); // index of smaller element
for (int j = low; j < high; j++) {
// If current element is smaller than or equal to pivot
if (arr[j] <= pivot) {
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}

// BINARY SEARCH - O(log n)

public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = [Link] - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // Avoid potential overflow
if (arr[mid] == target) {
return mid; // Found the target
} else if (arr[mid] < target) {
left = mid + 1; // Search in the right half
} else {
right = mid - 1; // Search in the left half
}
}
return -1; // Target not found
}

public static void main(String[] args) {

int[] arrayToSort = {64, 34, 25, 12, 22, 11, 90, 5};
[Link]("Original array: " + [Link](arrayToSort));

quicksort(arrayToSort, 0, [Link] - 1);

[Link]("Sorted array: " + [Link](arrayToSort));

int target = 22;

int result = binarySearch(arrayToSort, target);
if (result == -1) {
[Link]("Element " + target + " not found in the array.");
} else {
[Link]("Element " + target + " found at index: " + result);
}
 }
}

4. Dynamic Programming
Theoretical Explanation

Dynamic Programming (DP) is a powerful technique for solving optimization

problems by breaking them down into simpler subproblems. It avoids recomputing
the same subproblem by storing their results (a technique called memoization or
using a DP table).

 Key Properties (CLRS):

1. Optimal Substructure: An optimal solution to the problem contains optimal
solutions to its subproblems.
2. Overlapping Subproblems: The problem can be broken down into subproblems
which are reused several times.
 Approaches:

o Top-Down with Memoization: We start at the original problem and recursively

break it down, but we cache the result of each subproblem the first time we solve it.
o Bottom-Up (Tabulation): We solve all the smaller subproblems first and use their
solutions to build solutions to larger subproblems, typically by filling up a table.
 Classic Problems: Fibonacci Sequence, 0/1 Knapsack Problem, Longest Common
Subsequence (LCS), Matrix Chain Multiplication, Shortest Path algorithms (Bellman-
Ford).

Java Code Example: 0/1 Knapsack Problem

Given weights and values of items, determine the maximum value that can be
carried in a knapsack of a given capacity.
java
Copy
Download
public class DynamicProgramming {

// Top-Down Memoization solution for 0/1 Knapsack

public static int knapsackMemo(int[] weights, int[] values, int capacity) {
int n = [Link];
Integer[][] dp = new Integer[n + 1][capacity + 1];
return knapsackHelper(weights, values, capacity, n, dp);
}

private static int knapsackHelper(int[] weights, int[] values, int capacity, int n,
Integer[][] dp) {
// Base Case: No items or no capacity left
if (n == 0 || capacity == 0) {
return 0;
}
// If value is already computed, return it
if (dp[n][capacity] != null) {
return dp[n][capacity];
 }
// If weight of the nth item is more than capacity, it cannot be included
if (weights[n - 1] > capacity) {
dp[n][capacity] = knapsackHelper(weights, values, capacity, n - 1, dp);
} else {
// Return the maximum of two cases:
// 1. nth item included
int include = values[n - 1] + knapsackHelper(weights, values, capacity -
weights[n - 1], n - 1, dp);
// 2. nth item not included
int exclude = knapsackHelper(weights, values, capacity, n - 1, dp);
dp[n][capacity] = [Link](include, exclude);
}
return dp[n][capacity];
}

// Bottom-Up Tabulation solution for 0/1 Knapsack

public static int knapsackTabulation(int[] weights, int[] values, int capacity) {
int n = [Link];
int[][] dp = new int[n + 1][capacity + 1];

// Build table dp[][] in bottom-up manner

for (int i = 0; i <= n; i++) {
for (int w = 0; w <= capacity; w++) {
if (i == 0 || w == 0) {
dp[i][w] = 0;
} else if (weights[i - 1] <= w) {
dp[i][w] = [Link](values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][capacity];
}

public static void main(String[] args) {

int[] values = {60, 100, 120};
int[] weights = {10, 20, 30};
int capacity = 50;

int maxValueMemo = knapsackMemo(weights, values, capacity);

int maxValueTab = knapsackTabulation(weights, values, capacity);

[Link]("0/1 Knapsack Problem");

[Link]("Weights: " + [Link](weights));
[Link]("Values: " + [Link](values));
[Link]("Capacity: " + capacity);
[Link]("Maximum value (Memoization): " + maxValueMemo);
[Link]("Maximum value (Tabulation): " + maxValueTab);
}
}

5. Graph Algorithms
 Theoretical Explanation

Graphs model pairwise relationships between objects. Key algorithms include:

 Graph Traversal:
o Breadth-First Search (BFS): Explores a graph level by level. Uses a queue.
Excellent for finding the shortest path in unweighted graphs. O(V + E) time.
o Depth-First Search (DFS): Explores as far as possible along each branch before
backtracking. Uses a stack (often via recursion). Useful for cycle detection,
topological sorting, and solving puzzles. O(V + E) time.
 Shortest Path:
o Dijkstra's Algorithm: Finds the shortest path from a source node to all other nodes
in a weighted graph with non-negative weights. Uses a priority queue. O((V +
E) log V) time.
o Bellman-Ford Algorithm: Finds the shortest path from a source node in a
weighted graph, even with negative weight edges (but not negative cycles).
Slower than Dijkstra: O(V * E).
 Minimum Spanning Tree (MST): A subset of edges that connects all vertices with
the minimum total edge weight.
o Kruskal's Algorithm: Sorts all edges and adds them to the MST if they don't form a
cycle (using Union-Find). O(E log V) time.
o Prim's Algorithm: Grows the MST one vertex at a time, adding the cheapest edge
from the tree to a vertex not yet in the tree. O(E log V) time.

Java Code Example: BFS for Shortest Path in Unweighted Graph

java
Copy
Download
import [Link].*;

public class GraphAlgorithms {

// BFS to find shortest path in an unweighted graph

public static void bfsShortestPath(List<List<Integer>> graph, int start, int target) {
int n = [Link]();
boolean[] visited = new boolean[n];
int[] parent = new int[n]; // To reconstruct the path
[Link](parent, -1);

Queue<Integer> queue = new LinkedList<>();

[Link](start);
visited[start] = true;

[Link]("BFS Traversal order:");

while (![Link]()) {
int current = [Link]();
[Link](current + " ");

// If we found the target, we can break early

if (current == target) {
break;
}

for (int neighbor : [Link](current)) {

if (!visited[neighbor]) {
visited[neighbor] = true;
 parent[neighbor] = current; // Record where we came from
[Link](neighbor);
}
}
}
[Link]();

// Reconstruct and print the shortest path

printShortestPath(parent, start, target);
}

private static void printShortestPath(int[] parent, int start, int target) {

if (parent[target] == -1 && start != target) {
[Link]("No path from " + start + " to " + target);
return;
}
List<Integer> path = new ArrayList<>();
for (int at = target; at != -1; at = parent[at]) {
[Link](at);
}
[Link](path);
[Link]("Shortest path from " + start + " to " + target + ": " + path);
}

public static void main(String[] args) {

// Graph representation using Adjacency List
int numNodes = 6;
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numNodes; i++) {
[Link](new ArrayList<>());
}

// Adding edges (undirected graph)

[Link](0).add(1);
[Link](0).add(2);
[Link](1).add(0);
[Link](1).add(3);
[Link](2).add(0);
[Link](2).add(3);
[Link](2).add(4);
[Link](3).add(1);
[Link](3).add(2);
[Link](3).add(5);
[Link](4).add(2);
[Link](4).add(5);
[Link](5).add(3);
[Link](5).add(4);

int startNode = 0;
int targetNode = 5;
bfsShortestPath(graph, startNode, targetNode);
}
}

6. Greedy Algorithms
 Theoretical Explanation

A greedy algorithm builds up a solution piece by piece, always choosing the next
piece that offers the most obvious and immediate benefit. It makes a locally optimal
choice at each stage, hoping to find a global optimum.

 Key Property (Kleinberg & Tardos): Greedy algorithms are often used for
optimization problems. They are usually easy to design and efficient, but they do
not always yield the globally optimal solution. Proving their correctness is
crucial.
 When do they work? For problems that exhibit the greedy-choice property (a
global optimum can be arrived at by selecting a local optimum) and optimal
substructure.
 Classic Examples:
o Huffman Coding: For lossless data compression.
o Dijkstra's Algorithm: For shortest paths (greedy on the current shortest known
distance).
o Kruskal's & Prim's Algorithms: For MST.
o Fractional Knapsack: Where taking the item with the highest value/weight ratio is
optimal.

Java Code Example: Huffman Coding (Information Compression)

This is a classic greedy algorithm for data compression.

java
Copy
Download
import [Link].*;

// A node in the Huffman Tree

class HuffmanNode implements Comparable<HuffmanNode> {
char data;
int frequency;
HuffmanNode left, right;

public HuffmanNode(char data, int frequency) {

[Link] = data;
[Link] = frequency;
[Link] = null;
[Link] = null;
}

@Override
public int compareTo(HuffmanNode other) {
return [Link] - [Link];
}
}

public class GreedyAlgorithms {

public static void main(String[] args) {

String testString = "huffman coding example";
[Link]("Original String: " + testString);

// Step 1: Build frequency map

Map<Character, Integer> freqMap = new HashMap<>();
for (char c : [Link]()) {
 [Link](c, [Link](c, 0) + 1);
}

// Step 2: Build Huffman Tree using a Priority Queue (Min-Heap)

PriorityQueue<HuffmanNode> pq = new PriorityQueue<>();
for (var entry : [Link]()) {
[Link](new HuffmanNode([Link](), [Link]()));
}

// Greedy step: Repeatedly combine the two nodes with the smallest frequency
while ([Link]() > 1) {
HuffmanNode left = [Link]();
HuffmanNode right = [Link]();
HuffmanNode parent = new HuffmanNode('-', [Link] + [Link]);
[Link] = left;
[Link] = right;
[Link](parent);
}
HuffmanNode root = [Link](); // Root of the Huffman Tree

// Step 3: Generate Huffman Codes by traversing the tree

Map<Character, String> huffmanCodes = new HashMap<>();
generateCodes(root, "", huffmanCodes);

[Link]("\nHuffman Codes:");
for (var entry : [Link]()) {
[Link]("'" + [Link]() + "' : " + [Link]());
}

// Step 4: Encode the original string

StringBuilder encodedString = new StringBuilder();
for (char c : [Link]()) {
[Link]([Link](c));
}
[Link]("\nEncoded Bitstring: " + encodedString);

// Calculate compression ratio (simplified)

int originalBits = [Link]() * 8; // Assuming 8-bit ASCII
int encodedBits = [Link]();
double compressionRatio = (1.0 - (double) encodedBits / originalBits) * 100;
[Link]("Compression saved: %.2f%% of original bit size%n",
compressionRatio);
}

private static void generateCodes(HuffmanNode node, String code, Map<Character,

String> huffmanCodes) {
if (node == null) return;
// If it's a leaf node, it contains a character
if ([Link] == null && [Link] == null) {
[Link]([Link], [Link]() ? "0" : code); // Handle single
character case
}
generateCodes([Link], code + "0", huffmanCodes);
generateCodes([Link], code + "1", huffmanCodes);
}
}
 7. Information Compression Algorithms
Theoretical Explanation

Compression algorithms reduce the number of bits needed to represent data. They
are broadly classified into:

 Lossless Compression: The original data can be perfectly reconstructed from the
compressed data. Essential for text, code, and certain types of images (e.g., PNG).
o Run-Length Encoding (RLE): Replaces sequences of the same data value (runs)
with a single value and a count.
o Huffman Coding (Greedy): Uses variable-length codes, where more frequent
characters have shorter codes.
o Lempel-Ziv-Welch (LZW): Builds a dictionary of frequently occurring patterns.
Used in GIF and PDF files.
 Lossy Compression: Some information is permanently discarded, but ideally in a
way that is not easily perceptible. Used for images (JPEG), audio (MP3), and video
(MPEG).
o JPEG: Uses Discrete Cosine Transform (DCT) to convert image data into frequency
components, which are then quantized (reduced in precision).
o MP3: Uses psychoacoustics to remove sounds that the human ear is less likely to
perceive.

Java Code Example: Run-Length Encoding (RLE)

A simple yet effective lossless compression method.

java
Copy
Download
public class InformationCompression {

// Run-Length Encoding (Lossless Compression)

public static String runLengthEncode(String input) {
if (input == null || [Link]()) {
return "";
}
StringBuilder encoded = new StringBuilder();
int count = 1;
for (int i = 1; i < [Link](); i++) {
if ([Link](i) == [Link](i - 1)) {
count++;
} else {
[Link]([Link](i - 1)).append(count);
count = 1; // Reset count for the new character
}
}
// Append the last character and its count
[Link]([Link]([Link]() - 1)).append(count);
return [Link]();
}

// Run-Length Decoding
public static String runLengthDecode(String encoded) {
if (encoded == null || [Link]()) {
return "";
}
 StringBuilder decoded = new StringBuilder();
// Assumes the encoded string is well-formed: [char][count][char][count]...
for (int i = 0; i < [Link](); i += 2) {
char character = [Link](i);
int count = [Link]([Link](i + 1));
// Append the character 'count' times
for (int j = 0; j < count; j++) {
[Link](character);
}
}
return [Link]();
}

public static void main(String[] args) {

String originalData = "AAAAAAABBBBBBCCCCDDDDAAA";
[Link]("Original Data: " + originalData);
[Link]("Original Data Size: " + [Link]() + " characters");

String compressedData = runLengthEncode(originalData);

[Link]("\nCompressed Data (RLE): " + compressedData);
[Link]("Compressed Data Size: " + [Link]() + "
characters");

String decompressedData = runLengthDecode(compressedData);

[Link]("\nDecompressed Data: " + decompressedData);
[Link]("Decompressed Data Size: " + [Link]() + "
characters");

// Verify losslessness
boolean isLossless = [Link](decompressedData);
[Link]("\nLossless Compression Verified: " + isLossless);

if (isLossless) {
double compressionRatio = (1.0 - (double) [Link]() /
[Link]()) * 100;
[Link]("Compression saved: %.2f%% of original size%n",
compressionRatio);
}
}
}

This concludes the detailed explanation and code examples for all seven requested
subjects, presented in the academic style of the referenced textbooks. Each section
provides a theoretical foundation and a practical Java implementation to solidify the
concepts.

1. Temel ve İleri Düzey Veri Yapıları

Teorik Açıklama

Veri yapıları, veriyi düzenlemek, işlemek, almak ve depolamak için özelleşmiş

formatlardır. Algoritma tasarımının temelini oluştururlar çünkü veri yapısı seçimi, bir
algoritmanın verimliliğini ve karmaşıklığını doğrudan etkiler.

 Temel Veri Yapıları:

o Diziler (Arrays): Aynı türden elemanları depolayan bitişik bir bellek bloğu. İndeksle
erişim O(1) sağlar ancak ortada ekleme/silme O(n)'dir.
o Bağlı Listeler (Linked Lists): Her bir düğümün bir sonrakini işaret ettiği bir
düğümler dizisi. Başa ekleme/silme O(1) sağlar ancak indeksle erişim O(n)'dir.
o Yığınlar (Stacks): LIFO (Last-In, First-Out / Son Giren İlk Çıkar) yapısı.
İşlemler: push (ekle), pop (çıkar).
o Kuyruklar (Queues): FIFO (First-In, First-Out / İlk Giren İlk Çıkar) yapısı.
İşlemler: enqueue (ekle), dequeue (çıkar).
o Hash Tabloları (Hash Tables): Bir hash fonksiyonu kullanarak anahtarları
değerlere eşleyen bir yapı. Ekleme, silme ve arama için ortalama O(1) zaman sağlar.
 İleri Düzey Veri Yapıları (CLRS'de anlatıldığı şekliyle):
o İkili Arama Ağaçları (Binary Search Trees - BST): Her düğümün en fazla iki
çocuğu olduğu ve herhangi bir düğüm için, tüm sol torunların düğümden küçük, tüm
sağ torunların büyük olduğu bir ağaç. Arama, ekleme, silme için ortalama O(log n)
zaman.
o Dengeli BST'ler (Örn: Kırmızı-Siyah Ağaçlar): Ekleme ve silme işlemlerinden
sonra otomatik olarak dengeli bir yüksekliği koruyan BST'ler. En kötü durumda
çekirdek işlemler için O(log n) zamanını garanti eder.
Java'daki TreeMap ve TreeSet tarafından kullanılan çok önemli bir veri yapısıdır.
o Yığınlar (Heaps - Öncelik Kuyrukları): Her düğümün çocuklarından büyük veya
eşit (max-heap) ya da küçük veya eşit (min-heap) olduğu tam ikili ağaç. Ekleme ve
max/min çıkarma için O(log n), max/min bulma için O(1) sağlar.
o Grafikler (Graphs): Düğümler (köşeler) ve bağlantılardan (kenarlar) oluşan bir
koleksiyon. Komşuluk Matrisi (O(1) kenar arama, O(V²) bellek) veya Komşuluk
Listeleri (O(V+E) bellek, seyrek grafikler için verimli) ile temsil edilebilir.
o Tries (Prefix Ağaçları): String'leri saklamak için ağaç benzeri bir yapı. Her düğüm
ortak bir öneki temsil eder. O(L) arama/ekleme ile otomatik tamamlama ve sözlük
uygulamaları için mükemmeldir (L, string uzunluğu).
o Ayrık Küme (Disjoint-Set - Union-Find): Bir kümenin ayrık alt kümeler halinde bir
bölümünü takip eden bir yapı. İki ana işlemi destekler: union (iki kümeyi birleştir)
ve find (bir elemanın hangi kümede olduğunu belirle). Kruskal algoritması gibi
algoritmalar için çok önemlidir.

Java Kodu Örneği: Kırmızı-Siyah Ağaç (Dengeli BST)

Java'daki TreeMap, bir Kırmızı-Siyah Ağaç kullanılarak gerçekleştirilmiştir. İşte

basitleştirilmiş bir gösterim.
java
Copy
Download
import [Link];

public class RedBlackTreeOrnegi {

public static void main(String[] args) {
// TreeMap, Java'da bir Kırmızı-Siyah Ağaç olarak gerçekleştirilir.
TreeMap<Integer, String> ogrenciMap = new TreeMap<>();

// Ekleme - O(log n)
[Link](101, "Ali");
[Link](102, "Ayşe");
[Link](100, "Mehmet");
[Link](105, "Zeynep");

// Ağaç otomatik olarak dengeli kalır.

[Link]("En düşük ID'li öğrenci (ilk giriş): " + [Link]());

// Arama - O(log n)
int arananAnahtar = 102;
 if ([Link](arananAnahtar)) {
[Link](arananAnahtar + " ID'li öğrenci: " +
[Link](arananAnahtar));
}

// In-order dolaşım, sıralı bir liste sağlar - O(n)

[Link]("\nTüm öğrenciler sıralı şekilde:");
for (var entry : [Link]()) {
[Link]("ID: " + [Link]() + ", İsim: " + [Link]());
}

// Silme - O(log n)
[Link](100);
[Link]("\n100 ID'si silindikten sonra: " + ogrenciMap);
}
}

2. Algoritma Analizi
Teorik Açıklama

Algoritma analizi, bir algoritmanın kaynak tüketimini, öncelikle zaman

karmaşıklığını (çalışma süresi) ve bellek karmaşıklığını (bellek kullanımı) teorik
olarak tahmin etmek için bir çerçeve sağlar. Amaç, bir algoritmanın girdi
büyüklüğü *n* ile nasıl ölçeklendiğini anlamaktır.

 Asimptotik Analiz: *n* sonsuza yaklaşırken büyüme oranına odaklanırız, makineye

bağlı sabitleri ve düşük dereceli terimleri görmezden geliriz. Bu, Asimptotik
Notasyon ile tanımlanır.
o Büyük-O Notasyonu (O): Üst sınırı veya en kötü durum büyüme oranını tanımlar.
Örn: "Algoritma O(n²) zamanında çalışır."
o Büyük-Omega Notasyonu (Ω): Alt sınırı veya en iyi durum büyüme oranını
tanımlar.
o Büyük-Theta Notasyonu (Θ): Sıkı bir sınırı tanımlar, yani hem üst hem de alt
sınırlar aynıdır. Bu, bir algoritmanın büyüme oranının en kesin tanımıdır.
 Yaygın Karmaşıklık Sınıfları:
o O(1): Sabit zaman. (örneğin, bir dizi elemanına indeksle erişim).
o O(log n): Logaritmik zaman. (örneğin, sıralı bir dizide ikili arama).
o O(n): Lineer zaman. (örneğin, sıralanmamış bir dizide maksimum elemanı bulma).
o O(n log n): Lineeritmik zaman. (örneğin, Merge Sort ve Heap Sort gibi verimli
sıralama algoritmaları).
o O(n²): Karesel zaman. (örneğin, Bubble Sort gibi basit sıralama algoritmaları, bir
listedeki tüm çiftleri kontrol etme).
o O(2ⁿ): Üstel zaman. (örneğin, Fibonacci serisi için saf özyinelemeli çözüm).
 Metodoloji (CLRS'de olduğu gibi): Analiz, özellikle böl ve fethet algoritmaları için,
bir yineleme bağıntısı kurmayı ve daha sonra Master Teoremi gibi yöntemlerle
çözmeyi içerir.

Java Kodu Örneği: Ampirik vs. Teorik Analiz

Doğrusal bir O(n) algoritması ile karesel bir O(n²) algoritmasını ampirik olarak
karşılaştırabiliriz.
java
Copy
Download
public class AlgoritmaAnalizi {

// O(n) Lineer Algoritma: Bir dizinin toplamını bul

public static long lineerToplam(int[] arr) {
long toplam = 0;
for (int num : arr) {
toplam += num;
}
return toplam;
}

// O(n^2) Karesel Algoritma: Tüm eleman çiftlerini bul

public static void tumCiftleriYazdir(int[] arr) {
int n = [Link];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// [Link]("(" + arr[i] + ", " + arr[j] + ")");
// Konsolu boğmamak için yorum satırı yapıldı, sadece işi yapıyoruz.
int gecici = arr[i] + arr[j]; // Bir miktar iş yapıyormuş gibi simüle ediyoruz.
}
}
}

public static void main(String[] args) {

// Büyük bir girdi oluştur
int n = 10000;
int[] testDizisi = new int[n];
for (int i = 0; i < n; i++) {
testDizisi[i] = i + 1;
}

// O(n) işleminin süresini ölç

long baslangicZamani = [Link]();
long toplam = lineerToplam(testDizisi);
long bitisZamani = [Link]();
long lineerZaman = bitisZamani - baslangicZamani;
[Link]("O(n) Toplam: " + toplam + ", Geçen süre: " + lineerZaman / 1e6
+ " ms");

// O(n^2) işleminin süresini ölç

baslangicZamani = [Link]();
tumCiftleriYazdir(testDizisi);
bitisZamani = [Link]();
long kareselZaman = bitisZamani - baslangicZamani;
[Link]("O(n^2) Tüm çiftler yazdırıldı. Geçen süre: " + kareselZaman /
1e6 + " ms");

[Link]("\nO(n^2) algoritması, n=" + n + " için O(n) algoritmasından " +

(kareselZaman / lineerZaman) + " kat daha yavaş çalıştı.");
}
}

Çıktı İçgörüsü: n=10,000 için O(n²) algoritmasının O(n) algoritmasından binlerce

kat daha uzun sürdüğünü gözlemleyeceksiniz; bu, zaman karmaşıklığının dramatik
etkisini gösterir.
 3. Sıralama ve Arama
Teorik Açıklama

Bunlar belki de üzerinde en çok çalışılan algoritma sınıflarıdır.

 Sıralama:
o Karşılaştırmalı Sıralamalar: Elemanları karşılaştırarak sıralayan algoritmalar.
 Birleştirmeli Sıralama (Merge Sort): Bir böl ve fethet algoritmasıdır. Listeyi
özyinelemeli olarak böler, yarıları sıralar ve sonra birleştirir. O(n log n) zamanını
garanti eder ve kararlıdır, ancak O(n) ek bellek alanı gerektirir.
 Hızlı Sıralama (Quicksort): Başka bir böl ve fethet algoritmasıdır. Bir 'pivot' seçer,
diziyi pivot etrafında böler ve alt dizileri özyinelemeli olarak sıralar. Ortalama
durumda O(n log n), ancak en kötü durumda O(n²). Ancak, önbellek verimliliği
nedeniyle pratikte genellikle daha hızlıdır ve O(log n) bellek kullanır (çağrı yığını için).
 Yığın Sıralama (Heapsort): Bir max-heap oluşturur ve maksimum elemanı tekrar
tekrar çıkarır. O(n log n) zamanını garanti eder ve yerindedir, ancak kararlı
değildir ve ortalamada Quicksort'tan genellikle daha yavaştır.
o Karşılaştırmasız Sıralamalar: Belirli özelliklere sahip veriler için (örneğin, sınırlı
aralıkta tamsayılar).
 Sayarak Sıralama (Counting Sort): Her elemanın oluşum sayısını sayar. O(n + k)
zamanında çalışır, burada k girdi aralığıdır.
 Arama:
o Lineer Arama: Her elemanı sırayla kontrol eder. O(n) zaman.
o İkili Arama: Sıralı bir dizide arama aralığını tekrar tekrar ikiye böler. O(log n)
zaman. Bir azalt ve fethet stratejisinin klasik bir örneğidir.

Java Kodu Örneği: Hızlı Sıralama ve İkili Arama

java
Copy
Download
import [Link];

public class SiralamaArama {

// HIZLI SIRALAMA - O(n log n) ortalama, O(n^2) en kötü durum

public static void hizliSiralama(int[] dizi, int dusuk, int yuksek) {
if (dusuk < yuksek) {
// pi, bölümleme indeksidir, dizi[pi] şu an doğru yerinde
int pi = bolumle(dizi, dusuk, yuksek);
// Bölümlemeden önceki ve sonraki elemanları özyinelemeli olarak sırala
hizliSiralama(dizi, dusuk, pi - 1);
hizliSiralama(dizi, pi + 1, yuksek);
}
}

private static int bolumle(int[] dizi, int dusuk, int yuksek) {

int pivot = dizi[yuksek];
int i = (dusuk - 1); // Daha küçük elemanın indeksi
for (int j = dusuk; j < yuksek; j++) {
// Mevcut eleman pivottan küçük veya eşitse
 if (dizi[j] <= pivot) {
i++;
// dizi[i] ve dizi[j]'yi değiştir
int temp = dizi[i];
dizi[i] = dizi[j];
dizi[j] = temp;
}
}
// dizi[i+1] ve dizi[yuksek]'i (veya pivot'u) değiştir
int temp = dizi[i + 1];
dizi[i + 1] = dizi[yuksek];
dizi[yuksek] = temp;
return i + 1;
}

// İKİLİ ARAMA - O(log n)

public static int ikiliArama(int[] dizi, int hedef) {
int sol = 0;
int sag = [Link] - 1;
while (sol <= sag) {
int orta = sol + (sag - sol) / 2; // Potansiyel taşmayı önle
if (dizi[orta] == hedef) {
return orta; // Hedef bulundu
} else if (dizi[orta] < hedef) {
sol = orta + 1; // Sağ yarıda ara
} else {
sag = orta - 1; // Sol yarıda ara
}
}
return -1; // Hedef bulunamadı
}

public static void main(String[] args) {

int[] siralanacakDizi = {64, 34, 25, 12, 22, 11, 90, 5};
[Link]("Orijinal dizi: " + [Link](siralanacakDizi));

hizliSiralama(siralanacakDizi, 0, [Link] - 1);

[Link]("Sıralanmış dizi: " + [Link](siralanacakDizi));

int hedef = 22;

int sonuc = ikiliArama(siralanacakDizi, hedef);
if (sonuc == -1) {
[Link](hedef + " elemanı dizide bulunamadı.");
} else {
[Link](hedef + " elemanı " + sonuc + " indeksinde bulundu.");
}
}
}

4. Dinamik Programlama
Teorik Açıklama
 Dinamik Programlama (DP), optimizasyon problemlerini daha basit alt problemlere
bölerek çözen güçlü bir tekniktir. Aynı alt problemi tekrar hesaplamaktan kaçınır
(memorization veya DP tablosu kullanarak sonuçlarını saklama tekniği).

 Temel Özellikler (CLRS):

1. Optimal Alt Yapı: Problemin optimal çözümü, alt problemlerinin optimal
çözümlerini içerir.
2. Üst üste Binen Alt Problemler: Problem, birkaç kez yeniden kullanılan alt
problemlere ayrılabilir.
 Yaklaşımlar:

o Yukarıdan Aşağıya Memorizasyon: Orijinal problemden başlar ve özyinelemeli

olarak alt problemlere ayrıştırırız, ancak her alt problemi ilk çözüşümüzde sonucunu
önbelleğe alırız.
o Aşağıdan Yukarıya (Tablolama): Önce tüm küçük alt problemleri çözer ve
çözümlerini daha büyük alt problemlerin çözümlerini oluşturmak için kullanırız,
genellikle bir tablo doldurarak.
 Klasik Problemler: Fibonacci Serisi, 0/1 Sırt Çantası Problemi, En Uzun Ortak Alt
Dizi (LCS), Matris Zincir Çarpımı, En Kısa Yol algoritmaları (Bellman-Ford).

Java Kodu Örneği: 0/1 Sırt Çantası Problemi

Verilen ağırlık ve değerlere sahip öğeler için, belirli bir kapasitedeki bir sırt çantasına
konulabilecek maksimum değeri belirleyin.
java
Copy
Download
public class DinamikProgramlama {

// 0/1 Sırt Çantası için Yukarıdan Aşağıya Memorizasyon çözümü

public static int sirtCantasiMemo(int[] agirliklar, int[] degerler, int kapasite) {
int n = [Link];
Integer[][] dp = new Integer[n + 1][kapasite + 1];
return sirtCantasiYardimci(agirliklar, degerler, kapasite, n, dp);
}

private static int sirtCantasiYardimci(int[] agirliklar, int[] degerler, int kapasite, int n,
Integer[][] dp) {
// Temel Durum: Öğe kalmadı veya kapasite kalmadı
if (n == 0 || kapasite == 0) {
return 0;
}
// Değer zaten hesaplanmışsa, onu döndür
if (dp[n][kapasite] != null) {
return dp[n][kapasite];
}
// n. öğenin ağırlığı kapasiteden fazlaysa, dahil edilemez
if (agirliklar[n - 1] > kapasite) {
dp[n][kapasite] = sirtCantasiYardimci(agirliklar, degerler, kapasite, n - 1, dp);
} else {
// İki durumun maksimumunu döndür:
// 1. n. öğe dahil edildi
int dahilEt = degerler[n - 1] + sirtCantasiYardimci(agirliklar, degerler, kapasite -
agirliklar[n - 1], n - 1, dp);
// 2. n. öğe dahil edilmedi
int dahilEtme = sirtCantasiYardimci(agirliklar, degerler, kapasite, n - 1, dp);
dp[n][kapasite] = [Link](dahilEt, dahilEtme);
 }
return dp[n][kapasite];
}

// 0/1 Sırt Çantası için Aşağıdan Yukarıya Tablolama çözümü

public static int sirtCantasiTablolama(int[] agirliklar, int[] degerler, int kapasite) {
int n = [Link];
int[][] dp = new int[n + 1][kapasite + 1];

// dp[][] tablosunu aşağıdan yukarıya şekilde oluştur

for (int i = 0; i <= n; i++) {
for (int w = 0; w <= kapasite; w++) {
if (i == 0 || w == 0) {
dp[i][w] = 0;
} else if (agirliklar[i - 1] <= w) {
dp[i][w] = [Link](degerler[i - 1] + dp[i - 1][w - agirliklar[i - 1]], dp[i - 1]
[w]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][kapasite];
}

public static void main(String[] args) {

int[] degerler = {60, 100, 120};
int[] agirliklar = {10, 20, 30};
int kapasite = 50;

int maxDegerMemo = sirtCantasiMemo(agirliklar, degerler, kapasite);

int maxDegerTab = sirtCantasiTablolama(agirliklar, degerler, kapasite);

[Link]("0/1 Sırt Çantası Problemi");

[Link]("Ağırlıklar: " + [Link](agirliklar));
[Link]("Değerler: " + [Link](degerler));
[Link]("Kapasite: " + kapasite);
[Link]("Maksimum değer (Memorizasyon): " + maxDegerMemo);
[Link]("Maksimum değer (Tablolama): " + maxDegerTab);
}
}

5. Graf Algoritmaları
Teorik Açıklama

Grafikler, nesneler arasındaki ikili ilişkileri modeller. Temel algoritmalar şunları içerir:

 Graf Dolaşma:
o Genişlik Öncelikli Arama (BFS): Bir grafı seviye seviye dolaşır. Bir kuyruk
kullanır. Ağırlıksız graflarda en kısa yol bulmak için mükemmeldir. O(V + E)
zaman.
o Derinlik Öncelikli Arama (DFS): Her dalda mümkün olduğunca ilerler before geri
döner. Bir yığın kullanır (genellikle özyineleme yoluyla). Döngü tespiti, topolojik
sıralama ve bulmaca çözme için kullanışlıdır. O(V + E) zaman.
 En Kısa Yol:
o Dijkstra Algoritması: Negatif olmayan ağırlıklı bir grafta bir kaynak düğümden
tüm diğer düğümlere en kısa yolu bulur. Bir öncelik kuyruğu kullanır. O((V + E) log V)
zaman.
o Bellman-Ford Algoritması: Ağırlıklı bir grafta, negatif ağırlıklı kenarlar olsa bile
(ancak negatif döngüler olmasa) bir kaynak düğümden en kısa yolu bulur.
Dijkstra'dan daha yavaştır: O(V * E).
 Asgari Yayılan Ağaç (MST): Tüm köşeleri minimum toplam kenar ağırlığı ile
bağlayan bir kenar alt kümesi.
o Kruskal Algoritması: Tüm kenarları sıralar ve bir döngü oluşturmuyorsa (Union-
Find kullanarak) MST'ye ekler. O(E log V) zaman.
o Prim Algoritması: MST'yi bir seferde bir köşe büyütür, ağaca henüz dahil olmayan
bir köşeye ağaçtan en ucuz kenarı ekler. O(E log V) zaman.

Java Kodu Örneği: Ağırlıksız Grafta BFS ile En Kısa Yol

java
Copy
Download
import [Link].*;

public class GrafAlgoritmalari {

// Ağırlıksız grafta BFS ile en kısa yolu bulma

public static void bfsEnKisaYol(List<List<Integer>> graf, int baslangic, int hedef) {
int n = [Link]();
boolean[] ziyaretEdildi = new boolean[n];
int[] ebeveyn = new int[n]; // Yolu yeniden oluşturmak için
[Link](ebeveyn, -1);

Queue<Integer> kuyruk = new LinkedList<>();

[Link](baslangic);
ziyaretEdildi[baslangic] = true;

[Link]("BFS Dolaşma sırası:");

while (![Link]()) {
int mevcut = [Link]();
[Link](mevcut + " ");

// Hedef bulunduysa, erken çıkabiliriz

if (mevcut == hedef) {
break;
}

for (int komsu : [Link](mevcut)) {

if (!ziyaretEdildi[komsu]) {
ziyaretEdildi[komsu] = true;
ebeveyn[komsu] = mevcut; // Nereden geldiğimizi kaydet
[Link](komsu);
}
}
}
[Link]();

// En kısa yolu yeniden oluştur ve yazdır

 enKisaYoluYazdir(ebeveyn, baslangic, hedef);
}

private static void enKisaYoluYazdir(int[] ebeveyn, int baslangic, int hedef) {

if (ebeveyn[hedef] == -1 && baslangic != hedef) {
[Link](baslangic + " düğümünden " + hedef + " düğümüne bir yol
yok.");
return;
}
List<Integer> yol = new ArrayList<>();
for (int anlik = hedef; anlik != -1; anlik = ebeveyn[anlik]) {
[Link](anlik);
}
[Link](yol);
[Link](baslangic + " düğümünden " + hedef + " düğümüne en kısa yol:
" + yol);
}

public static void main(String[] args) {

// Komşuluk Listesi kullanarak graf temsili
int dugumSayisi = 6;
List<List<Integer>> graf = new ArrayList<>();
for (int i = 0; i < dugumSayisi; i++) {
[Link](new ArrayList<>());
}

// Kenarları ekle (yönsüz graf)

[Link](0).add(1);
[Link](0).add(2);
[Link](1).add(0);
[Link](1).add(3);
[Link](2).add(0);
[Link](2).add(3);
[Link](2).add(4);
[Link](3).add(1);
[Link](3).add(2);
[Link](3).add(5);
[Link](4).add(2);
[Link](4).add(5);
[Link](5).add(3);
[Link](5).add(4);

int baslangicDugumu = 0;
int hedefDugum = 5;
bfsEnKisaYol(graf, baslangicDugumu, hedefDugum);
}
}

6. Açgözlü Algoritmalar
Teorik Açıklama
 Bir açgözlü algoritma, çözümü parça parça oluşturur ve her aşamada en belirgin ve
anlık faydayı sunan bir sonraki parçayı seçer. Her seferinde yerel olarak en uygun
seçimi yapar ve küresel bir optimum bulmayı umar.

 Temel Özellik (Kleinberg & Tardos): Açgözlü algoritmalar genellikle optimizasyon

problemleri için kullanılır. Genellikle tasarlaması kolay ve verimlidir, ancak her
zaman küresel olarak en uygun çözümü sağlamazlar. Doğruluklarını
kanıtlamak çok önemlidir.
 Ne zaman çalışırlar? Açgözlü-seçim özelliği (küresel bir optimuma yerel bir
optimum seçilerek ulaşılabilir) ve optimal alt yapı sergileyen problemler için
çalışırlar.
 Klasik Örnekler:
o Huffman Kodlama: Kayıpsız veri sıkıştırma için.
o Dijkstra Algoritması: En kısa yollar için (mevcut bilinen en kısa mesafede
açgözlüdür).
o Kruskal'ın & Prim'in Algoritmaları: MST için.
o Kesirli Sırt Çantası: En yüksek değer/ağırlık oranına sahip öğeyi almanın optimal
olduğu durum.

Java Kodu Örneği: Huffman Kodlama (Bilgi Sıkıştırma)

Bu, veri sıkıştırma için klasik bir açgözlü algoritmadır.

java
Copy
Download
import [Link].*;

// Huffman Ağacı'ndaki bir düğüm

class HuffmanDugumu implements Comparable<HuffmanDugumu> {
char veri;
int frekans;
HuffmanDugumu sol, sag;

public HuffmanDugumu(char veri, int frekans) {

[Link] = veri;
[Link] = frekans;
[Link] = null;
[Link] = null;
}

@Override
public int compareTo(HuffmanDugumu digeri) {
return [Link] - [Link];
}
}

public class AcgozluAlgoritmalar {

public static void main(String[] args) {

String testString = "huffman coding example";
[Link]("Orijinal String: " + testString);

// Adım 1: Frekans haritasını oluştur

Map<Character, Integer> frekansHaritasi = new HashMap<>();
for (char c : [Link]()) {
[Link](c, [Link](c, 0) + 1);
}
 // Adım 2: Bir Öncelik Kuyruğu (Min-Heap) kullanarak Huffman Ağacı oluştur
PriorityQueue<HuffmanDugumu> pq = new PriorityQueue<>();
for (var entry : [Link]()) {
[Link](new HuffmanDugumu([Link](), [Link]()));
}

// Açgözlü adım: En küçük frekansa sahip iki düğümü tekrar tekrar birleştir
while ([Link]() > 1) {
HuffmanDugumu sol = [Link]();
HuffmanDugumu sag = [Link]();
HuffmanDugumu ebeveyn = new HuffmanDugumu('-', [Link] + [Link]);
[Link] = sol;
[Link] = sag;
[Link](ebeveyn);
}
HuffmanDugumu kok = [Link](); // Huffman Ağacı'nın kökü

// Adım 3: Ağacı dolaşarak Huffman Kodlarını oluştur

Map<Character, String> huffmanKodlari = new HashMap<>();
kodlariOlustur(kok, "", huffmanKodlari);

[Link]("\nHuffman Kodları:");
for (var entry : [Link]()) {
[Link]("'" + [Link]() + "' : " + [Link]());
}

// Adım 4: Orijinal string'i kodla

StringBuilder kodlanmisString = new StringBuilder();
for (char c : [Link]()) {
[Link]([Link](c));
}
[Link]("\nKodlanmış Bit Dizisi: " + kodlanmisString);

// Sıkıştırma oranını hesapla (basitleştirilmiş)

int orijinalBit = [Link]() * 8; // 8-bit ASCII varsayılıyor
int kodlanmisBit = [Link]();
double sikistirmaOrani = (1.0 - (double) kodlanmisBit / orijinalBit) * 100;
[Link]("Sıkıştırma, orijinal bit boyutunun %.2f%%'unu tasarruf etti%n",
sikistirmaOrani);
}

private static void kodlariOlustur(HuffmanDugumu dugum, String kod, Map<Character,

String> huffmanKodlari) {
if (dugum == null) return;
// Eğer yaprak düğümse, bir karakter içerir
if ([Link] == null && [Link] == null) {
[Link]([Link], [Link]() ? "0" : kod); // Tek karakter
durumunu ele al
}
kodlariOlustur([Link], kod + "0", huffmanKodlari);
kodlariOlustur([Link], kod + "1", huffmanKodlari);
}
}
 7. Bilgi Sıkıştırma Algoritmaları
Teorik Açıklama

Sıkıştırma algoritmaları, veriyi temsil etmek için gereken bit sayısını azaltır. Genel
olarak ikiye ayrılır:

 Kayıpsız Sıkıştırma: Orijinal veri, sıkıştırılmış veriden mükemmel şekilde yeniden

oluşturulabilir. Metin, kod ve belirli görüntü türleri (örneğin, PNG) için esastır.
o Run-Length Encoding (RLE): Aynı veri değerinin ardışık dizilerini (run) tek bir
değer ve bir sayı ile değiştirir.
o Huffman Kodlama (Açgözlü): Daha sık görülen karakterlerin daha kısa kodlara
sahip olduğu değişken uzunluklu kodlar kullanır.
o Lempel-Ziv-Welch (LZW): Sık oluşan desenlerin bir sözlüğünü oluşturur. GIF ve
PDF dosyalarında kullanılır.
 Kayıplı Sıkıştırma: Bazı bilgiler kalıcı olarak atılır, ancak ideal olarak kolayca
algılanamayacak bir şekilde. Görüntüler (JPEG), ses (MP3) ve video (MPEG) için
kullanılır.
o JPEG: Görüntü verilerini frekans bileşenlerine dönüştürmek için Ayrık Kosinüs
Dönüşümü (DCT) kullanır, daha sonra bu bileşenler nicemlenir (hassasiyeti azaltılır).
o MP3: İnsan kulağının algılama olasılığının daha düşük olduğu sesleri kaldırmak için
psikoakustik kullanır.

Java Kodu Örneği: Run-Length Encoding (RLE)

Basit ama etkili bir kayıpsız sıkıştırma yöntemi.

java
Copy
Download
public class BilgiSikistirma {

// Run-Length Encoding (Kayıpsız Sıkıştırma)

public static String runLengthKodla(String girdi) {
if (girdi == null || [Link]()) {
return "";
}
StringBuilder kodlanmis = new StringBuilder();
int sayac = 1;
for (int i = 1; i < [Link](); i++) {
if ([Link](i) == [Link](i - 1)) {
sayac++;
} else {
[Link]([Link](i - 1)).append(sayac);
sayac = 1; // Yeni karakter için sayacı sıfırla
}
}
// Son karakteri ve sayacını ekle
[Link]([Link]([Link]() - 1)).append(sayac);
return [Link]();
}

// Run-Length Decoding
public static String runLengthCoz(String kodlanmis) {
if (kodlanmis == null || [Link]()) {
return "";
}
 StringBuilder cozulmus = new StringBuilder();
// Kodlanmış string'in iyi biçimlendirildiği varsayılır: [char][count][char][count]...
for (int i = 0; i < [Link](); i += 2) {
char karakter = [Link](i);
int sayac = [Link]([Link](i + 1));
// Karakteri 'sayac' kez ekle
for (int j = 0; j < sayac; j++) {
[Link](karakter);
}
}
return [Link]();
}

public static void main(String[] args) {

String orijinalVeri = "AAAAAAABBBBBBCCCCDDDDAAA";
[Link]("Orijinal Veri: " + orijinalVeri);
[Link]("Orijinal Veri Boyutu: " + [Link]() + " karakter");

String sikistirilmisVeri = runLengthKodla(orijinalVeri);

[Link]("\nSıkıştırılmış Veri (RLE): " + sikistirilmisVeri);
[Link]("Sıkıştırılmış Veri Boyutu: " + [Link]() + "
karakter");

String cozulmusVeri = runLengthCoz(sikistirilmisVeri);

[Link]("\nÇözülmüş Veri: " + cozulmusVeri);
[Link]("Çözülmüş Veri Boyutu: " + [Link]() + " karakter");

// Kayıpsızlığı doğrula
boolean kayipsizMi = [Link](cozulmusVeri);
[Link]("\nKayıpsız Sıkıştırma Doğrulandı: " + kayipsizMi);

if (kayipsizMi) {
double sikistirmaOrani = (1.0 - (double) [Link]() /
[Link]()) * 100;
[Link]("Sıkıştırma, orijinal boyutun %.2f%%'unu tasarruf etti%n",
sikistirmaOrani);
}
}
}

Bu, belirtilen yedi konunun tümü için, atıfta bulunulan ders kitaplarının akademik
tarzında sunulan detaylı Türkçe açıklama ve kod örneklerini sonlandırmaktadır. Her
bölüm, kavramları pekiştirmek için teorik bir temel ve pratik bir Java uygulaması
sağlar.