Topics (as time permits)

1. Introduction[pdf]

Introduction to data structures and algorithm analysis, ADTs, features of C++.

2. Mathematical Fundations and Algorithm Analysis [pdf]

Mathematics Review. Asymptotic notations and growth of functions. Case study.

3. Linear Structures [pdf]

Abstract Data Types (ADTs) lists, stacks and queues.

4. Trees[pdf]

General trees, binary trees, search trees, AVL trees, splay trees, B-trees.

5. Hashing[pdf]

Hash function, separate chaining, open addressing, extendible hashing.

6. Priority Queues [pdf]

Binary heap, leftist heap, binomial heap.

7. Sorting and Order Statistics [pdf]

Insertion sort, shell sort, heapsort, mergesort, quicksort, indirect sorting and external sorting. Order statistics.

8. Graphs and Networks [pdf]

Implementation of graphs, topological sort, shortest path, network flow problems, minimum spanning tree, search techniques, introduction to NP-completeness.

9. Algorithm Design Techniques [pdf]

Greedy algorithms, divide and conquer, dynamic programming, randomized algorithms, backtracking algorithms.

Motivation of the course  :

  The most important property to express of any entity in a system is its type. In this course we deal with entities that are structured objects (e.g., an object that is a collection of other objects). When determining its type, the kinds of distinguishing properties include :

• Ordering : are elements ordered or unordered ? If ordering matters, is the order partial or total ? Are elements removed FIFO (queues), LIFO (stacks), or by priority (priority queues) ?
• Duplicates : are duplicates allowed ?
• Boundedness : is the object bounded in size or unbounded ? Can the bound change or it is fixed at creation time ?
• Associative access : are elements retrieved by an index or key ? Is the type of the index built-in (e.g. as for sequences and arrays) or user-definable (e.g. as for symbol tables and hash tables) ?
• Shape : is the structure of the object linear, hierarchical, acyclic, n-dimensional, or arbitrarily complex (e.g. graphs, forests) ?

1. Previous Assignments and projects (Spring 2000   and Spring 2002)
2. Spring 2000 Midterm(with solution) and  Final exams.
3. Spring 2002 Miderm and Final exams.
4. Fall 2003 Midterm and Final exams.
   
5. Gnuplot
6. ddd

Notes and Policies

       1.Information about the course appears in this Web page. Changes will be made here and/or  posted to the course mailing list (CS340@cs.uregina.ca).
       2.Late assignments are not accepted for any reason and will receive 0 points, except for extensions granted to the entire class.
       3.Basic concepts on recursion, ADTs  List, Stack, Queue, Tree and OO concepts are strongly recommanded for this course.
       4.You can discuss the assignment with other students but MAY NOT read, copy, or exchange other student's code.
       5.Out-of-class help is available from your Professor and  can take one of the following ways of communication:
           1.face to face: please respect in this case the office hours posted in this web page and on office door,
           2.through email to the instructor
           3.or using the course mailing list.
      6.Attendence is expected in lectures. Little time is available to assist those who have missed relevant classes.
      7.The midterm exam is closed book and   will be given during the regular lecture meeting time in the regular  classroom.
      8.The final exam is closed book and will be cumulative, but with more emphasis on material covered after the midterm.
      9. You must pass the final exam in order to pass the course.

About the slides

All slides  are in PDF and compressed("gzipped") Postscript (.ps.gz).
To view Postscript under MS-Windows you need to install :
           1. Ghostscript:  the interpreter of the Postscript language
           2. and  gsview :  the  corresponding previewer .
The above tools + tools for other systems/platforms are available in the following web page  : Ghostscript and GSview

Up: teaching
 

mouhoubm@cs.uregina.ca