(501435-3) Algorithms Analysis and Design

Homepage and Syllabus

Disclaimer

This is the best information available as of today, Saturday Aug 26, 2023 at 7:00 p.m. KSA time. Changes will appear in this web page as the course progresses.

Meeting time and place

  • Section 634:
    • Sunday 5:00 p.m. - 8:00 p.m. (in classroom 31106)
  • Section 647:
    • Monday 2:00 p.m. - 5:00 p.m. (in classroom 29102)

Instructor: Dr. Emad Alsuwat

Course Homepage: https://emadalsuwat.github.io/algorithms-Fall2023.html
Office: W101 CIT
Office hours: Monday 5:00 a.m. - 8: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 634: Oct 15, 2023
    • Section 647 : Oct 16, 2023
  • Final Exam:
    • Section 634: TBD
    • Section 647 : TBD

Grading

  • Midterm Exam: 25%
  • Homework Assignments: 20%
  • Participation and Quizzes: 10%
  • Final Exam: 45%

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 - -
Week 5 More on Recurrences Chapter 4 Homework 1 Oct 7, 2023
Reading only Sorting Chapter 2 - -
Week 6 Quicksort &
Randomizing Quicksort 		Chapter 7
Appendices C.2&C.3, Chapters 5&7 		- -
Week 7 Heapsort Chapter 6, Appendix B.5 Homework 2 xx xx, 2023
Week 8 Linear Sorting Chapter 8 Homework 3 xx xx, 2023
Week 9 Midterm Exam
The Exam will cover textbook
chapters 2, 4, 5, 6, 7, and 8 		- - Oct 15 and 16, 2023
Week 10 Binary Search Trees Appendix B5.2, Chapter 12 - -
Week 11 Red-Black Trees Chapter 14 - -
Week 12 Dynamic Programming Chapter 15 - -
Week 13 More on
Dynamic Programming 		Chapter 15 Homework 4 xx xx, 2023
Week 14 Mid-Semester Break - - -
Week 15 Graphs Theory &
Shortest Paths		 Chapter 22
Chapter 24		 - -
Week 16 NP-Completeness Chapter 34 - -
Week 17 Revision - - -
Week 18 & 19 Final Exams - - -