CPSC 319 Data Structures, Algorithms and Applications


Course Announcements:

Jan 08th Welcome to CPSC 319 course! This web site will be used as primary means for communication and announcements.



Please contact your TA directly for ALL questions about code, assignment specs, bonuses, extensions on assignment submission and question or clarification regarding material covered in labs.

You can find tutorial plan, assignment submission requirements, assignment submission record, code examples, etc. on TA web site.

NOTE: ALL QUESTIONS regarding assignments (specifications, code, marking) should be directed to your TA.
You can send an e-mail or make an appointment to met him if you need any help with your program, report or algorithm.


Course Textbook

  1. Algorithms Robert Sedgewick, Kevin Wayne March 19, 2011 032157351X 978-0321573513
    Pearson Education, 4th Edition



Recommended Reading

  1. Data Structures and Algorithms in Java, Adam Drozdek, Brooks/Cole publishers, a division of Thomson Learning, 2001 or 2005 edition (other editions are acceptable)

  2. Algorithms, Design Techniques and Analysis, M. Alsuwaiyel, World Scientific, 1999

  3. Introduction to Algorithms Cormen, Lieserson, Rivest, Stein Mc Graw Hill 2001

  4. Data Structures and Algorithm Analysis in Java Mark Allen Weiss, Peachpit Press, 1998


Java Books

  1. Java by Dissection by Ira Pohl and Charlie McDowell
  2. Java Programming from the beginning K.N. King, Norton and Company, 2000
  3. Java - A Framework for Programming and Problem Solving K. Lambert, M. Osborne Brooks/Cole 1998

Objectives and Outcomes

It is expected that students have basic procedural and object-oriented programming skills, as introduced in the courses CPSC 219, or 231/235. Since Java is the programming languages that students were made familiar with, it is expected that students are confident in performing assignments in those languages.

The course introduces algorithms that can be used to solve several fundamental problems as well as data structures that are commonly used to manage information when solving problems of small-to-moderate size. It also uses the terminology and notation that is commonly used in computer science for the analysis of algorithms.

The course introduces basic data structures, such as sorting, searching, arrays, lists, trees, graphs and hash tables, as well as some computational problems. Students are required to write programs using the above algorithms and data structures on assignments, to perform experiments involving the execution of their programs on data sets in order to assess the performance of their algorithms, and to use very simple analytic techniques to assess the performance of simple fragments of code.

Please note that learning to program is a very time-consuming activity and assignments in this course may well take more time to complete than assignments in other courses. The course emphasizes student activity. This means that a significant portion of what you learn will come from working on the assignments and programming independently.


Course Outline

Week 1

     History of Algorithms. Data Structures.

Lecture on History of Algorithms

Week 2

      Complexity. Algorithms.  Textbook Chapter 1.4

     Lecture Analysis of Algorithms


Week 3

    Search. Sorting. Bubble sort, Insertion Sort, Selection Sort.  Textbook Chapter 2.1

    Lectures Searching Applications, Elementary Sorts


Week 4

   Merge sort, Quick Sort textbook Chapters 2.2, 2.3

   Notes: simple sorts, complex sorts

   Arrays. Lists.

  Lectures Mergesort, Quicksort

Week 5

   Stacks. Queues. Binary Trees. Textbook Chapters 1.3, 2.4, 3.2

   Lecture Stacks and Queues

Data Analysis lecture

Week 6

       Binary Search Trees. AVL trees. Textbook Chapter 3.2.

       Lecture Binary Search Trees


     BST code

     BSTrotation1 BSTrotation2





Week 7

Midterm exam review questions.

Midterm Exam.

Week 8

Lecture on kd trees
Lecture on tries and search
Web search lecture


  Heaps. Heapsort. Textbook Chapter 2.4

 Lecture Priority Queues


Week 9

Hashing. Lecture on hashing.

Perfect hashing. 


Coalesced hashing lecture.

Textbook Chapter 3.4

Lecture Hash Tables

Week 10


Textbook Chapters 4.1, 4.2

Lectures Undirected Graphs, Directed Graphs


NP-complete comic, Graph comics

  Week 11

Graphs. Prim's, Kruskal's, Dijkstra algorithms

Textbook Chapters 4.3, 4.4

Graph review questions and corresponding Graph review figures

Greedy Algorithms lecture

Lectures Minimum Spanning Trees,  Shortest Paths


Week 12  

Invited lectures

Week 13

Applications of algorithms. Image Processing, biometrics, computer simulation.

Wednesday: Industry Invited lecture: "How to get hired by industry" James Birchall, Pason Systems, Calgary

Final review. Last week of classes. 

Week 14


Course Evaluation

Three components are included in the determination of the course grade.

Component Component Weight
Assignments 30%
Midterm Examination 30%
Final Examination 40%


The lab work and assignments are considered to be essential components of the course. Completed assignments should be submitted electronically to your TA. Remember to put your name, tutorial section and your TA's name on any material you hand in.


There will be four programming assignments in this course. Each assignment is to be submitted on the due date. Each of the FOUR assignments must be submitted in order to pass the course!

Please consult your TA web site on late submission policies and exceptions.

IMPORTANT: Versions of assignments that you find on this web page MAY be modified by your instructor at a later date, but no later than 3 weeks before the assignment is due.

NOTE: For Engineering students, Java is taught concurrently with CPSC 319 course. It is the primary language for all assignments. However, request to use another language (C++) will be honored by your TAs for each individual assignment upon e-mail request. Submission procedures will be explained by your TAs.

Assignment late submission policy:

Submitting your assignments is MANDATORY to pass this course. In case you cannot complete it on time, you can ask extension from your TA for up to 2 days (via e-mail), with each day penalty of 10% of your final assignment mark will be assessed.

Submission instructions:

Assignments are to be submitted through D2L system. Each student will find one folder in his/her D2L account to submit the assignment in, and notification will be sent to your TA once you upload your files in the folder.

Go to ASSESSMENTS --> Dropbox and submit your assignment in the folder called Assignment 01 - <Your Tutorial No>.
The convention for your enclosed file (zip, z7 or rar) should be: Tutorial-No_Last-Name_Assignment-No, for example (T02_Jarada_01).

Asmt 1  Sorting and Searching

Asmt 2  Binary Search Trees

Asmt 3  Hashing

Asmt 4  Graphs 


Access to Computers and Help

Each of you has been assigned two labs per week. TAs will provide help with the assignments. Since TAs for this course spend most of their required time in the lab, you should go to the lab for help rather than seeking out TAs in their offices.

General Notes

If you encounter problems in the lab that your TA can not resolve, or if you want to discuss the operation of the labs, please contact the Instructor. You should contact your Instructor to discuss lectures, exams and the overall organization of the course. In this course, you are always welcome to ask questions if you don't understand something during the lecture or in the lab. You can also always contact your instructor during office hours or any time by e-mail. Some of the exercises and assignments may require a reasonable amount of time to complete. You will find that you need to spend time on the computer outside of your regularly scheduled labs, and this is the way the course is designed.


Useful links

Some lectures:

See notes from CPSC 319 course on simple sorts, complex sorts, hashing, trees

History of Mathematics


Hashing and compression


Department of Computer Science
University of Calgary
2500 University Dr. N.W.
Calgary, AB, T2N1N4
Office: MS 269