UNIVERSITY OF ENGINEERING & APPLIED SCIENCE
(U-EAS), SWAT
Department of Computer Systems Engineering
Analysis of Algorithms
Course Code: Semester: 6th
Credit Hours: 3+0 Class:
Instructor: Email:
Office: Program: BS Artificial Intelligence
Course Description
This course provides BSc AI students with a comprehensive understanding of algorithm
analysis techniques, equipping them with the skills necessary to analyze and evaluate the
efficiency and performance of algorithms.
Course Objectives
The objectives of this course are to:
● Understand algorithm analysis techniques and their application in evaluating algorithm
efficiency.
● Demonstrate problem-solving skills through exposure to various algorithm design
techniques.
Course Learning Outcomes (CLOs) for BS Artificial Intelligence
At the end of the course the students will be able to: PLO Domain Taxonomy
Identify the efficiency of algorithms analysis
CLO 1 1 Cognitive C1
techniques and their application.
Classify algorithms using different algorithms
CLO 2 2 Cognitive C2
design techniques.
Apply proficiency in solving graph-related
CLO 3 problems. 3 Cognitive C3
Books
Text Book:
● Introduction to Algorithms (3rd edition) by Thomas H. Corman, Charles E. Leiserson,
Ronald L. Rivest and Clifford Stein
Reference Book:
● Algorithm Design, (1st edition, 2013/2014), Jon Kleinberg, Eva Tardos,
● Algorithms, (4th edition, 2011), Robert Sedgewick, Kevin Wayne
UNIVERSITY OF ENGINEERING & APPLIED SCIENCE
(U-EAS), SWAT
Department of Computer Systems Engineering
Course Weekly Distribution
Topic to be covered
Week#
1 -Introduction to algorithms and their role in computing
- Analysis on the nature of input and size of input
2 - Asymptotic notations: Big-O, Big Ω, Big Θ, little-o, little-ω
- Sorting algorithm analysis: Introduction and overview
3 - Sorting algorithm analysis: Merge sort
- Sorting algorithm analysis: Quick sort
4 - Recursion and recurrence relations: Introduction and concept of recursion
- Recursion and recurrence relations: Analyzing recursive algorithms
5 - Algorithm Design Techniques: Brute Force Approach
- Algorithm Design Techniques: Divide-and-conquer approach
6 - Greedy approach: Introduction and principles
- Dynamic programming: Introduction and elements
7 - Dynamic programming: Examples and applications
8 - Search trees: Introduction and basic operations
- Heaps: Introduction and heap operations
Mid Term Exam
10 - Hashing: Introduction and hash functions
- Hashing: Collision resolution techniques
11 - Graph algorithms: Introduction and traversing algorithms
- Graph algorithms: Shortest path algorithms
12 - Graph algorithms: Sparse graphs and their representation
- String matching algorithms: Introduction and brute force algorithm
13 - String matching algorithms: Knuth-Morris-Pratt (KMP) algorithm
- Introduction to complexity classes: Overview and P vs. NP
14 - Introduction to complexity classes: NP-hard problems
- Search algorithms
15 - Search algorithms: Binary Search Trees
- Search algorithms: Red-Black Trees
16 - Multithreaded Algorithms
17 - Matrix Operations
Final Term Exam
