## CSI2110 Data Structures and Algorithms (Fall 2015): course description

WEB PAGE: http://www.eecs.uottawa.ca/~lucia/courses/2110-15/
Virtual campus web site is where most material is available
PROFESSOR: Lucia Moura
tel: 562-5800 ext. 6678
email: lucia@eecs.uottawa.ca
OFFICE HOURS: Office: SITE 5-027
Tuesdays 11:40-12:40 and Thursdays 10:10-11:10
TA CONTACTS: TA names and contact, for each lab and DGD
CSI2110A: Lecture 1: Tuesday 13:00 - 14:30 MRT 205
Lecture 2: Thursday 11:30 - 13:00 MRT 205
students attend one of the DGDs/tutorials:
DGD/Tutorial 1A: Friday 14:30-16:00 DMS1150
DGD/Tutorial 2: Monday 17:30-19:00 CBY B205
students attend one of the labs:
Laboratory 1: Monday 14:30 - 16:00 STE 2060
Laboratory 2: Monday 14:30 - 16:30 STE 2052
Laboratory 3, 4: Tuesday 10:00 - 11:30 STE 0130
CSI2110B: Lecture 1: Tuesday 10:00 - 11:30 FSS 1007
Lecture 2: Thursday 8:30 - 10:00 FSS 1007
students attend one of the DGDs/tutorials:
DGD/Tutorial 1B: Friday 14:30-16:00 MRT 205
DGD/Tutorial 2: Monday 17:30-19:00 CBY B205
students attend one of the labs:
Laboratory 1: Monday 14:30 - 16:00 STE 0130
Laboratory 2: Tuesday 13:00 - 14:30 STE 2052
Laboratory 3: Tuesday 13:00 - 14:30 STE 0130

TEXTBOOK: Data Structures and Algorithms in Java (6th ed.), Michael Goodrich, Roberto Tamassia, Wiley, 2014.
Textbook is available at Agora bookstore
(The textbook is required)

COURSE
OBJECTIVES:
• Students will learn in a systematic way the most commonly used data structures with emphasis on their abstract properties.
• Understand the typical algorithms that operate on each kind of data structure and learn how to analise their performance.
• Be able to compare different data structures for solving the same problem, and choose the best.
COURSE OUTLINE:
1. Introduction and review. (Sept 10)
2. Analysis of algorithms. (Sep 15, 17)
3. Stacks, queues, deques.(Sep 22)
4. List and iterator ADT. (Sep 24)
5. Trees and binary trees. (Sep 29, Oct 1)
6. Priority queues and sorting. (Oct 6)
7. Heaps. (Oct 8, Oct 13)
8. Maps and dictionaries (Oct 15)
9. Search trees: binary search trees (Oct 15), AVL trees (Oct 19, 22), (2-4) trees (Nov 3).
10. Hash tables (Nov 5)
11. Sorting and their analysis: insertion sort , selection sort, bubble sort, merge sort, quick sort and other sorting methods. (Nov 10, Nov 12)
12. Graphs: data structures for graphs, traversals, minimum spanning trees, shortest paths. (Nov 17, Nov 19, Nov 24, Nov 26)
13. Strings and pattern matching. (Dec 1, Dec 3)
14. Review. (Dec 8)

MARKING SCHEME: 30 marks (A) Assignments (3 theoretical, 2 programming)
(NOTE NEW:) + LAB & DGD participation (3% bonus towards (A))
30 marks (M) Midterm test
40 marks (F) Final Exam

if (M+F)/70 >= 50% then G= A+M+F
else G=(M+F)*10/7

IMPORTANT
DATES:

 weight: due date: (tentative) Assignment 1 (T) 5% Oct 3 Assignment 2 (P) 7.5% Oct 17 Midterm Test 30% Sunday Nov 1, 3:00PM-5:00PM room: tba Assignment 3 (T) 5% Nov 14 Assignment 4 (P) 7.5% Nov 28 Assignment 5 (T) 5% Dec 6

Dates from the University of Ottawa Academic Calendar:
First lecture: September 10 (Thursday)
Study break: October 25-31
Last date to drop: November 20
Last lecture: December 8 (Tuesday)