ECE-1762: Algorithms and
Data Structures
Instructor: Andreas Veneris, veneris(at)eecg(dot)toronto(dot)edu
Admin: Duba Burin, dubravka(dot)burin(at)utoronto(dot)ca
Teaching Assistant: Zissis Poulos, zpoulos(at)eecg(dot)toronto(dot)edu
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:
T.Cormen, C.Leiserson, R.Rivest, and C.Stein
``Introduction to Algorithms,''
McGraw Hill, 2001
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