| Course Code |
CSC |
| Course Title |
Advanvce Algorithm Analysis |
| Credit Hours |
3+0 |
| Prerequisites by Course(s) and Topics |
|
| Assessment Instruments with Weights (homework, quizzes, midterms, final, programming assignments, lab work, etc.) |
SESSIONAL (Quizzes, Assignments, Presentations) =25 %
Midterm Exam =25 %
Final Exam = 50%
|
| Course Coordinator |
Dr. Tahir Alyas |
| URL (if any) |
|
| Current Catalog Description |
|
| Textbook (or Laboratory Manual for Laboratory Courses) |
|
| Reference Material |
|
| Course Goals |
The course goal of "Advance Analysis of Algorithm" is to enable students to develop a deep understanding of advanced algorithms and their analysis techniques. The course aims to build on the foundational knowledge of algorithms and data structures acquired in earlier courses and provide students with the ability to analyze and design more complex algorithms for a wide range of computational problems. Through this course, students will learn how to apply various techniques for algorithm analysis, such as asymptotic analysis, recurrence relations, and amortized analysis. They will also gain an understanding of important algorithm design paradigms, such as divide and conquer, dynamic programming, and greedy algorithms, and learn how to apply them to solve real-world problems. The course will also cover advanced topics in algorithm analysis, such as randomized algorithms, graph algorithms, and network flow algorithms. Students will learn how to analyze the efficiency and correctness of these algorithms and apply them to solve complex problems in various domains, including computer science, engineering, natural sciences, and social sciences. Overall, the course goal is to equip students with the knowledge and skills necessary to analyze and design advanced algorithms and enable them to apply this knowledge to solve complex computational problems in a wide range of domains. |
| Course Learning Outcomes (CLOs): |
| At the end of the course the students will be able to: | Domain | BT Level* |
|---|
| Students should develop a sound theoretical understanding of advanced algorithms and practical problem solving skills using them. |
BT |
1 |
| Analyze average and worst-case running times of given algorithm. |
BT |
1 |
| Students should gain a good understanding on a wide range of advanced algorithmic problems, their relations and variants, and application to real-world problems |
BT |
2 |
| Analyze and design algorithms on further advanced topics such as computational geometry, operations research, cryptography, number theoretic, algorithms etc. |
BT |
1 |
| * BT= Bloom’s Taxonomy, C=Cognitive domain, P=Psychomotor domain, A= Affective domain |
|
|
|
| Topics Covered in the Course, with Number of Lectures on Each Topic (assume 15-week instruction and one-hour lectures) |
| Week | Lecture | Topics Covered |
|---|
| Week 1 |
1 |
Introduction to course |
|
2 |
Logic and Proving Techniques |
| Week 2 |
3 |
Asymptotic order of growth |
|
4 |
Recursive Exponentiation |
| Week 3 |
5 |
Sorting Algorithm: Brute Force Approach |
|
6 |
Design of Algorithms using Brute Force Approach |
| Week 4 |
7 |
Designing Algorithms using Divide-and-Conquer Multiplication, recurrence relations |
|
8 |
Generating Permutations, 0-1 Knapsack Algorithm Analysis |
| Week 5 |
9 |
Greedy Algorithms: Analysis of Merge-sort and Quick Sort Algorithm |
|
10 |
Substitution Method, Recursion-Tree Method, Master Therom |
| Week 6 |
11 |
Dynamic Programming |
|
12 |
Dynamic Programming for Solving Optimization Problems |
| Week 7 |
13 |
Linear Vs Non-linear Data Structures |
|
14 |
Matrix Chain Multiplication Problem |
| Week 8 |
1 hours |
Mid Term |
| Week 9 |
15 |
Graph Theory and Types of Graphs |
|
16 |
BFS and DFS |
| Week 10 |
17 |
Breadth-first search, Dijkstra’s algorithm, |
|
18 |
Greedy Algorithms |
| Week 11 |
19 |
Minimum spanning trees, Huffman encoding, |
|
20 |
Horn formulas, |
| Week 12 |
21 |
set cover (approximation algorithm) |
|
22 |
Dynamic Programming |
| Week 13 |
23 |
Shortest paths in DAGs (revisited), |
|
24 |
longest increasing subsequence |
| Week 14 |
25 |
edit distance, knapsack problem |
|
26 |
Complexity Theory |
| Week 15 |
27 |
Turing machine |
|
28 |
P and NP, undecidability |
| Week 16 |
29 |
Halting problem |
|
30 |
|
| Week 17 |
2 hours |
Final Term |
|
| Laboratory Projects/Experiments Done in the Course |
|
| Programming Assignments Done in the Course |
|
