| Course Code |
CSC354 |
| Course Title |
Design & Analysis of Algorithms |
| Credit Hours |
3+0 |
| Prerequisites by Course(s) and Topics |
Data Structures and Algorithms |
| 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 |
Sadia Kousar |
| URL (if any) |
|
| Current Catalog Description |
|
| Textbook (or Laboratory Manual for Laboratory Courses) |
Introduction to Algorithms (3rd edition) by Thomas H. Corman, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein |
| Reference Material |
Algorithm Design, (1st edition, 2013/2014), Jon Kleinberg, Eva Tardos, 3. Algorithms, (4th edition, 2011), Robert Sedgewick, Kevin Wayne |
| Course Goals |
The course introduces students with the basic notions of the design of algorithms and the underlying data structures. Students will learn about several measures regarding the structure, complexity, and efficiency of algorithms. |
| Course Learning Outcomes (CLOs): |
| At the end of the course the students will be able to: | Domain | BT Level* |
|---|
| Apply common algorithmic techniques to standard computational problems |
C |
3 |
| Analyze computational complexity of common/standard algorithms |
C |
4 |
| Design new algorithms for different computational problems |
C |
5 |
| Construct proofs of correctness and time complexity of various algorithms |
C |
6 |
| * 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 |
Ch 1 : Introduction: What Is an Algorithm? The place of algorithms in computer science and our everyday world, Designing Techniques, Model of Computation. |
|
2 |
What kinds of problems are solved by algorithms? Examples of Algorithms Ch 2 : Getting Started Insertion Sort , Analysis of Insertion Sort: Best Case Analysis Worst Case Analysis |
| Week 2 |
3 |
Merge Sort Description of Merge Sort Examples of Merge Sort |
|
4 |
Performance of Merge Sort Analysis of Merge Sort |
| Week 3 |
5 |
Ch : 3 Growth of Function Asymptotic Notations: Big Oh |
|
6 |
Big Theta, Big Omega, Standard Notations and common functions Ch : 4 Recurrences Master Method Examples of Master Method |
| Week 4 |
7 |
Recursion Tree Method Examples, Ch : 6 Heap Sort Introduction to Heaps |
|
8 |
Substitution Method & Examples |
| Week 5 |
9 |
Maintaining the heap property Max-Heapify Procedure Analysis of Max-Heapify Procedure |
|
10 |
Build a heap (Build Max-Heap procedure) Analysis of Build Max-Heap procedure The Heap-Sort Algorithm, |
| Week 6 |
11 |
Ch: 7 Quick Sort Description of Quick Sort Examples |
|
12 |
Performance of Quick Sort Analysis of Quick Sort |
| Week 7 |
13 |
Ch:8 Sorting in Linear Time Counting Sort Analysis of Counting Sort |
|
14 |
Radix Sort & Analysis, Bucket Sort & Analysis |
| Week 8 |
1 hours |
Mid Term |
| Week 9 |
15 |
Ch : 15 Dynamic Programming Element of the dynamic programming |
|
16 |
Matrix Chain Multiplication |
| Week 10 |
17 |
Ch: 16 Greedy Algorithms Activity Selection Problem |
|
18 |
Element of the greedy strategy |
| Week 11 |
19 |
Greedy Vs Dynamic programming Knapsack Problem |
|
20 |
Huffman Trees and Codes |
| Week 12 |
21 |
Ch : 22 Elementary Graph Algorithms Representation of graph |
|
22 |
Breadth-First Search |
| Week 13 |
23 |
Ch : 23 Minimum Spanning Tree Growing a Minimum Spanning Tree |
|
24 |
Kruskal’s Algorithm Example |
| Week 14 |
25 |
Prim’s Algorithm Example |
|
26 |
Kruskal’s Algorithm Example |
| Week 15 |
27 |
Ch : 24 Single-Source Shortest Paths |
|
28 |
Single-Source Shortest Paths in DAG Dijkstra’s Algorithm |
| Week 16 |
29 |
Bellman-Ford Algorithm |
|
30 |
Floyd-Warshall Algorithm |
| Week 17 |
2 hours |
Final Term |
|
| Laboratory Projects/Experiments Done in the Course |
|
| Programming Assignments Done in the Course |
|
