(501435-3) Algorithms Analysis and Design
Homepage and Syllabus
Disclaimer
This is the best information available as of today,
Monday Jan 11, 2021 at
7:30 p.m. KSA time. Changes will appear in this web page as the course progresses.
Meeting time and place
- Section 5905: Monday 4:00 p.m. - 5:00 p.m. and Thursday 2:00 p.m. - 4:00 p.m.
- Due to COVID 19 pandemic, these classes will be conducted remotely and online via blackboard until further notice.
Instructor: Dr. Emad Alsuwat
Course Homepage:
https://emadalsuwat.github.io/algorithms-Spring2021.html
Office: W101 CIT
Office hours: Due to the COVID-19 pandemic restrictions, there will be no in-person office hours. Please email me if you have any question. If necessary, I will arrange a phone call or a virtual meeting
Phone: NA
Email: Alsuwat@tu.edu.sa
Course Overview
Algorithm is the central concept of Computer Science. This course provides introduction to algorithm design and analysis. Students study techniques for designing algorithms and for analyzing the time and space efficiency of algorithms. The algorithm design techniques include divide-and-conquer, greedy technique, dynamic programming, backtracking and branch and bound. The algorithm analysis includes computational models, computational complexity, and computation of best, average and worst case complexity. The course also includes study of limits of algorithmic methods (e.g. NP-hard, NP-complete problems).
Learning Outcomes
By the end of the course, students should be able to:
- Understand different algorithm design techniques
- Design an efficient algorithm for a given task using the most suitable design technique
- Understand major classical algorithms available for different tasks
- Analyze the algorithms for different problems
- differentiate between problems that can be solved by polynomial time
algorithm and problems for which no polynomial time algorithm is known
Textbook
- Required: Cormen, Leiserson, Rivest, Stein, Intro to
Algorithms, 3rd edition, McGraw Hill
Examinations
- First Midterm:
- Second Midterm:
- Final Exam: TBD
Grading
- Midterm Exam: 25%
- Homework Assignments: 25%
- Participation and Quizzes: 10%
- Final Exam: 40%
Topics to be covered
Below are roughly the sections of the CLRS book that I will cover. I
may de-emphasize some topics and add others, but this is basically the
list.
| Topic |
Text Reference |
| Summations |
CLRS Appendix A |
| Intro to Algorithms |
CLRS Ch 1 (brief) |
| Getting Started |
Ch 2 (brief) |
| Order of Growth/Asymptotics |
Ch 3 |
| Solving Recurrences |
Ch 4 |
| Heapsort and Randomized Quicksort |
from Ch 6 and Ch 7 |
| Lower Bounds for Sorting |
Ch 8 (Section 1 only) |
| Order Statistics |
Ch 9 |
| Counting and Probability |
Appendix C |
| Elementary Data Structures |
Ch 10 (brief) |
| Hash Tables (time permitting) |
Ch 11 (Sections 1 and 2 only) |
| Binary Search Trees |
Ch 12 (brief) |
| Red-Black Trees |
Ch 13 |
| Augmenting Data Structures |
Ch 14 (brief) |
| Dynamic Programming |
Ch 15 |
| Greedy Algorithms |
Ch 16 |
| Amortized Analysis |
Ch 17 |
| Mergeable Heaps: Fibonacci Heaps |
Ch 19 |
| Disjoint Sets |
Ch 21 (Section 3 only) |
| Elementary Graph Algorithms |
Ch 22 |
| Minimum Spanning Trees |
Ch 23 |
| Dijkstra's Algorithm |
Ch 24 Section 3 |
| Floyd-Warshall Algorithm (time permitting) |
Ch 25 Section 2 |
| Intro to NP-Completeness |
Ch 34 Sections 1 and 2 |
| Theory of NP-Completeness |
Ch 34 Section 3 |
Lecture Notes and Homework Assignments
Note that changes to the table below will appear week by week as the course progresses
| Week |
Topic |
Slides |
Assignment |
Due Date |
| Week 1 |
Syllabus Week |
- |
- |
- |
| Week 2 |
Asymptotic Analysis |
Chapter 3, Appendix A |
- |
- |
| Week 3 |
Recurrences |
Appendix A, Chapter 4 |
- |
- |
| Week 4 |
More on Recurrences |
Chapter 4 |
Homework 1 |
Feb 20, 2021 |
| Week 5 |
Sorting – Part A & Part B |
Chapter 2
Chapter 7 |
- |
- |
| Week 6 |
Randomizing Quicksort |
Appendices C.2&C.3, Chapters 5&7 |
- |
- |
| Week 7 |
Heapsort |
Chapter 6, Appendix B.5 |
Homework 2 |
March 25, 2021 |
| Week 8 |
First Midterm Exam
The Exam will cover textbook
chapters 2, 3, 4, 5, 6 and 7 |
- |
- |
- |
| Week 9 |
Linear Sorting |
Chapter 8 |
Homework 3 |
April 3, 2021 |
| Week 10 |
Binary Search Trees |
Appendix B5.2, Chapter 12 |
- |
- |
| Week 11 |
Dynamic Programming |
Chapter 15 |
Homework 4 |
April 8, 2021 |
| Week 12 |
Graphs
Shortest Paths |
Chapter 22
Chapter 24 |
- |
- |
| Week 13 |
Midterm Exam II |
- |
- |
- |
| Week 14 |
NP-Completeness
& Revision |
Chapter 34 |
- |
- |