[Last Update: Monday, June 23, 2003] | Cpsc 461 - Copyright (C) 2003 Katrin Becker
Welcome to Computer Science 461...
NEWS & Changes |
After the Review Session on Thursday: there will be a whole movie (not just the documentary parts) - the choice is: "Toys" starring Robin Williams; or Mel Brooks' "Space Balls" [June 23] Digital Libraries Notes & Storage Area Networks [June 21] Main Points Summary for AlphaSort Paper: "AlphaSort: A Cache-Sensitive Parallel External Sort" [June-19 - later] *unofficial* extention Both parts 2 & 3 can be handed in the Monday after they are due without penalty. If you get them in By Friday Midnight, there's a 5 point bonus. Useful Code Site: http://www.abvolt.com/Sources.htm [June 19] Links to Gwen Howziger's (previous TA) Review Notes [June 12] [June 6] , [June 4 - later that same day] , [June 4] , [June 1] ,[May 30] ,[May 24] , [May 21], [May 20] , [May 19] , [May 18] | Mystery 'Tune' One of my Favorites Very Useful Shhhh! Final Exam: Friday *, June 27 8-10 AM (Yikes!) *MFH 164 The 461 COURSE DIRECTORY (CODE, etc.) IS AT: /home/profs/becker/Courses/461 TA Discussion Page

Admin. Stuff | Lesson Plans | Help
Important Dates | Previous Weeks | Course Directory (CODE)
Lecture Sections | THIS WEEK | Reference Links
Teaching Assistants | Comming Up | New Links
Marks So Far |  | Becker's Home Page
Other News | FAQ | (Becker's approach to teaching)

| SPRING: |  | FALL: |
| Lecture P01: Katrin Becker |  | Lecture L01: Katrin Becker |
| T-R at 9:00-12:00 ICT 116 |  | T-R at 12:30 - 1:45 MFH 164 |
| e-mail: K.Becker office: MS 220 phone: 220-5769 Office Hours: by appointment |  | e-mail: K.Becker office: MS 220 phone: 220-5769 Office Hours: T-R 11-12 |

| TAs | Lab |  |  | Contact |
| Georges Jodoin | [spring] Lab B20 | M-W @ 3 in MS 205 |  | email: jodoin |
| Georges Jodoin | [spring] Lab B21 | T-R @ 1 in MS 205 |  | email: jodoin |
| TBA | Fall B01 | T-R @ 11 in ENC 129 |  | tba |
| TBA | Fall B02 | M-W @ 11 in ENC 129 |  | tba |
| TBA | Fall B03 | T-R @ 11 in ENC 33 |  | tba |
| TBA | Fall B04 | M-W@ 10 in ENC 129 |  | tba |

Important Dates Spring 2003: | Why it's Important | Important Dates FALL 2003:
Tues. May 14 | Lectures Begin | Sept. 10
Fri. May 23 | HW Presentation Hard-copy due | Fri. Sept 27
Mon. May 26 - Thur. May 29 | HW Presentations | Mon. Sept. 29 - Thur. Oct. 9
Fri. June 6 | File Ananlysis, PART 1 due [Proposal] | Fri. Oct 11
Fri. June 20 | File Ananlysis, PART 2 due [Code] | Fri. Nov. 7
Thur. June 26 | File Ananlysis, PART 3 due [Post Mortem] | Fri. Nov. 21
--- | Last Assignment due | Fri. Dec. 5
Thur. June 12 | ***MIDTERM*** | Thur. Oct 30
Thur. June 5 | Reading DAY | Tues Nov. 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:

- how to represent stuff
- how to organize it
- how to manipulate it
- how to make efficient use of storage devices: both long- and short-term

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

at this site and in the Course:

Updates [something I've changed]:
Possible "Movietime" Stuff: (votes and suggestions welcome - must have computer science connection) "From Morf to Morphing" Featurette on the early days of CG from the movie "Willow" "Noodle Player" by Afro Celt Sound System Volume 2: Release [a flash toy on the music CD] StrongBad Email (Fun Flash for Everyone: Japanese Animation,Dragon,Fingers,Techno,English Paper) "The Tech of Shrek" PDI/Dreamworks - documentary on the CGA in Shrek "Deconstructing Minority Report" Fox - bits of documentary on special effects in Minority Report
Assignment number for "submit" : File Ananlysis, part 1 = #1 File Ananlysis, part 2 = #2 File Ananlysis, part 3 = #3 Hardware Presentation = #4 Last Assignment (desn't apply in spring) = #5
NEWS
[June 23] Digital Libraries Notes & Storage Area Networks [June 21] Main Points Summary for: Nyberg, Barclay, Cvetanovic,Gray,Lomat "AlphaSort: A Cache-Sensitive Parallel External Sort" [June-19 - later] *unofficial* extention Both parts 2 & 3 can be handed in the Monday after they are due without penalty. If you get them in By Friday Midnight, there's a 5 point bonus. [June 19] Links to Gwen Howziger's (previous TA) Review Notes (these pages have been copied locally so some of the links my not work) Basic File Ops Indexing Part 1 & Part 2 File Formats Part1 & Part 2 Data Compression Part 1 & Part 2 [June 12] - 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. 2) Gdk-pixbuf (http://developer.gnome.org/arch/imaging/gdkpixbuf.html) 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. File Formats Extra Info: 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 [June 6] - More Assignment Help: Framework for the Post-Mortem (useful to give you direction for the work too); Habits of Mind; Marking Rubric for "The Work" and the Post Mortem. Please read over the marking guides carefully. You will have to submit a self-assessment again, plus, the marking guides will tell you what is required. [June 4 - later that same day] - some possibly useful links to information on how to do a research project (might be helpful even if you plan to use one of the supplied papers as your starting point).
http://www.abs.gov.au/websitedbs/D3310116.NSF/4a255eef008309e44a255eef00061e57/ a3b99ee98e8c272b4a256521002128fb!OpenDocument
http://www.cmu.edu/adm/uri/faq.html
http://www.researchtoolbox.com/
http://trochim.human.cornell.edu/kb/probform.htm
http://www.virtosphere.de/schillo/research/tips.html
[June 4] - Assignment (Proposal) Marking Guide PLUS important information on submitting your proposal and how it will be marked. This mark guide is a "rubric" which describes the criteria by which you will be assessed. You need to MARK YOURSELF and hand that in with your proposal. The TA will then fill in his own rubric and explain the differences (if any). There will be an "unofficial" grace period allowed for the submission of this assignment: you may submit this assignment without penalty up until the end of Monday. (After that it is considered late). There is a 5 point bonus for submitting the assignment by the end of Friday. Copies of the Marking Rubric and the required cover page are available outside Becker's office. Submitting your own assessment also gets you a 5 point bonus (not submitting your own assessment will make it harder for you to argue your case if you decide to try for a better mark than you've been given. How to use the Proposal Rubric: Each row has a certain point value associated with it (usually in the range 2-5). The columns are labelled: "unacceptable" "meets requirements" "exceeds requirements". The numbers at the column headers are multiplication factors, so: unacceptable = point-value X 0 meets = point-value X 0.5 exceeds = point-value X 1.0 When marking, you need to choose which "box" your assignment matches best, and then that is the value allotted to that portion. There are no in-betweens. At the end the values are added up and mapped onto the letter grade. [June 1] - Assignment Ideas [May 30] - ppt slides for LZ77, LZ78 [May 24] - Additional Notes on File Formats - Revision - reorganization of existing notes (now in 5 sections), some new pictures. [May 21] - new less cheesey ppt notes on binary I/O [May 20] - submit should work: the Hardware asst is # 4; Also, you should all have windows access, should you dare care to use it. [May 19] - new Notes on Indexing [power point slides] (Um, the MS Dog seems to have eaten my homework. What's left is a pale shadow of its former self - I will replace these when I get a chance but I'm working on the next set first. Then I'm taking that dog to be 'fixed'.) [May 18] - updated versions of notes on presentations - expanded research assignment outline (A-B-C specs & marking guide still to come)
NEW LINKS:
Still to come: Everything!!!!!

Week | Date | Lesson Plan:
1: | [R May 15] [Sept 8-12] | Introduction - why are we here? admin stuff (asst, the RULES, what you need to do to pass, etc.) Basic File Anatomy basic file operations kinds of file how UNIX views a file logical vs. physical file structure logical vs. physical file operations Problem: *Save a Tree* Problem: *Wondersort*
2: | [T May 20] [Sept 15-19] LABS: get into groups and choose topic for HW assignment | Problem: *Wondersort* solution records/fields 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 Indexing single; multiple indices; index placement; index management Problem: *Save a Tree* solution
3: | [R May 22] [Sept 22-26] | Binary I/O blocking our own records File Formats Part 1a Data Representation Introduction to File Formats
4: | [T May 27] [Sept. 29 - Oct 3] LABS: Presentations | File Formats Part 1b Characteristics of Scientific & Graphics File Formats Analog - Digital Conversion Audio Files Data Compression Part 1 introduction intuitive methods Movie Time (during the break): "Scully's New Car" Pixar - full Computer Generated Animation & Pixar Tour
5: | [R May 29] [Oct. 6 - 10] LABS: Presentations | Data Compression Part II dictionary methods (Second Half) Guest Lecture [King Chung Huang & Mike Mattson] About EduSource & the CAREO project Current Directions in Educational Object Repository Research Movie Time (during the break): "Buffy Special Effects" Joss Whedon, Fox - documentary on Special Effects in Season 3 of Buffy
6: | [T June 3] [Oct 14 - 17] | File Formats Part 1c Video Files 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 Data Compression Part III statistical methods bit of coding theory; huffman coding adaptive huffman coding Movie Time (during the break): "From Morf to Morphing" Featurette on the early days of CG from the movie "Willow"
7: | [T June 10] [Oct 20-24] Buffy Season 4 to be released June 10. | Data Compression other methods arithmetic coding fractal compression UNIX File System Signatures binary attributes generating signatures using signatures bloom filters Wicked Problems http://www.pmi-portland.org/presentations/Wicked_problems.pdf http://kmi.open.ac.uk/people/sbs/csca http://www.mmm.com/meetingnetwork/readingroom/gdss_wicked.html http://www.cpgec.ufrgs.br/norie/iglc10/papers/83-Whelton&Ballard.pdf Movie Time (during the break): "The Tech of Shrek" PDI/Dreamworks - documentary on the CGA in Shrek

8:
[R June 12] [Oct 27 - Oct. 31]

Review [first half]
MIDTERM [50 Minutes: 10:45-11:35]
Movie Time (during the break):

"Hush" - Buffy

9:
[T June 17] [Nov. 3 - 7]
Go over Midterm

Cosequential Processing
Defined
working with multiple files
heapsort
tournament trees
K-way Merge
Multi-Phase Merge
Movie Time (during the break): [no more Buffy - I promise]
Chuck Jones - Traditional Animation - Classic Cartoons

10:
[R June 19] [Nov. 13]

Cosequential Processing
Poly-Phase Merge
Cascade Merge
Examination of Alpha-Sort Paper
Movie Time (during the break): T2; "Noodle Player" by Afro Celt Sound System Volume 2: Release [a flash toy on the music CD]

11:
THIS WEEK[T June 24] [Nov. 17 - 21]

Digital Libraries
Distributed Storage Networks (Intro ONLY)
Movie Time (during the break): "Deconstructing Minority Report" Fox - bits of documentary on special effects in Minority Report

12:
[R June 26] [Nov. 24 -28]

Looking Back: Review - Questions ; Exercises
Also Student Assessments of Instructors
Movie Time (during the break): After Class: "Toys" or "SaceBalls

13:
[Dec. 1 - 5]

Review - Questions ; Exercises

In Other News....
Opportunities for UndergraduateWomen Research Project Funding Buffy Season 4 will be released in June 10. Angel Season 2 will be released in August.
OLDER LINKS & News:
PLEASE NOTE: Attendance in labs during the presenations is mandatory - and not just your OWN presentation. This material is testable material. Wicked Problems Information: http://www.pmi-portland.org/presentations/Wicked_problems.pdf http://kmi.open.ac.uk/people/sbs/csca http://www.mmm.com/meetingnetwork/readingroom/gdss_wicked.html http://www.cpgec.ufrgs.br/norie/iglc10/papers/83-Whelton&Ballard.pdf

Reference Links
461 Course Directory [code samples; assignment samples; data; etc.] The 461 COURSE DIRECTORY IS AT: /home/profs/becker/Courses/461
Course Text & Software Support |
All Things Java | java.sun.com 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 BOOKS: http://www.apl.jhu.edu/~hall/java/Java-Books.html http://www.cs.uidaho.edu/~frincke/misc/booklists/java_books.html http://www.ibiblio.org/javafaq/books.html http://www.javaranch.com/
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]
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 June 23, 2003 09:58 PM