Design and analysis of algorithms. Asymptotic analysis as a means of evaluating algorithm efficiency. The application of induction and other mathematical techniques for proving the correctness of an algorithm. Data structures for simplifying algorithm design, such as hash tables, heaps and search trees. Elementary graph algorithms. Assignments include written work and programming assignments.

Course objectives

By the end of the course you are expected to gain the following skills:

1. earn skills on analysis of algorithms.
2. learn how to determine the asymptotic growth of algorithms and how to apply probabilistic analysis for non-deterministic algorithms.
3. study various algorithms of the areas of sorting, searching, hashing, string matching, and graph algorithms with reviews of elementary data structures (binary search trees, hash table, etc.).
4. study design techniques of randomized, divide-and-conquer, dynamic programming, and greedy algorithms. 5 learn about the limits of computation by looking at NP completeness.
5. learn necessary skills to apply the knowledge on algorithmic analysis from a competitive programming perspective.

Prerequisites

1. CSCI 2312 : Object Oriented Programming,
2. CSCI 2421 : Data Structures and Program Design,
3. CSCI 2511 : Discrete Structures.

Topics covered

1. Getting started (ref: CLRS:2)
2. Growth of Functions (ref: CLRS:3)
3. Recurrences (ref: CLRS:4)
4. Probabilistic analysis and randomized algorithms. (ref: CLRS:5)
5. Sorting algorithm
6. Insertion sort and Heap sort (ref: CLRS:2, 6)
7. Quick sort (ref: CLRS:7)
8. Sorting in linear-time (ref: CLRS:8)
9. Elementary data structures (ref: CLRS:10)
10. Hash tables (ref: CLRS:11)
11. Binary search tress (ref: CLRS:12)
12. Balanced Binary search tress. (ref: CLRS:13)
13. Dynamic Programming (ref: CLRS:15)
14. Greedy Algorithms (ref: CLRS:16)
15. Elementary Graph Algorithms (ref: CLRS:22)
16. Minimum Spanning Trees (ref: CLRS:23)
17. Single source Shortest Paths (ref: CLRS:24)
18. All pairs shortest paths (ref: CLRS:25)
19. NP-completeness (ref: CLRS:34)
20. String Matching (ref: CLRS:32)
21. Number-theoretic Algorithms (ref: CLRS:31)