(501435-3) Algorithms Analysis and Design

Homepage and Syllabus

Disclaimer

This is the best information available as of today, Tuesday Jan 18, 2022 at 8:00 a.m. KSA time. Changes will appear in this web page as the course progresses.

Meeting time and place

  • Section 7420:
    • Sunday 6:00 p.m. - 9:00 p.m. (in classroom 24103)

Instructor: Dr. Emad Alsuwat

Course Homepage: https://emadalsuwat.github.io/algorithms-Spring2022.html
Office: W101 CIT
Office hours: Sunday 10:00 a.m. - 12:00 p.m.
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:
    • Section 7420: TBD
  • Final Exam:
    • Section 7420: TBD

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 Feb 28, 2022
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 xx xx, 2022
Week 7 Heapsort Chapter 6, Appendix B.5 Homework 2 xx xx, 2022
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 xx xx, 2022
Week 10 Binary Search Trees Appendix B5.2, Chapter 12 - -
Week 11 Dynamic Programming Chapter 15 Homework 4 xx xx, 2022
Week 12 Graphs Theory Chapter 22 - -
Week 13 Shortest Paths Chapter 24 - -
Week 14 NP-Completeness
& Revision		 Chapter 34 - -