Discrete Structures: Basics of Counting: Solving Recurrence Relations(Common examples, The Master Theorem), Graphs and Trees(Spanning trees and forests, Traversal strategies). Algorithms and Complexity – Basic Analysis: Asymptotic analysis of complexity (upper and average bounds), Differences among best, average, and worst-case behaviors,Big O, little o, Ω (omega), and Θ (theta) notation, Standard complexity classes, Empirical measurements of performance, Time and space trade-offs in algorithms, Using recurrence relations to analyze recursive algorithms. Algorithms and Complexity – Algorithmic Strategies: Brute-force algorithms, Greedy algorithms, Divide-and-conquer, Backtracking, Branch-and-bound, Heuristics, Pattern matching and string/text algorithms, Numerical approximation algorithms. Algorithms and Complexity – Fundamental Algorithms: Simple numerical algorithms, Searching algorithms: sequential and binary search, Sorting algorithms, Quadratic (selection, insertion), $O(n \log n)$ (quicksort, heapsort, mergesort), Hash tables (including collision-avoidance strategies), Binary search trees, Graph algorithms: Representations (adjacency list, adjacency matrix), Depth-first and breadth-first traversals, Shortest-path algorithms (Dijkstra’s, Floyd’s), Transitive closure (Floyd’s algorithm), Minimum spanning trees (Prim’s, Kruskal’s). Algorithms and Complexity – Geometric Algorithms: Closest pair, Convex hull finding algorithms. Algorithms and Complexity – Advanced Analysis: Online and offline algorithms, P versus NP, Standard NP-complete problems.
- Teacher: Jean Bosco Musabe