|Subject Area||Applications and Foundations of Computer Science|
|Semester||Semester 4 – Spring|
This course offers an introduction to the Design and Analysis techniques of Algorithms. Covered topics: Design techniques (divide and conquer, dynamic programming, greedy algorithms). Worst, average, and amortized complexity. Graph Algorithms (storing and traversal, connected components, strongly connected components, bi-connectivity, MST, shortest paths, flows, matching). String algorithms. Competitive analysis and on-line algorithms. Numerical Algorithms and RSA. Introduction to Theory of Computation and NP-completeness. Approximation Algorithms. Heuristics for NPC problems.
The course introduces the fundamental principles of algorithm design and analysis while exhibits the key role of choosing the proper data structures to algorithm performance.
Upon successful completion of this course, the student will be able to:
- know, understand and apply fundamental algorithm design techniques (divide and conquer, dynamic programming, greediness)
- know to analyze algorithms and estimate their behavior in the worst, average and amortized case, using a pseudo-language
- understand how the application of proper data structures affects algorithm performance
- know how to apply basicgraph and string algorithms
- distinguish complexity classes and know heuristic techniques for NPC problems