| School of Engineering and Technology, (SET) | ||||
| AT70.24 : Algorithms Design and Analysis 3(3-0) | ||||
| Course objectives: | ||||
This course introduces methods for the design and analysis of efficient algorithms emphasizing methods useful in practice. Different algorithms for a given computational task are presented and their relative merits evaluated based on performance measures. The following important computational problems will be discussed: sorting, searching, elements of dynamic programming and greedy algorithms, advanced data structures, graph algorithms (shortest path, spanning trees, tree traversals), and other advanced algorithms. |
||||
| Learning Outcomes: | ||||
The students on the completion of this course would be able to:
• Analyze an algorithm time and space complexity.
• Apply and implement a repertoire of standard and advanced algorithm-design techniques as well as data structures.
• Design and implement algorithms given a problem
• Judge the appropriateness of the applications of different algorithms and data structures
|
||||
| Pre-requisite(s): | ||||
None |
||||
| Course Outline: | ||||
I. Foundations
1. AsymptoticAnalysis
2. Recurrences
II. Randomized Algorithms
1. Indicator Variables
2. Probabilistic Analysis
III. Sorting
1. Quicksort
2. Sorting in Linear Time
3. Order Statistics
IV. Hashing
1. Hash Tables
2. Hash Functions
3. Universal Hashing
4. Perfect Hashing
V. Advanced Data Structures
1. Skip List
2. Fibonacci Heap
3. B-Tree
4. Red-Black Trees
VI. Advanced Design Techniques
1. Dynamic Programming
2. Greedy Algorithms
VII. Graph Algorithms
1. Shortest Paths
2. Minimum Spanning Tree (added)
3. All-Pairs Shortest Paths (added)
VIII. Other Topics
1. RSA
2. Rabin-Karp Algorithm
3. Edit Distance
4. NP-Completeness
5. Linear Programming
6. Knuth-Morris-Pratt Algorithm
7. DFT and FFT
|
||||
| Laboratory Sessions: | ||||
None |
||||
| Learning Resources: | ||||
| Textbook: | ||||
No designated textbook, but class notes and handouts will be provided. |
||||
| Reference Books: | ||||
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. (2009). Introduction to Algorithms, Third Edition (3rd ed.). The MIT Press.
• Robert Lafore.(2002). Data Structures and Algorithms in Java, Second Edition (2nd ed.). Sams, Indianapolis, IN, USA. (added)
• Roberto Tamassia (2013). Data Structures and Algorithms in Python, 1st Edition. Wiley.
• Skiena, S. S.(2008). The Algorithm Design Manual, Second Edition (2nd ed). Springer Science & Business Media. (added)
|
||||
| Journals and Magazines: | ||||
None |
||||
| Time Distribution and Study Load: | ||||
Lectures: 45 hours
Self-study: 135 hours
|
||||
| Teaching and Learning Methods: | ||||
This course is mainly theoretical, so the teaching method is based on classroom lectures with active participation by students in problem-solving sessions. In particular, after each new design method is presented, students will be challenged to solve problems using it.
|
||||
| Evaluation Scheme: | ||||
• ProgrammingAssignments:30%
• Midterm:30%
• Final:40%
A grade of “A” indicates excellent and insightful understanding of the key concepts; “B” indicates a good understanding of the key concepts; “C” indicates barely acceptable understanding; and “D” indicates poor understanding.
|
||||
| Instructor(s): | ||||
|
||||