(5018101-3) Algorithms Analysis and Design

Homepage and Syllabus

Disclaimer

This is the best information available as of today, Tuesday Sept 3, 2024 at 7:00 p.m. KSA time. Changes will appear in this web page as the course progresses.

Meeting time and place

  • Section 4823:
    • Wednesday 12:00 p.m. - 3:00 p.m. (via Blackboard)

Instructor: Dr. Emad Alsuwat

Course Homepage: https://emadalsuwat.github.io/algorithms-Fall2024.html
Office: W101 CIT
Office hours: Thursday 10:00 a.m. - 2: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, Introduction to Algorithms, 3rd edition, McGraw Hill

Examinations

  • Midterm Exam:
    • Section 4823: TBD
  • Final Exam:
    • Section 4823: 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/ Date Topic Slides Assignment Due Date
Week 1
8/18/24		 Syllabus Week - - -
Week 2
8/25/24		 Asymptotic Analysis Chapter 3, Appendix A - -
Week 3
9/1/24		 Recurrences Appendix A, Chapter 4 - -
Week 4
9/8/24		 More on Recurrences Chapter 4 Homework 1 xxx xx, xxxx
Reading only Sorting Chapter 2 - -
Week 6
9/15/24		 Quicksort &
Randomizing Quicksort 		Chapter 7
Appendices C.2&C.3, Chapters 5&7 		- -
Week 7
9/22/24		 Heapsort Chapter 6, Appendix B.5 Homework 2 xx xx, xxxx
Week 8
9/29/24		 Linear Sorting Chapter 8 Homework 3 xx xx, xxxx
Week 9
10/6/24		 Binary Search Trees Appendix B5.2, Chapter 12 - -
Week 11
10/13/24		 Red-Black Trees Chapter 14 - -
Week 9
10/20/24		 Midterm Exam
The Exam will cover textbook
chapters 2 - 8, 12, and 14 		- - Oct 23, 2024
Week 12
10/27/24		 Dynamic Programming Chapter 15 - -
Week 13
11/3/24		 More on
Dynamic Programming 		Chapter 15 Homework 4 xx xx, xxxx
Week 14
11/10/24		 Mid-Semester Break - - -
Week 15
11/17/24		 Graphs Theory Chapter 22 - -
Week 15
11/24/24		 Shortest Paths Chapter 24 - -
Week 16
12/1/24		 NP-Completeness Chapter 34 - -
Week 17
12/8/24		 Revision - - -
Weeks 18 - 20
12/8-26/24 		Final Exams - - -