Courses
- Data Sructures (10117) תקציר הקורס:
- Advanced Algorithm and Complexity (10121) תקציר הקורס:
Abstract:
Issues of the course:
Recursion. Recursion as an interdisciplinary thinking paradigm. Analysis of Algorithms and Mathematical Foundations: Growth of f?unctions and Asymptotic notations, Summations, Recurrences: The Substitution, Iteration and Master Methods. Searching for a term in a sorted and an unsorted list, minimum, maximum, merging sorted series, analyzing the complexity of their run times.
Abstract Data Types, the Concept of Implementation, Data Types in C. Lists: Linked Lists, the Linked List as a Data Structure, Circular and Double Linked Lists. Stacks, Queues, Infix, Postfix, Prefix and Evaluating Expressions.
Trees: Binary Trees and Traversals, Binary Search Trees and Josephus problem, General Trees, Balanced Trees.
Heaps and Heapsort, analysis of Heapsort . Sorting and Searching:, Quicksort,
analysis of Quicksort, Sorting in Linear Time : Bucket sort, Radix sort, Counting sort . Median and Order Statistics, Select algorithm and their applications. Sequential/ Binary/ Tree Searching. Hash Tables.Abstract:
The course consists of two parts: one is devoted to some methods of
algorithm design, while another part is an introduction to the complexity theory.
The topics covered are: flow in networks and matching,
string-matching, approximation algorithms; Church-Turing thesis, decidability, reducibility, complexity.