Iqra University Islamabad Campus

Faculty of Computer Science & Information Technology

Course Outline
Course Course Design and Analysis of Algorithm
Information Title
Course ID CSC441 / CSC332 Course Type Core
Credit 3 Hours per week (C-L) 3-0
hours
Programs BS (CS), BS(AI) Preferred Semester 5
Date 17-03-2025 Version 1.0
Instructor Ms. Affefah Qureshi TA / Lab Engineer N-A
Course The objective of this course is to study paradigms and approaches used to analyze and design algorithms
Objective(s) and to appreciate the impact of algorithm design in practice. It also ensures that students understand how
the worst-case time complexity of an algorithm is defined, how asymptotic notation is used to provide a
rough classification of algorithms, how a number of algorithms for fundamental problems in computer
science and engineering work and compare with one another, and how there are still some problems for
which it is unknown whether there exist efficient algorithms, and how to design efficient algorithms.
Course At the end of this course students will be able to;
Learning CLO’s Outcome Relation of CLO
Outcomes with GA
(CLO) and CLO 1 Understand of the behavior and time and space complexity of simple C2 GA 2
Mapping algorithms using big O, Omega, and Theta notation
with CLO 2 Analyze problem class and investigate its solution via suitable C4 GA 3
Graduate algorithms
Attributes CLO 3 Design and Develop strategies to solve a problem by mapping from C6 GA 4
(GAs) similar ‘known’ problems
Lecture type Classroom Lectures, Presentations
Textbook Title Edition Authors Publisher Year ISBN
Introduction to Algorithms 4th Thomas H. The MIT 2022 978-0-26-204630-5
Cormen Press
References Design and Analysis of Algorithms 3rd Anany Levitin Pearson 978-0-13-231681-1
Assessment Assessment Weight Used to attain Assessment Weight Used to attain
Criteria CLO CLO
(100%) Assignment 10% CLO1 - CLO3 Quiz 10% CLO1 - CLO3
Lab 0% Project / 10% CLO3
Presentation
Mid Term 30% CLO1, CLO2 Final 40% CLO1 - CLO3
Methods of Assignments, Quizzes, Presentations, Midterm Exam and Final Term Exam.
Evaluation
Notes -
Assessment Assessment Goal
Goal Assignment Logically think and develop problem solving skills.
Achievement Quiz Revision of concepts
Project/Presentation Team work, Technical Skills
Exam Evaluates student’s ability to evaluate the performance of algorithms in terms of time and
space complexities.
Assesses student’s ability to apply their knowledge of algorithm design and analysis to solve
common computational problems.

Week Lecture Relation with

Topic Lecture Contents
No. No. CLO
− Introduction to Analysis of Algorithms
L1.
W1. Algorithm Overview − Revision of Data structure, Growth of Function CLO1
L2. − summation and its properties, related examples

Page 1 of 3
 − Algorithm Complexity calculation for polynomial non-polynomial
L3. time solvable problems;
Algorithm
W2. − Calculating best case and worst case complexity of an Iterative CLO1, CLO2
Complexity
Algorithm e.g. Insertion Sort.
L4.
− Calculating complexity of a Recursive Algorithm e.g. Merge Sort
− Asymptotic Notations and Basic Efficiency Classes, big theta, big O,
L5. and big Omega,
Asymptotic
W3. − Lower bound and upper bound Some, related examples of lower CLO3
Notations
L6. and upper bounds sic
− Efficiency Classes, big theta, big O, and big Omega,
− Greedy Algorithms Coin Changing,
L7.
W4. Greedy Algorithms − Huffman’s Algorithm, Interval Scheduling, Interval Partitioning, CLO2
L8. − Scheduling to minimize Lateness, Optimal Caching
− Divide and Conquer Problems, Matrix Multiplications, Examples and
L9. properties of summations;
Iterative and
− Recurrence relations and recursive algorithms, construction of
W5. Recursive method CLO3
general recursive based algorithms,
L10. − analysis of recursive algorithms using the stack, analysis time and
space complexity
L11. − Divide and Conquer Problems (continued)
− Some related examples, factorial, Fibonacci series, construction of
W6. Sorting Techniques CLO3
L12. recursion tree; Quick Sort;
− Decision Tree, Radix Sort
− Dynamic programming, Concept of overlapping sub-problem.
Dynamic L13. − Weighted Interval Scheduling, Longest Common Sub-sequence,
W7. CLO2,CLO3
Programming Maximum Subarray problem,
L14. − Project / CCP Discussion and Group allocation

W8. Mid Term Examination

− Dynamic Programming (contd). Floyd-Warshall’s algorithm for all
L15.
Shortest Path pairs shortest path algorithms;
W9. CLO2
Algorithms − Weighted KnapSack Problem, Longest Common Sub sequence,
L16.
− Bellman Ford, Distance Vector Algorithms

L17. − Graph algorithms; Basic understanding the graph and trees,

− Decrease and conquer based algorithms, construction of depth-first
CLO1, CLO2,
W10. Graph search and breadth-first search;
CLO3
L18. − Space and time complexity analysis of depth-first search and
breadth-first search, Matching in Bipartite graphs

L19. − Construction of heap tree, heap-sort algorithm;

W11. Heap − Maintaining the heap property, max-heapify, CLO2,CLO3
L20. − building heap, analysis of time and space

− Topological sort, construction and time complexity;

L21. − Greedy algorithms: Minimum spanning trees MST, purpose
CLO1,
W12. MST − and advantages of MST,
CLO2,CLO3
L22. − construction by using Prim’s and Kruskal's Algorithm, time and
space analysis, MST construction by Prim’s algorithm;
L23. − Single source shortest path algorithm,
Single Source
W13. − Dijkstra’s algorithm, space and time analysis, CLO1, CLO3
Shortest Path
L24. − Ford-Fulkerson Algorithm
 L25. − Bellman Ford Algorithm
Single Source
− Examples
W14. Shortest Path CLO2, CLO3
L26. − Travelling Salesman Problem
− Examples

L27. − NP and Computational Intractability,

W15. NP –Hard Problems − Sequencing, Partitioning, CLO1, CLO3
L28. − Graph coloring, Numerical Problems,
Presentations \
W16. − Presentations \ Project
Project
W17. Final Exams