Cpsc331 Information Structures, Winter 2004

Announcements about Cpsc331 will appear on this page

Links Page for Lecture Notes.

Discussion Page for Assignments.

Welcome back! 11.00 pm, SUNDAY April 25, 2004

Your Cpsc331 Final Exam papers have been marked and the final results computed.

TENTATATIVE RESULTS will be posted about 10.00AM, Monday, 26 April at Cpsc Main Office, ICT Floor 6. Results have been double checked, but if you find an error, email me at once. Final results go to Registrar on Friday morning.

The method of results computation is standard, and a requirement of the Course Description, with 40% weighting for the Final, and 30% each for Labs and Mid Term. The conversion of mark to Grade Points for the Final was as follows:

A+ (4.0) 39, 40
A (4.0) 37, 38
A- (3.7) 35, 36

B+ (3.3) 33, 34
B (3.0) 30, 31, 32
B- (2.7) 28, 29

C+ (2.3) 26, 27
C (2.0) 24, 25
C- (1.7)22, 23

D+ (1.3) 20,21
D (1.0) 17, 18, 19
F (0) 1 . . .16

Class Average in Final Exam was 30.0%.

Both Midterm and Lab marks were converted to grade points (GP), as follows:

A+ (4.0) 29, 30
A (4.0) 26, 27, 28
A- (3.7) 24, 25

B+ (3.3) 22, 23
B (3.0) 20, 21
B- (2.7) 18, 19

C+ (2.3) 16, 17
C (2.0) 15
C- (1.7) 14

D+ (1.3) 13
D (1.0) 12
F (0) 1 . . .11

Final result is (0.4* FinalGP + 0.3 * MidTermGP + 0.3 * LabGP).

[The TOTAL SCORE IN PERCENT is also posted, but as a guide only. It can happen, on a few occasions, that with a pair of students, the one with a slightly higher % score gets a slightly lower GP score. There is nothing unusual about this, since not all marks have the same value. It depends where the marks come from: Final, MT or Lab.]

Please: If you find yourself just under a grade boundary, do not become obsessed, and come after me to go through your Final Exam, question by question, until you have squeezed out enough extra marks to jump the hated boundary. Remember that there have to be boundaries, and that there is a random character to where you land. In some courses, you will be just below, but other times just above. In the end it will all average out, and, anyway, in five years you will not remember anything of such boundary obsessions. So give yourself a break, and accept where the roulette wheel stops.

Have a good summer.

Welcome back! THURSDAY April 22, 2004

There is a typographic error in the answer to Question 11b in the Trial Exam Questions. The answer is 200 collisions, not 2000.

GOOD LUCK TOMORROW

Welcome back! April 14, 2004

FINAL EXAMINATION, Friday, April 23.

The exam is closed book.

On for the exam is the material covered in class relating to Chapters 6, 7, 8, 9.

Of course, you are expected to have a good knowledge of the material in Chapters 3, 4, and 5, which were covered by the Mid Term Exam, since the data structures from those chapters are used in the data structures for Chapters 6, 7, 8, 9. However there will be no specific questions on material from Chapters 3, 4, or 5.

Do NOT neglect the course lecture notes. The course lecture notes posted on the web are very relevant to the examination questions, as you will see if you attempt the TRIAL EXAM Questions. [Minor bugs in the course notes, mostly typos, have been repaired on an ongoing basis, so that the latest postings are the cleanest.]

The Trial Exam Questions are typical of the kinds of questions you can expect, and you are strongly advised to try them.

All of the questions on the Final Examination are designed, not to test how smart you are, but the extent to which you have studied and understood the course material.

Tentative Examination Results will be posted on Monday morning (early afternoon at latest), April 26 at the Cpsc Main Office. Final grades will be submitted to the registrar on Friday April 30th, before noon.

Good Luck.

Welcome back! April 12, 2004

We have almost completed the material on orderd dictionaries in Chapter 8, and we will skip over Sections 8.4 and 8.5. [Skip Lists are uncommonly used.]

In Wednesday's class, we will cover Binary Search Trees, as applied to ordered dictionaries, essentially what is in Section 9.1, but no farther than the end of Section 9.1.2, and that will COMPLETE THE COURSE.

The class slot on Friday is available to you to go through the TRIAL EXAM questions, which will be posted as Class 35 Lecture Notes, the link to be found on the Lecture Notes page.

Welcome back! March 26, 2004

We have now completed Chapters 6 and 7. Remember to skip Section 6.3.5, and Section 7.3.6 when reviewing the material.

Remember also that the class notes posted on the web are an important resource.

Welcome back! March 08, 2004

There's a trivial typo in Assignment 3, but with serious consequences if not fixed. See the Discussion Page for the assignments.

Welcome back! March 03, 2004 /

The trial midterm exam plus answers is posted.

The MIDTERM EXAMINATION on Friday is CLOSED BOOK.

You should bring a calculator, but you may not use a hand-held computer (i.e. any computing device with a display screen). You may not use notes of any kind either.

Welcome back! March 01, 2004

MID TERM EXAMINATION

Please note the following:

1.The MT is on Friday March 05 in class at 10.00 am.

2. On for the exam is the material covered in class relating to Chapters 3, 4 and 5. The course lecture notes posted on the web are very relevant. [Minor bugs in the course notes, mostly typos, have been repaired on an ongoing basis, so that the latest postings are the cleanest.]

3. Currently we are at page 266 in Chapter 6 in the course, but the material on trees in Chapter 6 is NOT on for the MT. [It is best left to the Final, because of the number of recursive algorithms, which require more time to ponder than is available in a MT exam.]

REPRESENTATIVE TRIAL MIDTERM EXAM ON WEDNESDAY

There will be a representative TRIAL MT on Wednesday morning in class. The TRIAL MT will be posted on the web along with the other class notes by about noon on Wednesday.

Welcome back! Feb 23, 2004

The material in Chapter 6 needs to be pondered, especially the recursive methods. The class notes should help here.

With regard to the use of iterators with many of the methods in Chap 6, do not be overly concerned if you have not fully grasped the generalized iterator concept that the textbook uses.

To help you here:

(1) The class notes explain the iterators being used in the methods

(2) The class notes also show how we can carry out the same methods without using the authors' iterators.

So if you understand the methods in the notes that do not use iterators you will at least have understood essential tree processing. Iterators are on for the Mid Term Exam, but will not be emphasized, since they are a specific Java feature for manipulating data structures, and the book could easily have been written without them.

Welcome back! Feb 11, 2004

We have now finished Chapter 5, having covered Sections 5.1 and 5.2 and 5.5.
We are skipping Section 5.3, which is merely about a complex ADT that combines vector and list properties, and Section 5.4 which is merely an example, since you have a comparable example for Assignment 2.

Starting on Friday, Feb 13, we will cover trees in Chapter 6.

Welcome back! Jan 30, 2004

We will finish with Chapter 4 on Monday. Monday's class will begin with linked list stacks, and then we will go on to vectors in Chapter 5. After that we will study lists in earnest. Your next assignment involves a doubly linked list.

Note the following when studying Chapter 4:
You can read the Josephus problem, as solved by a queue, for fun.
Skip Section 4.3.5. You will learn about thread management in Cpsc457.
You can read section 4.4.3 for fun --linked list queues are not common.
Skip Section 4.5 --it just blurs the distinctions between the various kinds of data structures.

Never neglect to draw diagrams to enable clarity of understanding when analyzing data structures or programming with them. If you can't draw the diagram, you don't understand it.

Welcome back! Jan 19, 2004

Make sure you attend your labs to find out exactly what you have to do. Remember each TA has discretion over minor points in the assignment, and can decide how he wants those points covered.

We should finish the material in Chap 3 in Wednesday's class. Skip the section on Big Theta, but take a look at Big Omega.

On Friday, we can expect to start with Chapter 4. The chapter begins with a theoretical discussion of recursion, but since we've just had a big enough dose of theory to keep us digesting for a while, we'll skip that section for now, and go straight into stacks, and then queues. We'll probably come back to the section on recursion later, when a suitable opportunity, or a pressing need, presents itsself.

Welcome back! Jan 09, 2004

Your first assignment will be handed out in class (6 pages) on Monday. Jave programming information and discussions relevant to Assignment 1 is now posted on the Assignments Web page.

Welcome! Jan 02, 2004

The mid term exam is on FRIDAY, March 05.

You are supposed to have a reasonable knowledge of Java programming, particularly how to construct and use the following: super and sub classes; instance variables or objects; class, and instance methods, including constructors; class and instance data members; how to override constructors and methods. In a nutshell, you are supposed to know about programming with objects, and the abstract data types that subsume them.

All this is overviewed in Chapters One and Two of the textbook. If you have some problems here, make sure you attend the labs, where Java matters will be covered as needed. There will be 4 assignments, all using Java with data structures.

In the classes, we will very quickly get into Chapter Three about the analysis of the running times of algorithms that manipulate data structures. Then we will cover the various data structures, in the order covered in the text, beginning in Chapter 4.

So if you want to get a head start, read Chapter 3 repeatedly for the time being, and brush up on your Java.

Details of Assignment 1, likely about circular queues and double linked-list stacks, will be posted around about January 12.

Return to Computer Science Department Home Page

Return to James Bradley Home Page.