MSCS: MCS 540 – Design and Analysis of Algorithms
Categories: MS in Computer Science
About Course
- This course provides an in-depth exploration of algorithm design and analysis, emphasizing efficient problem-solving techniques across various computational challenges.
- Students will study core algorithmic strategies, including sorting, searching, and graph algorithms, while also delving into complexity theory to understand the theoretical limits of computational efficiency.
- The course equips students with the skills necessary to analyze and implement algorithms that are both effective and efficient for a wide range of applications.
Course Objectives
- Develop an understanding of key algorithmic design techniques.
- Analyze the efficiency of algorithms using big-O notation and other complexity measures.
- Apply algorithmic strategies to solve problems in sorting, searching, and graph theory.
- Evaluate the complexity of problems and understand the theoretical limits of algorithmic approaches.
Course Content
Week 1: Introduction to Algorithm Design
-
Week 1: Introduction to Algorithm Design
03:43 -
LO1: Define the fundamental concepts of Algorithms and their importance in Computational Problem-solving
09:40 -
LO2: Explain examples of Algorithmic approaches to everyday Computational challenges
08:41 -
LO3: Discuss the role of Algorithm Design in ensuring efficiency and scalability of Software Systems
10:57 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Key Terms and Concepts Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
Week 2: Asymptotic Notation and Analysis
-
Week 2: Asymptotic Notation and Analysis
03:44 -
LO1: Describe Big-O, Big-Omega, and Big-Theta notations and their applications in Algorithm Analysis
12:28 -
LO2: Apply Asymptotic notation to compare the efficiency of common Algorithms
11:17 -
LO3: Evaluate Algorithmic performance by interpreting Time and Space Complexity
13:13 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Key Terms and Concepts Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
Week 3: Divide and Conquer Algorithms
-
Week 3: Divide and Conquer Algorithms
03:48 -
LO1: Explain the Divide and Conquer Technique and its theoretical basis
11:44 -
LO2: Analyse the performance of Divide and Conquer Algorithms
12:25 -
LO3: Design Algorithms using Divide and Conquer
09:30 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Key Terms and Concepts Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
Week 4: Dynamic Programming
-
Week 4: Dynamic Programming
03:13 -
LO1: Define Dynamic programming and explain how it differs from Divide and Conquer
11:40 -
LO2: Solve Optimisation problems using Dynamic Programming
09:30 -
LO3: Evaluate the efficiency of Dynamic programming solutions
10:09 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Key Terms and Concepts Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
Week 5: Greedy Algorithms
-
Week 5: Greedy Algorithms
03:39 -
LO1: Explain the Greedy strategy and its key Decision-making Principles
10:44 -
LO2: Apply greedy Algorithms to solve problems such as Activity Selection and Huffman Coding
10:19 -
LO3: Discuss when greedy Algorithms yield optimal solutions versus when they fail
10:27 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Key Terms and Concepts Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
Week 6: Graph Algorithms
-
Week 6: Graph Algorithms
02:54 -
LO1: Describe fundamental Graph Traversal Methods
09:57 -
LO2: Implement DFS and BFS to solve Graph-related problems
10:12 -
LO3: Analyze the efficiency and applications of Graph Traversal in Real-world scenarios
10:55 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Key Terms and Concepts Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
Week 7: Shortest Path and Minimum Spanning Tree Algorithms
-
Week 7: Shortest Path and Minimum Spanning Tree Algorithms
03:27 -
LO1: Explain Algorithms for shortest path and Minimum Spanning Trees
09:31 -
LO2: Apply Algorithms to Weighted Graph problems
10:03 -
LO3: Compare the Time Complexity and suitability of Shortest path and Spanning tree Algorithms
08:30 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Key Terms and Concepts Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
Week 8: Mid Term
-
Week 8: Mid Term
08:11 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Short Answer Questions
Week 9: Advanced Topics in Graph Algorithms
-
Week 9: Advanced Topics in Graph Algorithms
03:38 -
LO1: Define advanced Graph problems such as Network Flows and Bipartite Matching
10:30 -
LO2: Apply Algorithms for solving Flow and Matching problems
11:25 -
LO3: Analyse recent advancements in graph Algorithms
10:17 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Key Terms and Concepts Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
Week 10: NP-Completeness and Computational Complexity
-
Week 10: NP-Completeness and Computational Complexity
03:26 -
LO1: Describe the concepts of NP, NP-completeness, and Reducibility
10:24 -
LO2: Classify computational problems based on Complexity classes
09:21 -
LO3: Evaluate famous NP-complete problems and their significance in Algorithmic Research
10:58 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Key Terms and Concepts Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
Week 11: Approximation Algorithms
-
Week 11: Approximation Algorithms
03:42 -
LO1: Explain the design principles of Approximation Algorithms
00:00 -
LO2: Apply Approximation Algorithms to solve Computationally Hard Problems
00:00 -
LO3: Evaluate the accuracy and efficiency of Approximation Strategies
00:00 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Key Terms and Concepts Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
Week 12: Randomised Algorithms
-
Week 12: Randomised Algorithms
00:00 -
LO1: Define Randomized Algorithms and explain their role in Computational Efficiency
00:00 -
LO2: Implement examples such as Randomized Quicksort and Hashing
00:00 -
LO3: Analyse the Probabilistic behaviour and expected performance of Randomized Algorithms
00:00 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Key Terms and Concepts Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
Week 13: Parallel Algorithms
-
Week 13: Parallel Algorithms
00:00 -
LO1: Describe the basics of Parallel Computation and its advantages
00:00 -
LO2: Implement Parallel Algorithms for problems like Sorting and Searching
00:00 -
LO3: Evaluate the performance Trade-offs between Parallel and Sequential Algorithms
00:00 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Key Terms and Concepts Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
Week 14: Algorithmic Game Theory
-
Week 14: Algorithmic Game Theory
00:00 -
LO1: Explain the Intersection of Algorithms and Game Theory
00:00 -
LO2: Analyze Computational Complexity in Game-theoretic contexts
00:00 -
LO3: Apply Algorithmic principles to model and evaluate strategic Decision-making problems
00:00 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Key Terms and Concepts Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
Week 15: Review and Open Problems in Algorithms
-
Week 15: Review and Open Problems in Algorithms
00:00 -
LO1: Summarise the key Algorithmic strategies studied throughout the course
-
LO2: Evaluate unresolved Research challenges in Algorithm Design
00:00 -
LO3: Integrate knowledge of Algorithms to propose solutions for emerging Computational problems
00:00 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Key Terms and Concepts Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
Week 16: Final Exam
-
Week 16: Final Exam
00:00 -
Multiple Choice Questions
-
True/False Questions
-
Scenario-Based Multiple Choice Questions
-
Key Terms and Concepts Questions
-
Short Answer Questions
-
Written Assignment
-
Presentation Task
-
Role-Playing Activity
-
Peer Review Task
-
Exercises and Activities Adaptation
