Algorithms Analysis and Design

Learning Outcomes

The course covers the fundamentals of algorithm design and analysis while showing the criticality of choosing appropriate data structures for solution efficiency.

Upon successful completion of the course, the student will be able to:

• Know, understand, and apply fundamental algorithm design techniques (divide and conquer, dynamic programming, greed).
• Know how to analyze algorithms and evaluate their behavior in the worst, average and partitioned case, expressing them in a pseudo-language.
• Understand how implementing appropriate data structures affects algorithm performance.
• Know how to implement basic algorithms involving graphs and strings.
• Distinguish between complexity classes and know heuristic techniques for solving NPC problems.

Indicative Module Content

• Introduction to asymptotic assessments, worst, average and shared case performance
• Brute-Force Algorithms
• Recursive algorithms
• Divide and Conquer Algorithms
• Dynamic Programming
• Greedy algorithms
• Backtracking algorithms
• Binary search trees
• Graph algorithms (Dijkstra, DFS, BFS)
• Hashing table
• Classes: P, NP, NP complete, NP hard