COMP 314
Algorithms and complexity
|
Subject: Algorithms and complexity |
Course Code: COMP 314 |
| Type: Core | FM: 100(60 int+40 final) |
Course Description: Builds upon existing skills in the mathematical analysis of algorithm complexity, including lower bounds, worst-case and average behavior. General techniques in algorithm design (such as divide and conquer, greedy and dynamic programming approaches) in the context of problem domains like graph, sorting, and optimization problems. Introduction to the topic of NP-complete problems.
Contents:
- Introduction to algorithms:Mathematical preliminaries or foundations: Growth of functions, Summations, Recurrences.
- Data structures revisited:Stack, Queue, Linked list, Hash tables, Binary search trees, Red-Black trees.
- Analysis of sorting methods: Selection sort, Insertion sort, Quick sort, Heap sort, Bubble sort, Merge sort, sorting in linear time.
- Medians: Minimum and Maximum
- Algorithm strategies: Brute-force algorithms, Greedy algorithms: action-selection problem and Huffman codes , Divide-and-Conquer, Backtracking, Branch-and-bound, Heuristics, Pattern matching and string/text algorithms, Numerical approximation algorithms.
- Dynamic programming: Matrix-chain multiplication and longest common subsequence
- Graph algorithms: Representation, traversal techniques, minimum spanning tree, shortest path algorithms, Dijkstra’s algorithm, Flow networks.
Text Books:
Introduction to Algorithms- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest.
The Design and Analysis of computer algorithms- Aho/Hopcroft/Ullman.
Discrete Mathematics for Computer Scientists- John Truss.
An Introduction to Data Structures with Applications- Jean Paul Tremblay, Paul G. Sorenson. Second Edition. |
