Formal treatment of algorithms and algorithms design methodologies; both sequential and parallel paradigms will be covered. Measures of parallel complexity. Program complexity and correctness proofs.

None

1. Knowledge and experience in a high-level programming language.
2. Familiarity with abstract data types and data structures.
3. Familiarity with mathematical concepts from calculus, linear algebra, discrete
mathematics, and elementary probability theory.
4. Course in algorithms including following topics:
- Measuring the complexity of algorithms: Best-case, Average, and Worst-case
complexities, asymptotic notation
- Design &analysis of classical algorithms such as Binary search, Insertion Sort, etc.
- Quicksort, Heap Sort, Tree Sort, Radix Son
- Mathematical properties of binary trees: lower bounds for depth and leaf-path
length.
- Induction and correctness proofs.
- Recurrence relations.
- Implementing graphs and digraphs; DFS and VFS search and traversals &
applications to shortest paths in unweighted graphs and topological sort of dags,
computing shortest paths in graphs.

To provide a solid foundation for the classical theory of sequential algorithms, and to cover some of the most important recent algorithmic developments, including the rapidly emerging theory of parallel algorithms. To provide students with the mathematical tools nCSsary to analyze the correctness and efficiency of algorithms, and to be able to judge how close an algorithm is to being optimal for a given problem. To enhance the ability to create new algorithms or to modify existing algorithms in order to solve new problems. To introduce lower bound theory as a tool to judge how close an algorithm is to being optimal for a given problem. To describe major sequential and parallel design strategies that have wide applicability in problem solving.

1. Foundations of sequential algorithms (weeks 1 & 2)
2. Intro to parallel algorithms and architectures (weeks 3 & 4)
3. Intro to graph algorithms and disjoing sets (week 5)
4. Probability and average complexity of algorithms (week 6)
5. Intro to lower bound theory and NP-completeness (week 7)
6. Greedy Method (week 8)
7. Divide-A-Conquer (week 9)
8. Dynamic Programming (week 10)

None

None

Engineering Science: 3credits or 100%