(501435-3) Algorithms Analysis and Design
Homepage and Syllabus
Disclaimer
This is the best information available as of today,
Tuesday December 1, 2020 at
2:14 p.m. KSA time. Changes will appear in this web page as the course progresses.
Meeting time and place
- Section 1646: Tuesday 8:00 a.m. - 9:00 a.m. and Thursday 8:00 a.m. - 10:00 a.m.
- Section 3172: Monday 9:00 a.m. - 11:00 a.m. and Thursday 11:00 a.m. - 12: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-Fall2020.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:
- Section 1646: Thursday November 22, 2020 - 9:00 a.m. - 10:00 a.m.
- Section 3172: Thursday November 26, 2020 - 9:30 a.m. - 10:30 a.m.
- Second Midterm:
- Section 1646: Thursday October 26, 2020 - 8:00 a.m. - 9:00 a.m.
- Section 3172: Monday October 26, 2020 - 11:00 a.m. - 12:00 p.m.
- Final Exam: TBD
- Section 1646:
- Section 3172:
Grading
- First Midterm: 15%
- Second Midterm: 15%
- Homework Assignments: 20%
- 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 |
Lecture 1 |
- |
- |
| Week 3 |
Recurrences |
Lecture 2 |
Homework 1 |
Oct 4, 2020 |
| Week 4 |
More on Recurrences
No class on the 2nd Lecture of the week
Saudi 90th National Day |
- |
- |
- |
| Week 5 |
Sorting – Part A & Part B |
Lecture 3
Lecture 4 |
- |
- |
| Week 6 |
Randomizing Quicksort |
Lecture 5 |
- |
- |
| Week 7 |
Heapsort |
Lecture 6 |
Homework 2 |
Oct 21, 2020 |
| Week 8 |
First Midterm Exam
The Exam will cover textbook chapters 2, 3, 4, 5, 6 and 7 |
- |
- |
- |
| Week 9 |
Linear Sorting |
Lecture 7 |
Homework 3 |
Oct 31, 2020 |
| Week 10 |
Binary Search Trees |
Lecture 10 |
- |
- |
| Week 11 |
Dynamic Programming |
Lecture 12 |
Homework 4 |
November 23, 2020 |
| Week 12 |
Graphs
Shortest Paths |
Lecture 13
Lecture 15 |
- |
- |
| Week 13 |
Midterm Exam II |
- |
- |
- |
| Week 14 |
NP-Completeness
+ Revision |
Lecture 16 |
- |
- |