SEN2212 · Veri Yapıları ve Algoritmalar II

Data Structures and Algorithms II

Trees, BST, AVL, heaps, hashing, graphs and greedy algorithms.

Textbook: Data Structures & Problem Solving Using Java (Mark Allen Weiss)

Week 1
Introduction and Sorting Algorithms.
- Sorting algorithms: analysis, lower bound, counting and radix sortStep-by-step traces and Big-O analysis of merge sort, quicksort and heapsort, the n log n lower bound for comparison-based sorting, and the non-comparison counting and radix sorts.
Week 2
Introduction to different tree structures.
- Trees: terminology, binary trees and traversalsTerms such as root, leaf, depth and height, general and binary trees, preorder/inorder/postorder/level-order traces, and expression trees.
Week 3
Introduction to binary search trees.
- Binary search trees: search, insert, deleteThe BST property, the search path, how insertion order determines the shape of the tree, the three cases of deletion, the inorder successor and height analysis.
Week 4
Implementing binary search tree using Java.
- Writing a BST in JavaA generic BinarySearchTree class: the node class, recursive insert/remove/contains/findMin/findMax, traversals, size and height; the 'write a method' patterns asked in exams.
Week 5
Introduction to balanced trees and implementing AVL balanced tree structure using Java.
- AVL trees: balance factor and rotationsThe AVL rule that keeps a BST at O(log n), the LL/RR/LR/RL rotations, and the classic exam question: what does the tree look like after inserting in this order?
Week 6
Using other balanced tree structure using Java.
- Other balanced trees: red-black, 2-3, B-tree, splayThe five rules of a red-black tree and its insertion cases, splitting in 2-3 trees, the role of B-trees on disk and the splay idea. Drawing a colored tree and tracing splits are the exam questions from here.
Week 7
Using heap structure and implementing them using Java.
- Binary heap: array representation, percolate, buildHeap, heapsortHow a binary heap is stored in an array, traces of insert (percolate up) and deleteMin (percolate down), O(n) buildHeap and heapsort. The classic exam question: what does the array look like after these operations?
Week 8
Using heaps as priority queues. Midterm.
- Priority queue: PriorityQueue with a heapUsing a binary heap as a priority queue, Java's PriorityQueue class, ordering with a Comparator, k-smallest, merging k lists, and job scheduling applications.
- Midterm review: sorting, trees, BST, AVL, heapA one-page summary of weeks 1-8: the Big-O table, the tracing pattern for each topic and mixed midterm questions.
Week 9
Analyzing and implementing hashing algorithms.
- Hashing: chaining, open addressing and rehashingThe hash function, load factor, separate chaining, linear/quadratic probing, double hashing, lazy deletion and rehashing; step-by-step solutions to the classic 'fill in the table' exam questions.
Week 10
Analyzing and implementing graph structure using Java.
- Graphs: representation, BFS, DFS and topological sortStoring a graph with an adjacency matrix and list, traversing with BFS and DFS, counting connected components and ordering a DAG topologically; the rules behind the exam's 'write the visit order' questions.
Week 11
Analyzing and implementing graph algorithms.
- Shortest path and cycle detection: BFS, Dijkstra, Bellman-FordShortest paths with BFS in an unweighted graph, with Dijkstra for positive weights, with Bellman-Ford for negative edges; finding cycles in directed and undirected graphs. The exam's table-filling questions come from here.
Week 12
Analyzing and implementing greedy algorithms.
- Greedy algorithms: activity selection, fractional knapsack, coin changeThe greedy idea, when it gives the correct result and when it breaks. Activity selection, fractional and 0/1 knapsack, and coin change examples with their counterexamples.
- Huffman coding: building the tree, codes, total bitsBuilding a Huffman tree by merging the two smallest frequencies, reading codes from the tree, computing total bits and the average, and decoding. A tracing question that appears in the exam almost every term.
Week 13
Analyzing and implementing greedy algorithms. Quiz.
- Minimum spanning tree: Prim, Kruskal and union-findThe tree that connects all vertices of a weighted undirected graph at the lowest cost. You learn to trace Kruskal with union-find and Prim with a step table, and to solve quiz-style questions.
Week 14
Review.
- Final review: which structure, which algorithm, which Big-OThe whole term on one page: a table for choosing a structure/algorithm by problem type, a Big-O summary of all operations and one mixed final question from each topic.