This course covers fundamentals of computer algorithms and data structures. The objective is to give the audience an introduction to combinatorial modeling, algorithms and the underlying analysis. It also aims to present a wide range of fundamental data structures and examine their complexity in terms of space/time. In brief, the course will start with a review of a number of basic combinatorial tools such as recurrences, worst/best/average case analysis, probability, and discrete mathematics (summations, principles of counting, induction). Next, it will present a wide range of fundamental data structures and algorithms along with a detailed analysis of their time/space behavior and real life use. Topics include searching and sorting, dictionary operations, dynamic programming, greedy methods, graph algorithms (shortest paths, maximum flow), parallel algorithms, intro to NP-completeness, approximation algorithms and one advanced topic of choice such as matrix multiplication, FFT or amortized analysis.

Algorithms and data structures along with an in-depth performance analysis is an important subject and has numerous applications in different areas of computer engineering such as software design, distributed computing, networking and wireless computing, programming languages, compilers, operating systems, multimedia and security, computer architecture, and digital circuit design.

This is a homework (problem solving) course and all topics are exercised on paper for the student to gain expertise on the subject. Theory is presented in class (lecture) and tutorial concentrates on homework. No programming is required. Auditing is welcome but strongly not recommended; a student will need to do homeworks and take the exams to digest the ideas.

Requirements and Weight: 5 homeworks 30%, 100 min Midterm exam 30%, 150 min Final exam 40%. Exams are open book. Homeworks can be done in groups of 1 or 2 students.

Textbook:

Parenthesis contain the number of lectures, where every lecture is equivalent to two hours approx:

* Background review: summations, recurrences, asymptotic notation, probability, graphs/trees (3)

* Heapsort and analysis (1)

* Deterministic and randomized quicksort and analysis (2)

* Sorting in linear time (1)

* Lower bounds for sorting, medians and order statistics (1)

* Hashing, Uniform Hashing and analysis (1)

* Binary Search Tree and Balanced Trees (2)

* Dynamic Programming (2)

* Greedy Algorithms (2)

* Amortized analysis and Splay trees (2)

* Intro to Graph Algorithms, BFS/DFS (1)

* Minimum Spanning Trees (1)

* Single Source Shortest Paths and intro to All-Pair Shortest Paths (2)

* Maximum flow and bipartite matching (3)

* Intro to Parallel Algorithms (2)

* Intro to Theory of Computation (2)

* Complexity and NP Completeness (3)

* Intro to Approximation Algorithms (1)

Back to main