Fundamental of Data Structures

At the end of the course, students should be able to: 1. describe fundamental Data Structures including linked-lists, trees, binary search trees, AVL trees, stacks, queues, priority queues, and hash-tables and skiplists; 2. explain fundamental abstract data types which can include: Maps, Sets and Vectors; 3. explain program data structures and use them in implementation of abstract data types; 4. devise novel solutions to small scale programming challenges involving data structures and recursion; 5. describe the basic algorithmic complexity; 6. estimate the algorithmic complexity of simple, non-recursive programs; 7. perform simple inductive proofs and proofs by contradiction and reason about program correctness and invariants; and 8. select appropriate data structures and algorithms for problems and to justify that choice.

Stacks, linked lists; trees, priority queues; search trees; sorting; hashing, garbage collection; storage management; maps and dictionaries; text processing; graphs. Introduction to algorithms and their importance, mathematical foundations: growth functions, complexity analysis of algorithms, summations, recurrences, sorting algorithms. Algorithm design: divide-and-conquer approach, greedy approach. Graph algorithms and its applications in games. String matching. Dynamic programming and longest common subsequence. Theory of NP–completeness.