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).
 | Contact information |
| Textbook and recommended reading |
| Course outline |
| Course evaluations |
| Useful links |
| Course Textbook: Database Management Systems, Ramakrishnan and Gehrke, McGraw Hill |
| Strongly Recommended
reading: Database Systems: The Complete Book, Garcia-Molina et.al., Prentice Hall |
|
Other Recommended reading: Data Structures and Algorithms in Java, Adam
Drozdek, Brooks/Cole publishers, Thomson Learning, 2001
|
| 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 Hashing |
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
|
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 |
RAID. 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 Security/Encryption
|
Microsoft Invited Lecture
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
|
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 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 |
| 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
|
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.
|
|
See notes from CPSC 331 course on simple sorts, complex sorts, heaps, graph1, trees1, trees2, simple_hashing.
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?",
Encryption/security
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.
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% |
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.
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.
Sensor Web Guest lecture
Future Databases
TIBCO software: http://spotfire.tibco.com/en/demos.aspx
GrassGIS is an open source project: http://grass.itc.it/download/index.php
For data analysis software, Acastat (and others) can be found at http://www.newfreedownloads.com/find/data-analysis.html
|
On-line LibrariesComputer Science Bibliography Advanced Search Bibliography on object-oriented programming Other Research Related Links
|
| Web_trees_search |
| Ignobel Prize |
| Optimization |
| Visualization and AdaBoost link |
Optical Illusions
| Optical Illusion Site - Green Dragon |
| Optical Illusion - 3D face |
| Optical Illusions |
| Human Mind Text |
| Puzzles and Fun Math |
Trees
| AVL tree |
| BST animation |
| B tree animation @slady |
| B tree operations and code |
| Red-black tree video |
| Optimization |
| C++ STL links
|
Hashing and compression
| Hugues Hoppe web page at Microsoft |
| MP3 and Huffman coding |
| Huffman coding |
Animations
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
