- Elementary Concepts in the Design and Analysis of Algorithms
The concept of algorithm, applications and importance of algorithms. The concept of efficiency, a model for measuring efficiency, methods for analyzing the complexity of algorithms, technological importance of efficient algorithms.
- Basic Concepts in the Analysis and Complexity of Algorithms
Efficiency and time complexity, optimal algorithms, methods in analyzing the complexity of algorithms, asymptotic complexity, correctness of algorithms.
- Elementary Algorithms and Data Structures
Arrays, lists, stacks, queues, trees. Algorithms for finding the minimum or maximum in a set of elements. Algorithms for merging sorted lists, insertion sort, binary search, counting element tuples. Heap, priority queues, and their application in sorting (heapsort).
- Stable Matching
Problem formulation and applications. The propose-and-reject algorithm. Correctness and complexity analysis of the algorithm. Efficient implementation of the algorithm.
- The Divide-and-Conquer Technique
Generic description of the divide-and-conquer technique. The merge-sort algorithm. The algorithm for counting inversions. Recurrence relations and methods for their solution.
- Graphs and Graph Algorithms
Graphs as fundamental model of networks and systems. Basic properties and features of graphs. Graph connectivity. Graph traversal and searching algorithms: breadth-first-search (BFS), depth-first-search (DFS). Extensions/applications of BFS and DFS for computing connected components, topological sorting, strongly connected components, and for checking graph bipartiteness.
- The Greed Technique
Generic description of the greed technique. Scheduling algorithms: interval scheduling, scheduling all intervals, scheduling to minimize lateness. Network optimization algorithms: minimum spanning tree (Kruskal’s and Prim’s algorithms), shortest paths (Dijkstra’s algorithms). Efficient implementation of network optimization algorithms.
- The Dynamic Programming Technique
Generic description of the dynamic programming technique. Efficient application and implementation of dynamic programming. Algorithms for weighted interval scheduling and knapsack problems.