# Introduction to Data Structures and Algorithms

16:198:512

This course is suitable for Computer Science M.Sc. students who have not taken a solid Algorithm classes in his/her undergraduate study. Students from other departments can request special permission numbers provided they meet the prerequisites as stated below.

The course study a variety of useful algorithms and analyze their complexity; by that experience to gain insight into principles and data-structures useful in algorithm design.

This course counts as category A for M.Sc. degree requirement. This course does NOT count as category A for Ph.D. students. Ph.D. students should take 513 instead.

Credits:
3
Prerequisite:

Calculus and Discrete Math and Ch 1, 2, 3 of the Textbook and Chapter 0 of the reference below.

Topics:

1. Complexity Measures. Methods for expressing and comparing complexity of algorithms: worst and average cases, lower bounds, and asymptotic analysis.
2. Searching, Sorting. Lower bounds for comparison-based sorting; merge sort, quick sort, heapsort, insertion sort (binsort, radix sort).
3. Divide and Conquer. Fast integer multiplication; recurrences; the master theorem; randomized median and selection algorithms; quicksort; fast matrix multiplication.
4. Graph Search Algorithms. Graphs representations; depth first search; topological search; strongly connected components. Breadth first search and layered DAGs.
5. Greedy Algorithms. Spanning trees and cuts, union-find and path compression; minimum spanning tree (MST) algorithms; Sample of randomized algorithms.
6. Shortest Paths (SPs) in Digraphs. Single-source SPs for nonnegative edge weights; priority queues and Dijkstra's; SPs in DAGs; single-source SPs for general edge weights.
7. Dynamic Programming. Paradigm of SPs in DAGs; longest increasing subsequence; (approximate) string matching; integer and (0, 1) knapsack problems; chain matrix multiplication; single-pair reliable SPs, all-pairs SPs; independent sets.
8. Introduction to Linear Programming
9. Network Flows. Max flow min cut theorem; bipartite matching; Menger's theorem and disjoint dipaths. Global minimum cuts.
10. NP-completeness and Problem Reductions and Coping with NP-Completeness. Approximation Algorithms and Fix Parameter Tractability.
11. Algorithm Sampler* Some more advanced topics of current interest like Page Rank, External Memory Algorithms, Streaming Algorithms, Parallel Algorithms, Distributed Algorithms, and Quantum Computing.

Course Material:

Textbook: Introduction to Algorithms by Cormen, Leiserson and Rivest, Third Edition, The MIT Press and the useful

Reference: Algorithms by Dasgupta, Papadimitriou, and Vazirani, McGraw Hill

Expected Work:

Weekly Homeworks and a Programming Project (about 25% f the final Grade)

Exams:
Weekly Quizzes plus two Midterms and a cumulative Final
Learning Goals:

- will be prepared to contribute to a rapidly changing field by acquiring a thorough grounding in the core principles and foundations of computer science (e.g., techniques of program design, creation, and testing; key aspects of computer hardware; algorithmic principles).

- will acquire a deeper understanding on (elective) topics of more specialized interest, and be able to critically review, assess, and communicate current developments in the field.

Professor:
James Abello Monedero
Ahmed Elgammal
Semester:
Fall
Spring
Course Type: