(501435-3) Algorithms Analysis and Design
Homepage and Syllabus
Disclaimer
This is the best information available as of today,
Saturday August 28, 2021 at
4:30 a.m. KSA time. Changes will appear in this web page as the course progresses.
Meeting time and place
- Section 1646:
- Tuesday 2:00 p.m. - 4:00 p.m. (in classroom 31104)
- Thursday 2:00 p.m. - 3:00 p.m. (in classroom 29204)
Instructor: Dr. Emad Alsuwat
Course Homepage:
https://emadalsuwat.github.io/algorithms-Fall2021.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
- Midterm Exam:
- Final Exam:
Grading
- Midterm Exam: 20%
- Homework Assignments: 20%
- Participation and Quizzes: 20%
- 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 |
Oct 4, 2021 |
| Week 5 |
Sorting – Part A & Part B |
Chapter 2
Chapter 7 |
- |
- |
| Week 6 |
Randomizing Quicksort |
Appendices C.2&C.3, Chapters 5&7 |
Quiz 1 |
Oct 9, 2021 |
| Week 7 |
Heapsort |
Chapter 6, Appendix B.5 |
Homework 2 |
Nov 13, 2021 |
| Week 8 |
Midterm Exam
The Exam will cover textbook
chapters 2, 3, 4, 5, 6 and 7 |
- |
- |
- |
| Week 9 |
Linear Sorting |
Chapter 8 |
Homework 3 |
Nov 13, 2021 |
| Week 10 |
Binary Search Trees |
Appendix B5.2, Chapter 12 |
- |
- |
| Week 11 |
Dynamic Programming |
Chapter 15 |
Homework 4 |
November xx, 2021 |
| Week 12 |
Graphs Theory |
Chapter 22 |
- |
- |
| Week 13 |
Shortest Paths |
Chapter 24 |
- |
- |
| Week 14 |
NP-Completeness
& Revision |
Chapter 34 |
- |
- |