2SI4 Web Page

Instructor: Dr. Xiaolin Wu, ITB-A315

Lectures: Monday, Wednesday, Thursday 10:30-11:20, ITB/137

Tutorials: T01: Thursday 8:30-10:20 JHE/326H

T02: Friday 14:30-16:20 T13/125

T03: Wednesday 14:30-16:20 JHE/326H

Teaching Assistants:

H. Hassanein

office hours: Mon. 2~4pm, ITB A302

hhassanein@grads.ece.mcmaster.ca

N. Iftikhn

office hours: Tue. 2~4pm, ITB A302

iftikhn@mcmaster.ca

Y. Shen

office hours: Wed. 10am~12pm, ITB A103

sheny35@mcmaster.ca

A. Hammad

office hours: Thur. 2~4pm, ITB A302

ahammad@mcmaster.ca

A. Khezriam

office hours: Fri. 2:30~4:30pm, ITB A302

khezriam@grads.ece.mcmaster.ca

Announcements:

Tutorials start in the week of January 14

Course Objectives:

To provide a foundation of the concepts of data abstraction, algorithm design and performance estimation. The main topics to be discussed are:

1) Algorithm performance estimation using asymptotic complexity analysis.

2) The use and implementation of elementary data structures such as lists, stacks, queues, trees, binary search trees and hash tables.

3) Efficient algorithms for searching and sorting.

Required materials:

Textbook: M.A. Weiss, Data Structures & Problem Solving Using JAVA, 3rd or

4th ed., Addison Wesley, (ISBN 0-321-32213-4).

Additional References - not required:

1) M. T. Goodrich, R. Tamassia, Data structures & Algorithms in Java

2) A. V. Aho, J. E. Hopcroft, J. D. Ullman, Data structures and algorithms, Addison-Wesley,

3) T. E. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 2nd or 3rd ed., MIT Press and McGraw-Hill.

4) Any good references on program design and on the Java programming language.

Outline:

✸ Review:

Java programming language review, brief math review.

✸ Algorithm Complexity Analysis:

Space and time complexity, asymptotic notation, examples.

✸ Recursion

Recursive algorithms, their space and time complexity analysis, divide and

conquer method.

✸ Lists:

Basic operations, array-based implementation, linked lists.

✸ Stacks and Queues:

Operations, array and linked-list implementations, applications.

✸ Trees:

Operations, pointer-based and array-based implementations.

✸ Searching and Hashing:

Linear search, binary search, binary search trees, hash tables.

✸ Sorting Algorithms:

Insertion sort, bubble sort, merge sort, quicksort, heaps, heap sort.

✸ (Time permitting) Graphs. Algorithms on Graphs:

Representation of graphs, paths, spanning trees, Dijkstra’s Algorithm, Prim’s

Algorithm.

Assessment:

Assignments – 20% (3 individual programming assignments)

Midterm Test – 25%

Quizzes – 5%

Final Exam – 50%.

Midterm Sample Questions:

• On the topic of algorithm complexity analysis, the questions will be similar to Assignment 1 in format, scope and difficulty level.
• Can you implement two stacks in one array? If yes, devise the algorithm.
• What are the average and worse case time complexities of Find, Insert, and Delete operations on a binary search tree of size N?
• Is Delete operation of binary search tree more expensive than Find operation? If yes, by how much? Does Delete have a higher complexity than Find in Big O sense?
• Prof. Wu claims that the order in which a fixed set of elements is inserted into a binary search tree does not matter – the same tree results every time. Give a small example that proves Prof. Wu wrong.
  __________________________________________________________________________________

Lecture Notes:

Lecture_1.ppt

Lecture Notes Sept. 11-18

Lecture Notes Link Lists

Lecture Notes Pointers

Lecture Notes Stacks

Lecture Notes Search Trees

Lecture Notes Hashing

Lecture Notes Heap

Lecture Notes Union-and-Find

Lecture Notes on Graph Algorithms