CPSC 331 Information Structures I


horizontal rule

Contact information


Contact  information


TA Information




Textbook and recommended reading


Course information


Course outline


Code examples


Course evaluation




Useful links


Course policies

horizontal rule

Course Textbook

Title: "Data Structures and Algorithms in Java"
Author: Adam Drozdek
Publisher: Brooks/Cole publishers, a division of Thomson Learning, 2001

Recommended Reading

  1. Algorithm Analysis in Java
    Mark Allen Weiss, Peachpit Press
  2. Robert Sedgewick,
    Michael Schidlowsky, Addison Wesley Professional
  3. Fundamentals of Algorithmics,
    Giles Brassard and Paul Bratley, Prentice Hall
  4. Algorithms, Design Techniques and Analysis,
    M. Alsuwaiyel, World Scientific
  5. Algorithmics: Theory and Practice,
    Giles Brassard and Paul Bratley, Prentice Hall

Books on Java

  1. Java by Dissection by Ira Pohl and Charlie McDowell

  2. Java Programming from the beginning K.N. King, Norton and Company

  3. Java - A Framework for Programming and Problem Solving K. Lambert, M. Osborne Brooks/Cole


horizontal rule

Course Information

Computer Science 331 Information Structures I

Algorithms: searching, sorting, graph navigation. Data structures: arrays, lists, stacks, queues, graphs, trees, hash tables; time and space efficiency of associated algorithms.

horizontal rule

Objectives and Outcomes

It is expected that students have basic procedural and object-oriented programming skills, as introduced in the prerequisite courses CPSC 231 and CPSC 233. CPSC 331 continues CPSC 231 and 233 by introducing additional tools and skills that are needed to solve problems by computers, through the development of programs with high-level programming languages. It 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 introduces the terminology and notation that is commonly used in computer science for the analysis of algorithms.

The course introduces fundamental data structures, including arrays, linked lists, graphs, trees, and hash tables. For each of these, the course includes definitions of the operations on data that these data structures support, algorithms that are commonly used to implement these operations, and a discussion the worst-case complexity. The course introduces fundamental algorithms to search for data in sorted and unsorted lists, and in graphs and trees, as well as algorithms to sort the elements of an array. This course also introduces terminology and notation that is commonly used in computer science to describe the worst-case performance of algorithms on large inputs.

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 large sets of data 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.


horizontal rule

Course Outline


Week 1


Introduction to Analysis of Algorithms (Chapter 2, pp. 49-70, Ch. 5, pp. 159-187, Appendix pp. 609-613)

   Week 2


Analysis of Algorithms and Algorithmic Complexity (Chapter 2, pp. 49-70, Ch. 5, pp. 159-187, Appendix pp. 609-613):

                             Time and space complexity
                             Big-O notation
                             Examples of iterative and recursive algorithms
                             Worst case, average, best case performance

Week 3


Searching and Sorting (Ch.2, Ch. 9, pp. 433-471):

                              Binary search
                        Sequential search
                        Interpolation search     
                     Selection sort
                        Bubble sort


Week 4


Sorting continues (Ch. 9, pp. 433-471):

Insertion sort
Merge sort
Quick sort

Week 5


Arrays and Linked Lists (Ch. 3 pp. 71-123):

Singly and doubly linked  lists  
Circular lists

Week 6


Stacks and Queues (Ch. 4, pp. 129-158)

                              Priority queues
                         Array and list implementation
                         Case study: A-mazing problem

Lecture on queues and lecture on stacks is now available.

Midterm Exam

Week 7

bulletReading Week

Week 8

bullet Binary Search Tree
   Insertion/Deletion, Search
   Tree traversals
Lectures on trees are now available.


Week 9


Trees (Ch 6, pp. 256-264, Ch 7, pp. 287-305)
Heaps (Ch 8, pp. 355-410)

     AVL trees,
     Multiway trees


Week 10

bulletHeaps and Heapsort

     Graph definitions and operations
     Graph traversals


bullet     The shortest path problem. Dijkstra's algorithm. Minimum cost spanning trees. Kruskal's and Prim's algorithm

Week 12


Hash Tables (Ch. 10, pp. 483-526) Lecture on hashing.

  Hash functions
  Perfect hashing
  Dynamic hashing

Week 13

bullet Selected topics (algorithms and applications). Lecture on Future Development.

horizontal rule

Code Examples in JAVA

bulletBubble Sort
bulletSelection Sort
bulletInsertion Sort
bulletQuick Sort
bulletMerge sort
bulletLinked List Search
bulletLinked List Insertions Simple
bulletLinked List Insertion Complex
bulletLinked List Deletion
bulletDoubly Linked List Insertion
bulletDoubly Linked List Deletion
bulletCircular Linked List
bulletBinary Tree Traversals


horizontal rule

 Code Examples in C++

bullet Bubble Sort
bulletSelection Sort
bulletInsertion Sort
bulletQuick Sort
bulletLinked List
bulletLinked List 2
bulletDoubly Linked List


horizontal rule

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 final exam will be scheduled by Registrar during the final examination period.


The lab work and assignments are considered to be essential components of the course. Completed assignments should be deposited in the appropriate box for your lab section located on the second floor of the Math Sciences building or submitted electronically (instructions will follow). Remember to properly identify and label any material you hand in.

LAB exercises are now available. They are grouped according to subjects studies in the course.



There will be four programming assignments in this course. Each assignment is to be submitted on the due date as indicated below. Please note that ALL assignments should be attempted in order for you to pass the course.  Late assignments will not be accepted.

IMPORTANT: Preliminary versions of assignments that you find on this web page MAY BE modified by your instructor at a later date, but no significant changes will take place within the two weeks before the assignment is due.


Assignment # Topic Due Date





February 26th, 4:00 pm



Binary Search Trees 

Sample data sets:


March 10th, 4:00 pm






March 24th, 4:00 pm







Extended till April 11th, 4:00 pm


All assignments for this course are individual. Academic misconduct on assignments and / or exams will result in penalties which may include an F grade on the assignment component, failing the course and expulsion from the faculty and university (see Plagiarism/Cheating/Other Academic Misconduct sections of the university calendar).

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 lectures or labs. You can also always contact your instructor during office hours or any time by e-mail. Some 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.

horizontal rule

Useful links

bulletC++ STL links
bulletPuzzles and Fun Math
bullet Optimization
bulletLink to "How to write an unmaintainable code" website 
bulletSearch tree data structures
bulletHuman Mind Text
bulletB tree animation
bulletR tree animation
bulletBST animation
bullet Link to Euclidean Distance Transform Computation 





This page was last updated on 06/01/2020

Department of Computer Science
University of Calgary
2500 University Dr. N.W.
Calgary, AB, T2N1N4
Office: MS 269
Phone: (403) 220-5105
Fax: (403) 284-4707
E-mail: marina@cpsc.ucalgary.ca