CSI 2110: Data Structures and Algorithms

(3 hours of lectures, 1.5 hours of labs and 1.5 hours tutorial per week, 3 credits)

(Fall, 2019, September 4 - December 3)

Instructor:

Professor WonSook LEE

CBY A509 (tel x2501)

wslee@uottawa.ca

http://www.eecs.uottawa.ca/~wslee

Professor's Office Hour:

TBD at CBY A509

TAs: 

• TBD

Timetable:

Description:

The concept of abstract data types. Simple methods of complexity analysis. Trees. The search problem: balanced trees, binary-trees, hashing. Sorting. Graphs and simple graph algorithms: traversal, minimum spanning tree. Strings and pattern matching. Prerequisites: ITI1121/ITI1221, MAT1348

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.

Textbook:

Michael Goodrich and Roberto Tamassia, Data Structures and Algorithms in Java, Wiley. (6th ed.) 

The textbook is available at AGORA Bookstore.

The textbook has a great web site at http://ca.wiley.com/WileyCDA/WileyTitle/productCd-EHEP002900.html.

Other sources:

D.E. Knuth, Sorting and Searching , vol. 3 of The Art of Computer Programming, Addison Wesley, 1973. 

T.A. Standish: Data Structures in Java. Addison Wesley. 

S.Sahni: Data Structures, Algorithms, and Applications in Java.

Marking scheme:

A maximum of 100 marks will be available. The division is as follows:

To pass the course you must get at least 50% in the exams. The exact calculation is as follows:

            If (M+F)/70 >= 50% then Grade = A+M+F

            else Grade =(M+F)*10/7

NOTE I: Assignment submission

NOTE II: A student who has an official medical certificate (from the University Health Services) for the absence on the day of the midterm will have the final exam mark scaled up accordingly.  The medical certificate must be obtained on the very day!

NOTE III: Attendance in the lecture, Lab and tutorial will be checked randomly and it may be rewarded as 2% bonus points toward the final grade.

Schedule (tentative): 

Marks for assignments and exams are available in the Blackboard website

Lecture Schedule (Tentative):

The lecture notes are available in the Brightspace website

1. Introduction and review.
2. Stacks, queues, deques.
3. Analysis of algorithms.
   
4. List and iterator ADT.
5. Priority queues and sorting.
6. Trees and binary trees.
7. Heaps.
8. Maps and dictionaries 
9. Search trees: binary search trees , AVL trees ), (2-4) trees .
10. Hash tables
    
11. Sorting and their analysis: insertion sort , selection sort, bubble sort, merge sort, quick sort and other sorting methods. 
12. Graphs: data structures for graphs, traversals, minimum spanning trees, shortest paths.
13. Strings and pattern matching.
    
14. Review.