Introduction to Algorithms

Course Code: 
Credit Points: 

Course Outline

  1. 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.

  1. 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.

  1. 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).

  1. Stable Matching

Problem formulation and applications. The propose-and-reject algorithm. Correctness and complexity analysis of the algorithm. Efficient implementation of the algorithm.

  1. 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.

  1. 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.

  1. 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.

  1. 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.

Startup Growth Lite is a free theme, contributed to the Drupal Community by More than Themes.