Algorithms and Data Structures - Spring 2018

Course Program

This page contains a preliminary program of the course. This program is subject to change, so, please, monitor the announcements page and always refer to the schedule page for more details on the topics covered in the course.

• Introduction to algorithms and data structures: intro to the course (syllabus), the importance of algorithms, the example of the Fibonacci series.
• Complexity under the RAM model. Growth of Functions: big-O, omega, and theta notations.
• Representing numbers: space complexity. Adding and multiplying numbers. The simple algorithms and their analysis.
• Analysis of basic algorithms: complexity and correctness of insertion-sort.
• Other basic data structures and algorithms and their analysis (e.g., list operations, bubble-sort).
• Divide and conquer strategy: binary search, merge, merge sort, recursive multiplication, median and k-smallest selection.
• General divide and conquer strategy and complexity: recurrences.
• Sorting: quicksort, heaps and heapsort.
• Hash tables.
• Binary search trees.
• Radix-search. Tries, and ternary search tries.
• Red-Black Trees: structure, properties, insertion, and deletion.
• B-Trees. Data structures in secondary storage: modeling disk access. Structure, search, and insertion in B-trees.
• String matching: Knuth-Morris-Pratt algorithm, Boyer-Moore algorithm.
• Graphs and elementary graph algorithms: graph representations, depth-first search algorithms, strongly-connected components
• Minimal spanning trees.
• Greedy algorithms: general strategy, Huffman codes.
• Dijkstra's algorithm for shortest paths.
• Dynamic programming: examples, and general strategy.
• Dynamic programming and shortest paths in a graphs: Bellman-Ford algorithm.
• Randomized Algorithms: randomized variants of already-seen deterministic algorithms, Monte Carlo and Las Vegas algorithms, examples.
• Interesting randomized algorithms: Primality testing with basic elements of modular arithmetic.
• Basic elements of complexity theory: polynomial-time algorithms and problems; the P complexity class; the NP class; polynomial-time reduction and NP-completeness; satisfiability.