Information Structures III

CPSC 461

Course Announcements:

Welcome to all 461 Students!

News and updates:

Midterm exam is now marked. 

-Textbook review chapters and list of topics can be found HERE.

-List of PRACTICAL problems for training can be found HERE.

-Solutions to practical problems can be found HERE.

Bonus Questions: Parity bit prisoners, ball drop, robot on the rail tracks, etc.

Please submit bonus question answers to your TA.

Note on assessment:

All assignments must be submitted by all students in order to successfully Pass the course. If one or more assignments is missing, no grade above D+ can be assigned at the end of the term.  All programs should be written in Java (in exceptional cases other language might be permitted by request to your TA).





bulletContact information
bulletTextbook and recommended reading
bulletCourse outline
bulletCourse evaluations
bulletUseful links

Course textbook and recommended reading 

bulletCourse Textbook:
Database Management Systems, Ramakrishnan
and Gehrke, McGraw Hill


bulletStrongly Recommended reading:
Database Systems: The Complete Book, Garcia-Molina, Prentice Hall



Other Recommended reading:

Data Structures and Algorithms in Java, Adam Drozdek, Brooks/Cole publishers, Thomson Learning, 2001

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

File Organization and Processing, Alan L. Tharp, John Wiley and Sons




Course Outline


Week Dates Topic Lecture Notes Lab Plan
1 9/11-Sep Intro. Topic review.

Information Systems review.


Self Assessment


 No Labs this week
2 16/18-Sep

Representing structured data. Index structures. Overview of Storage and Indexing


Ch1 Text 1, Ch1 Text 2;

Ch8, Text 1

Ch 11, Text 1


Lab 1 Asmt 1 discussion

Lab 2 Ch 9, text 1, exercises at the end of Chapter 9 - RAID (Ex 9.3, 9.4,  9.5, 9.15 and 9.19)


3 23/25-Sep Memory hierarchy.

Disks and Files.


Tree indexes. B trees and variants.


Ch10, Text 1

Ch 9, Text 1, pp. 304-337 Section 13, p. 557, Text 2

Lab 1 Indexes Ch 8 ex 8.1, 8.2, 8.3

Lab 2 B-trees Text 1, Ch 10, p365, Ex 10.1 (1,2,3,6), 10.3,


4 30Sept/2 Oct


Algorithms for dealing with large data sets.

Data Integrity and Security.


Text 2, Ch 14 (14.1, 14.2)

Text 2, Ch 14 (14.5, 14.6, 14.7)



Lab 1 B trees Text 1, Ch 10, 10.5 (selected), 10.6 (selected)

Lab 2 Asmt 2 discussion

5 7/9 Oct  


Invited lecture

Moved to week of Oct 21-23




Microsoft Invited  Lecture

Text 1, Ch 28

Grid in-class

Text 2, Ch 14 (14.3)



Lab 1 -Thanksgiving

Lab 2-Hashing Ch 11, text 1, ex 11.5,  11.7, 11.10

6 14/16

Information Retrieval

Web-search indexes

Text 1, Ch 11,
Text 1, Ch 21, Ch 27


Text 2, Ch 14 (14.3)



Lab 1 - Grid files, r-trees, spatial indexes Ch 28, p. 990, Ex. 28.3, 28.4, 28.5

Lab 2- More hashing - extendable, linear Ex 11.6

7 21/23 Oct

Spatial trees, Grid files, Quad-trees, r-trees

K-d trees

kd trees animations

Text 1, Ch 13, 14

Lab 2 - Asmt 3 and algorithm analysis examples

Lab 1 - Encryption, Ch 21, text 1, Ex at the end of Ch 21 (RSA, SSL, digital signatures)


8 28/30 Oct


Midterm exam

Tu, 28 Oct, MS 319
2:00-3:15 pm

Th: Invited Industry


Textbook review chapters and list of topics can be found HERE.

List of PRACTICAL problems for training can be found HERE.

Solutions to practical problems can be found HERE.



Midterm review



9 4/6 Nov

Data mining.

Market analysis.


Text 1, Ch 26


Ch 26 data mining
Ex 26.2, 26.5

10 10-11 Nov - reading days, no lectures

14 Nov

Pattern analysis.


Text 1, Ch 26


Section 26.4.2 - an algorithm for decision trees and Ex 26.8

Section 26.5.1 - clustering algorithm and Ex 26.9


11 18/20 Nov Clustering.

Concurrency control.

Failure and recovery.


Text 1, Ch 17, 18

Learning algorithm review

Link to Weka data mining


Asmt 4

Ch 16 Ex 16.1, 16.2, 16.4

Ch 17 Ex 17.4, 17.5, 17.10 (refers to figure 17.5)

12 25/27 Nov Parallel Systems

Distributed Systems.


Text 1, Ch 22, 23

Ch 18, Ex 18.4, 18.5, 18.7 

Ch 22.1, 22.2 

13 2/4 Dec Information retrieval.

Future directions.


Invited Lecture by Alex Vetsak, lead Business Development, MYLE Electronics.

Education: MSc in Computer Science and in Petroleum Engineering.

DATABASE summary

Final review topics

List of FINAL EXAM CHAPTERS for review is posted HERE. 

List of FINAL EXAM review topics is posted HERE. 




Additional notes

See notes from CPSC 331 course on simple sorts, complex sorts, heaps, graph1,  trees1, trees2, simple_hashing.



Labs and Assignments

The deadlines for submitting four course assignments are below:

Sept 26, 9:00 pm Assignment 1 "Pictures from Space", Assignment 1 Marking Scheme
9:00 am by e-mail to your TA

Information System Data Representation and Storage, 9:00 pm, to your TA

Additional resources: code to get color of pixel

October 17th, 9:00 pm Assignment 2 "Trouble with Bitmaps",
Index Structures 

EXTENDED to Monday, November 11th, 9:00 pm Assignment "Want Salt with It?",


Sample input file wordsALL.txt

SATURDAY, November 29th, Assignment 4 "Data Mining"

Assignment 4 bonus

Data Mining, 9:00 pm  to your TA

For detailed Lab schedule and Assignment specifications, as well as any relevant information, please check TA's web site regularly.


Course Evaluation

Three main components are included in the determination of the course grade. There are four assignments in this course.

Final exam will be determined by the registrar.

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

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. All assignments must be completed independently unless stated otherwise. Please consult University Calendar for rules and regulations related to Academic Misconduct policy.


Useful information

    Some links

Sensor Web Guest lecture

Future Databases

Sample Excel data test file

TIBCO software:

GrassGIS is an open source project:

For data analysis software, Acastat (and others) can be found at


On-line Libraries

Project Gutenberg Library

Berkeley Library 

Computer Science Bibliography Advanced Search

Bibliography on object-oriented programming

Other Research Related Links 


bulletIgnobel Prize
bullet Optimization
bulletVisualization and AdaBoost link


Optical Illusions

bullet Optical Illusion Site - Green Dragon
bullet Optical Illusion - 3D face
bulletOptical Illusions
bullet Human Mind Text
bullet Puzzles and Fun Math


bulletAVL tree
bullet BST animation
bulletB tree animation @slady
bulletB tree operations and code
bulletRed-black tree video
bullet Optimization
bulletC++ STL links


Hashing and compression

bullet Hugues Hoppe web page at Microsoft
bulletMP3 and Huffman coding
bulletHuffman coding


bullet Database Clustering
bullet Randomized mazes
bullet Sorting out Sorting code and demo
bulletAlgorithms animation
bullet Optimization
bulletLink to "How to write an unmaintainable code" website 
bullet Link to Euclidean Distance Transform Computation 
bulletScientific Computing World
bulletHead tracking
bullet Optiverse
bulletDeep Blue game



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