Compiti ed esercitazioni VERIFICATO
Eserciziario
15 visualizzazioni
25 download
Nessun voto ancora
Di cosa parla
This study material presents a series of exercises and detailed solutions covering core topics in algorithms and data structures. It aims to deepen understanding through practical applications.
- Algorithm Correctness: Explores formal proofs using mathematical induction and loop invariants for algorithms like squaring a number, fast exponentiation (recursive and iterative), linear search, and binary search.
- Sorting Algorithms: Analyzes quadratic-time sorting methods such as Insertion Sort and Selection Sort, evaluating their best-case, worst-case complexities, and performance metrics like comparisons and swaps.
- Asymptotic Growth: Discusses Big-O, Omega, and Theta notations, including proofs for various function relationships and properties, and the implications for algorithm efficiency.
- Recurrence Relations: Provides solutions for common recurrence relations using techniques like iteration, master theorem, and variable substitution, including
T(n) = T(n/2) + nandT(n) = T(√n) + 1. - Algorithm Analysis: Deconstructs the time complexity of various algorithms, including polynomial evaluation (Horner's rule), finding maximum consecutive odd numbers, and permutation generation.
- Lists and Hash Tables: Covers operations on linked lists such as finding duplicates, ranking elements, reversing, and palindrome checks. It also details hash table implementations with linear and quadratic probing, demonstrating insertion processes and collision handling.
- Trees: Explores different tree structures including k-ary trees, binary search trees (BSTs), and heaps. Exercises involve verifying tree properties (e.g., parent-child sum, completeness, BST property), adding nodes, finding common ancestors, and analyzing heap extractions.
- Graphs: Features fundamental graph algorithms like Breadth-First Search (BFS) for traversal and component analysis, Dijkstra's algorithm for single-source shortest paths (with priority queue explanations), algorithms for detecting bipartite graphs, and checking for acyclicity in directed graphs using Depth-First Search (DFS).