Courses
- Introduction To Software Engineering (10014) תקציר הקורס:
- Data Sructures (10117) תקציר הקורס:
- Design & Analysis Of Algorithms (10120) תקציר הקורס:
- Advanced Algorithm (10121) תקציר הקורס:
Abstract:
The first digital computer was built for the US Army in 1946.
High-level programming languages appeared in the 1950s.
Within a quarter century, we already faced what is known as the “software crisis”.
The crisis did not occur because software was not func tioning properly but rather because of problems related to the software development process, and the growing demand for complex software systems. The software crisis manifests itself in many problems: lack of well defined requirements;
frequently changing requirements; poorly estimated costs and budgets;
programmer productivity that cannot keep up with demand;
and software of insufficient quality. Software Engineering was developed in order to solve the problems that characterize the software crisis, and it encompasses the entire software development life cycle.Abstract:
Issues of the course:
Recursion. Recursion as an interdisciplinary thinking paradigm. Analysis of Algorithms and Mathematical Foundations: Growth of functions 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:
Introduction to Linear Programming, Simplex Method, Primal Problem and Dual Problem. Transportation Problem, Transportation Simplex Method, Assignment Problem – Hungarian Algorithm. Dynamic Programming.
Graph Algorithms: different methods of representing graphs, finding transitive closure: Matrix Multiplication and Warshall's Algorithm, Euler and Hamiltonian Path. BFS and DFS Algorithms ,Topological Sort, Strongly Connected Components, Hyper Graph, Bridges and Biconnected components, Pert. Trees and Greedy Algorithms: Huffman codes. Shortest Paths: from single source and between all pairs of vertices – Dijkstra / Bellman Ford / Floyd Warshall algorithms. Single-source Shortest Paths in DAG (Directed Acyclic Graph).
Minimal Spanning Trees, Kruskal and Prim algorithms. Euler and Hamiltonian Path.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, dynamic programming, approximation algorithms; Church-Turing thesis, decidability, reducibility, complexity.