|
HU Credits:
4
Degree/Cycle:
1st degree (Bachelor)
Responsible Department:
computer sciences
Semester:
Teaching Languages:
Hebrew
Campus:
E. Safra
Course/Module Coordinator:
Guy Kindler
Coordinator Office Hours:
By appointment
Teaching Staff:
Prof Michael Ben-Or
Prof Guy Kindler
Course/Module description:
1. Sorting: insertion-sort, merge-sort and quick-sort. Lower bound for comparison sorting. 2. Asymptotic analysis of running time 3. Recurrence relations, and the divide and conquer paradigm 4. Dynamic data structures 5. Heaps: implementation with an array. Heapsort algorithm 6. Binary Search Trees, AVL trees 7. Huffman Coding 7. Hashing algorithms. 8. Graph algorithms: breadth first search, depth first search (BFS, DFS), minimum spanning tree (MST), strongly connected components (SCC), topological ordering.
Course/Module aims:
See learning outcomes
Learning outcomes - On successful completion of this module, students should be able to:
Learn and understand in-depth the basic algorithms and data structures in Computer Science:
sorting, graph search, coding schemes, trees, graphs, arrays, heaps.
Analyze existing algorithms and data structures.
Develop new algorithms and data structures
Understand the complexity of computational problems
Attendance requirements(%):
Teaching arrangement and method of instruction:
Frontal lectures + recitation sessions
Course/Module Content:
Data Structures, course number 67109 Syllabus 1. Sorting: insertion-sort, merge-sort and quick-sort. Lower bound for comparison sorting. 2. Asymptotic analysis of running time 3. Recurrence relations, and the divide and conquer paradigm 4. Dynamic data structures: 5. Heaps: implementation with an array. Heapsort algorithm 6. Binary Search Trees: AVL trees 7. Hash tables 8. Graph algorithms: breadth first search (BFS), minimum spanning tree (MST)
Required Reading:
Introduction to Algorithms, Second Edition . Thomas H. Cormen, Charles E. Leiserson, .Ronald L. Rivest
Additional Reading Material:
NA
Grading Scheme :
Additional information:
Home assignment will be checked either by an oral interview or in writing, during three meetings during the semester. The weight of these will be 15 points out of the final grade (5 for each meeting) There may be an additional quiz, whose grade will weigh 15 points out of the total, but will only be counted in if it is higher than the test grade.
|
