[Last Update: Thursday, January 01, 2004]
Cpsc 461 - Copyright (C) 2003 Katrin Becker
Welcome to Computer Science 461...
NEWS & Changes

Admin. Stuff
Lesson Plans




Lecture L01:
Katrin Becker

Alton Yu
Fall B01
T-R @ 11 in ENC 129

T-R at 12:30 - 1:45
MFH 164

Alton Yu
Fall B02
M-W @ 11 in ENC 129

e-mail: K.Becker
office: MS 220
phone: 220-5769
Office Hours: T-R 11-12

Gregor McEwan
Fall B03
T-R @ 11 in ENC 33

Gregor McEwan
Fall B04
M-W@ 10 in ENC 129

Why it's Important
Important Dates
FALL 2003:
Lectures Begin
Sept. 8
HW Presentation Hard-copy due
Fri. Sept 26
HW Presentations
Mon. Sept. 29 - Thur. Oct. 9
Research Project, PART 1due [Proposal]
Fri. Oct 10
Research Project, PART 2 due [Code]
Fri. Nov. 7
Research Project, PART 3 due [Post Mortem]
Fri. Nov. 21
Last Assignment due
Fri. Dec. 5
Thur. Oct 30
Reading DAYS
Mon./Tues Nov. 10-11

Welcome to Computer Science 461...

This course is formally known as "Information Structures II" and is intended as follow-up course for CPSC 331. It will be assumed that all students in this class are competent with the material covered in both CPSC 331 and CPSC 355. In this course, we discuss things like File Systems (Unix's and others) and various file formats (jpeg, .gif, .tiff, .bmp, .mp3, ...). We also look at data compression and some other advanced data representation and manipulation stuff (like signatures, decision trees, etc.).

In a nutshell, this course is about storing information (primarily in files) efficiently and effectively:

The material in this course is not hard but there is a LOT of it so make sure you keep up.

Updates [something I've changed]:

Assignment number for "submit" :
File Ananlysis, part 1 = #1
File Ananlysis, part 2 = #2
File Ananlysis, part 3 = #3
Last Assignment = #4
Recent Final Exam: MSWord; html
Announcement regarding the last assignment.... the data files labelled: "Record-Type-1-C1" are text versions of the corresponding file "F-TYPE-1-C1". These were created so you could see what the records in the file are supposed to look like. ALL test files for this assignment are 720KB files.

Please examine the "boot sector" for details of how each sample is corrupted. [note: Types 4 & 5 have 1/2 the block missing - 256 bytes - rather than 128 bytes]

In order to meet the assignment specs your program must be able to cope with at least ONE of the samples for that type.
Fibonacci [Polyphase] sort visualization, 3-way; 4-way
Thank you Dustin!!!

Polyphase vs Cascade Sort simulation (code)

Writing a Research Report:

NOV. 7: IMPORTANT news regarding the Assignment and How it is to be marked and submitted.

Audio files can be found at: /home/vision/behmb/audio
[Sept. 24] I will not be able to post the sign-up sheet on the web. The paper version currently lives outside my door (to the right).
[Sept 23] We Have a Temporary TA - Labs will run tomorrow as scheduled.
iCore Lecture on Digital Libraries (worth seeing) Sept 24 4pm BioSciences 587 (Learning Commons)

EOC: Pattern Recognition

Aoccdrnig to a rscheearch at an Elingsh uinervtisy, it deosn't mttaer in waht oredr the ltteers in a wrod are, the olny iprmoetnt tihng is taht frist and lsat ltteer is at the rghit pclae. The rset can
be a toatl mses and you can sitll raed it wouthit porbelm. Tihs is bcuseae we do not raed ervey lteter by it slef but the wrod as a wlohe.


Still to come:
Lesson Plan:

[Sept 8-12]

Admin Stuff (asst, the RULES, what you need to do to pass, etc.)

Introduction (notes) - why are we here?
Basic File Anatomy (notes)
basic file operations
how UNIX views a file
logical vs. physical file structure
Problem: *Save a Tree*
Problem: *Wondersort*
[Sept 15-19]
get into groups and choose topic for HW assignment
Problem: *Wondersort* solution [in class]
kinds of file
Logical vs. Physical file operations [PPT Slides]
Indexing (notes)
single; multiple indices; index placement; index management
Indexing [ppt slides]
manipulating fixed-length record files: adds; dels; mods
re-using space in fixed-length files
varying length records:[VLR] adds; dels; mods;
free lists for VLR - placement strategies (first, best, worst)
varying length record maintenance
Problem: *Save a Tree* solution [in class]

Binary I/O (notes)
Binay I/O [ppt slides]
blocking our own records
All About Data (notes)
Data Representation
Introduction to File Format
[Sept 22-26]
File Formats Part 1 (notes)
Characteristics of Scientific & Graphics File Formats (notes)
Analog - Digital Conversion (notes)
Audio Files (notes)
[Sept. 29 - Oct 3]
NOTE: Guest Lecture by J.R.Parker on non-text searching

Data Compression Part 1
Introduction (notes)
intuitive methods
[Oct. 6 - 10]
Data Compression Part II
dictionary methods

statistical methods
bit of coding theory;
huffman coding
[Oct 14 - 17]
Data Compression Part III
LZW revisited
adaptive huffman coding

File Formats Part II [assigned as reading in the notes]
Brief overview of some well-known formats: GIF, JPEG, BMP, PNG, FITS, MP3, AVI, WAV

Video Files
[Oct 20-24]

Data Compression
other methods
arithmetic coding
fractal compression
UNIX File System
binary attributes
generating signatures
using signatures
bloom filters
Wicked Problems

(Thursday?) Guest Lecture [Mike Mattson]
About EduSource & the CAREO project
Current Directions in Educational Object Repository Research
[Oct 27 - Oct. 31]
Review [Tuesday]
MIDTERM [Thursday, 50 Minutes: 12:30-1:40]
[Nov. 3 - 7]
Go over Midterm
Talk about assignment

MovieTime: [2003] Pixar Studios Tour/ Making of "Finding Nemo" [Disney/Pixar]
[Nov. 13]
Cosequential Processing
working with multiple files
tournament trees
Examination of Alpha-Sort Paper
[Nov. 17 - 21]
Cosequential Processing
K-way Merge
Multi-Phase Merge
Poly-Phase Merge
Cascade Merge
Also Student Assessments of Instructors
[Nov. 24 -28]
Digital Libraries
Distributed Storage Networks (Intro ONLY)
[Dec. 1 - 5]

Buffy Season 5 to be released December 9.

Looking Back: Review - Questions ; Exercises
In Other News....
Opportunities for UndergraduateWomen Research Project Funding
Buffy Season 5 will be released in Dec. 9.
Angel Season 2 will be released in Sept.
PLEASE NOTE: Attendance in labs during the presenations is mandatory - and not just your OWN presentation. This material is testable material.
Wicked Problems Information:
Reference Links
461 Course Directory [code samples; assignment samples; data; etc.]
The 461 COURSE DIRECTORY IS AT: /home/profs/becker/Courses/461
Software Support
Image reading libraries:
1) GNU imlib (http://freshmeat.net/projects/imlib)
Pros : Supports every graphics format known to man, supports basic image operations such as scaling, colorspace transform
Cons : May not work cross-platform, many dependency issues (the software guys will hate you), may not easily allow direct access to image data, poor documentation.
Pros : Supports all common graphics formats, portable, allows easy access to image data, good documentation, supports basic image operations such as scaling, colorspace transform, etc
Cons : Requires GLib, uses funny type defines for regular types

As for sound, you can get my .wav library out of /home/vraid2/wavlib-1.0.6.tar.gz. It only supports uncompressed .wav files, but it's dead simple and comes with reasonable docs.
All Things Java
Main Site - 1.4
Downloads [J2SRE & SUN ONE Studio 4]
Coding Standards
Java Doc
Libraries Doc
Sun's OO Concepts
AlphaWorks Robocode (Java) Site
Y. Danial Liang's notes on: Configuring JDK, compiling, and running programs from DOS prompt

General; maybe even fun...
Garry Morse's Game Programming Tutorial
Sun's Applet Tutorial
Sun's Threads Tutorial

Other Supplementary Material
Open Source UML Tool (application)

Parker's 501 Page -Link to Parker's CPSC 501 page [includes info on various kinds of algorithms like genetic algorithms, neural nets, simulated annealing; BOTTOM of page has links to notes on edge detection in images]

Video Conversion Website [thanks to Tony Truong]

Chapman, Nigel & Jenny, Digital Multimedia, 2000 John Wiley & Sons ISBN 0-471-98386-1
- excellent resource - explains many forms of mutlimedia WebSite [note: works under IE but not so well under netscape]: http://www.wiley.com/digital_multimedia
A Few Points of Interest:
Information on the Spare-Time Programming Contest (OPEN DEADLINE)
Need a diversion??? TRY THIS (warning: it's a great time waster)
Interested in Games Design?
An on-line Games Developer's Magazine [gamasutra.com]
- you can subscribe for free and you WON'T get a lot of unsolicited e-mails

Animated B-Tree
Please check this out - we are looking for comments (can be sent to me).
- in the course directory at /home/profs/Courses/461/BtreeExp
Cpsc 461 - Copyright © 2003 Katrin Becker Last Modified January 1, 2004 04:53 PM