Basic concepts of algorithms, problem-solving strategies, and algorithm efficiency.
Introduction to algorithm complexity.
Problem-solving examples.
Design & Analysis of Algorithm
Fee: 8,000 /- PKR (per-month)
Registration Fee: 1,000 /- PKR
(non-refundable)
- Duration: 4.5 Months
- Starting: 26 January 2026
- Mode: Physical
- Days: Fri and Sat
- Timing: 05:30 PM to 07:00 PM
- Location: ITU 6th Floor Arfa Tower
In Collaboration with Information Technology University (ITU)
Who can join this course?
If you're at the beginning of a BS degree in Computer Science, Software Engineering, Data Science, Machine Learning, or Artificial Intelligence at any university or affiliated college in Lahore or its vicinity, this is an excellent opportunity to build a strong foundation for your journey in this field.
About Course
The Analysis of Algorithms course is designed to deeply engage you with algorithmic problem-solving techniques and the formal analysis of algorithms, combined with detailed, intense, and complex assignments that challenge your understanding at every step. Beginning with the fundamentals of algorithmic thinking and loop invariants, the course progressively covers time complexity, recursion, and the divide-and-conquer approach through real-world examples like stock investment and various sorting algorithms. Advanced topics such as graph theory, dynamic programming, and randomized algorithms are also covered in depth, leading up to critical concepts like P vs NP problems and geometric algorithms. Alongside these rigorous topics, each section is accompanied by comprehensive tutorials that guide you through the complex assignments, ensuring you grasp both the theoretical and practical aspects of algorithm design and analysis. This course is perfect for those looking to master the intricacies of algorithms and computational efficiency.
Course Outline
Lecture 1: Algorithmic Problem solving and Analysis of Algorithms
Lecture 2: Loop Invariant and Iterative Code Correctness
Correctness of algorithms using loop invariants.
Example: Binary Search Overflow Handling.
Bubble Sort, Selection Sort, and Insertion Sort proofs using loop invariants.
Lecture 3: Time Complexity Notations
Big O, Big Omega, Little O, Big Theta.
Limit definitions, logarithmic functions.
Examples and proofs.
Lecture 4: Practical Time Complexity Analysis
Applying time complexity concepts to various algorithms.
Analyzing multiple problem sets for real-world relevance.
Lecture 5: Introduction to Recursion
Fibonacci Numbers and recursive formulations.
TriSum Series, Slow and Fast Power, Recursive Bubble Sort.
Lecture 6: Solving Recurrences and the Master Theorem
T(N) = aT(N/b) + Nc and its applications.
Examples of recursive algorithms.
Tower of Hanoi and QuickSort recurrences.
Lecture 7: Divide and Conquer – Stock Investment and Merge Sort
Maximum Contiguous Subarray Problem.
Iterative vs. Recursive Merge Sort.
Lecture 8: Sorting Lower Bounds & Karatsuba Algorithm
Karatsuba’s Multiplication Algorithm.
Lower bounds of sorting algorithms and their impact.
Lecture 9: QuickSort – Randomized and Deterministic
Partitioning techniques in QuickSort.
Randomized partitioning and finding the Kth smallest element.
Lecture 10: Pseudo Algorithms
Stable Count Sort, Radix Sort, Bucket Sort.
Applications in Range Searching, Skyline, and Closest Pair Problems.
Lecture 11: Introduction to Graphs
Graph terminology and representations (Adjacency Matrix, Adjacency List).
Depth-First Search (DFS) applications.
Lecture 12: DFS Applications in Directed Graphs
DFS edge classification.
Detecting strongly connected components using DFS.
Lecture 13: Topological Sorting and BFS
Topological sorting in directed acyclic graphs (DAGs).
Breadth-First Search (BFS) and its applications in shortest path algorithms.
Lecture 14: DFS, Strongly Connected Components & Heaps
Kosaraju’s Algorithm for SCCs.
Introduction to heaps and priority queues.
Lecture 15: Shortest Path Algorithms
Dijkstra and Bellman-Ford algorithms.
Handling negative weights and universal sink problems.
Lecture 16: Minimum Spanning Trees
Prim’s and Kruskal’s algorithms.
Applications of minimum spanning trees in real-world problems.
Lecture 17: Introduction to Dynamic Programming
Smart recursion and memoization techniques.
Examples: Catalan Numbers, Fibonacci sequences.
Lecture 18: Dynamic Programming II – Subarrays and Subsequences
Kadane’s Algorithm for Largest Sum Subarray.
Longest Increasing Subsequence and DAG representations.
Lecture 19: Rod Cutting Problem
Solving the Rod Cutting problem using top-down and bottom-up approaches.
Lecture 20: Dynamic Programming in Grid-Based Problems
Edit Distance, Longest Common Subsequence.
Efficient grid-based pathfinding with DP techniques.
Lecture 21: P vs NP and Introduction to Reductions
Understanding the P vs NP problem.
Basic reductions and examples from graph theory.
Lecture 22: P vs NP and Advanced Reductions
More on reductions and complexity classes.
Lecture 23: Geometric Algorithms
Sweep Line Algorithm and its applications.
Introduction to geometric problem-solving in computational geometry.
Lecture 24: Randomized Algorithms
Randomized QuickSort and its performance guarantees.
Applications of randomized algorithms in real-world problems.
Lecture 25: Number Theoretic Algorithms
Efficient algorithms for number theory problems.
Use cases in cryptography and computer security.