Winter 2009 SYSC 2002 Data Structures and Algorithms

Carleton University
Department of Systems and Computer Engineering

SYSC 2002 Data Structures and Algorithms

Winter 2009

Lecturer and Course Details

Section D: Dr. Lynn Marshall, Room 4230 ME, lynnmar@sce.carleton.ca
Office Hours: Wed 10:15-11:15am; Thu 2:45-5:15pm
Lectures: Tue/Thu 10:05-11:25am TB210

Labs

Lab tests: Lab tests will be held during regular lab periods approximately bi-weekly. All lab tests are in ME4390/ME4377. (Lab tests start Wed Jan 21st -- see term at a glance below for more details.)

Lab Section D1: Wed 9:35-11:25am
Lab Section D2: Thu 3:35-5:25pm

Note that the above labs run only the dates that there are lab tests.

Open Labs: On the weeks when assignments are due (see "term at a glance" below), there will be open labs to meet with the TAs scheduled on Monday afternoon / evening.

Lab Schedule (updated Jan 20th; open labs moved to MC5010)

Course Material

Course Outline (updated January 6th)

Term at a Glance (added Dec 1st; updated Feb 18th: final exam added)

Assignments and Labs

Examples

Marks

News and Announcements

Apr 15th: The updated marks for the assignments, including each student's total (out of 10), have been posted in the marks folder above.
Apr 8th: The marks have been released for assignment #11.
Apr 7th: The marks have been released for assignment #10.
Apr 7th: My pre-exam office hours will be:
- Wed Apr 15th 10am-noon
- Fri Apr 17th 10am-noon
- Tue Apr 21st 9-11am
- Wed Apr 22nd 9-11am
You are also, of course, welcome to contact me via e-mail.
Apr 7th: A sample solution has been posted for assignment #11.
Apr 4th: The lab test marks have been corrected (one of the columns of my spreadsheet was missing). See "Marks" link above.
Apr 4th: The marks have been posted for assignments (#1-9) and lab tests (#1-5). See "Marks" link above.
Apr 3rd: The description of the grammar for assignment #11 and what the sample executable actually accepts were not quite the same. I've updated the assignment with a clarification about this, and posted two different sample executables. You can write and submit either version of the grammar, just ensure that you indicate at the top of your header file which version you did as well as the grammar. It will be assumed that you did the first version (i.e. matching with v1 of the sample executable) if you do not specify.
Apr 2nd: The marks have been released for lab test #5.
Mar 31st: My office hours are cancelled for Wed Apr 1st. Sorry for any inconvenience. Feel free to contact me via e-mail, or drop by my extended office hours on Thu Apr 2nd: 1:15-5:15pm.
Mar 31st: A sample solution has been posted for assignment #10.
Mar 31st: Both versions of lab test #5 and their solutions have been posted.
Mar 30th: There is an old final exam in your notes. Here is that exam and some other old final exams. Solutions to exams will not be posted, but we will cover some questions in the last two lectures. Note that you can check your solutions by running the code.
Mar 30th: Here is the crib sheet that you will be given for the final exam. No other aids are allowed (i.e. the exam is closed book, NO calculators).
Mar 28th: The marks have been released for assignment #9.
Mar 24th: A sample solution has been posted for assignment #9.
Mar 23rd: The supplementary files for assignment #11 have been updated so that they all use String2002 (not string).
Mar 20th: The marks have been released for assignment #8.
Mar 19th: The marks have been released for lab test #4. Remember that it is out of 10, and the maximum mark is 15!
Mar 18th: Thanks to Walter for finding a bug in the sample executable for assignment #9. The sample exe and skeleton.cpp have been re-posted with the bug corrected (in the LR rotation method, if C's balance factor was 0, it set C's balance factor to 0, instead of setting B's balance factor to 0).
Mar 17th: The two missing files (Tree.h and Treetest.cpp) have been added to assignment #9.
Mar 17th: A sample lab test #5 has been posted. Lab test #5 will be on trees, and will involve recursion, although recursion is optional, not required. Your lab test #5 will involve 3 parts and be marked out of 15, i.e. there are 5 bonus marks, just like for lab test #4. We will go over the sample lab test #5 in class on Tue Mar 24th.
Mar 17th: A sample solution for assignment #8 has been posted, along with the updated skeleton file for assignment #9 (now that assignment #8 is done).
Mar 13th: The marks have been released for assignment #7.
Mar 13th: The questions, sample executables, and sample solutions for lab test #4 have been posted for both sections.
Mar 12th: The last two assignments have been posted. Assignment #10 is on hashing (Chapter #15) and #11 is on parsing (Chapter #17).
Mar 11th: If you have had an outstanding TA for this course (or any other Systems and Computer Engineering course), please nominate that TA for a TA Excellence Award. Here is the one page nomination form. The deadline for submissions is Tue Mar 31st.
Mar 10th: A sample solution for assignment #7 has been posted.
Mar 10th: Assignment #9 has been posted. skeleton.cpp will be posted after assignment #8 is due.
Mar 8th: The marks (as of 5pm today) have been posted in the marks folder above for assignments #1-6, lab tests #1-3, and the midterm. If you notice any errors or omissions, please let me know.
Mar 6th: The marks have been released for assignment #6.
Mar 4th: Lab test #4 (Wed Mar 11th & Thu Mar 12th) will be on linked lists and recursion. A sample lab test #4 has been posted. We will go over this in class on Tue Mar 10th. You are strongly encouraged to try it on your own first.
Mar 3rd: Some typos in assignment #8's skeleton.h file (that will cause compile errors!) have been corrected. Thanks to Walter Waldron for pointing this out.
Mar 3rd: Assignment #8 has been posted.
Mar 3rd: A sample solution has been posted for assignment #6.
Mar 3rd: The questions, sample solutions and TA test programs for lab test #3 have been posted.
Mar 1st: The marks have been released for lab test #3. Note that the two remaining lab tests will be out of 15, but the marks will be recorded as if they are out of 10 (i.e. 5 bonus marks on each). That will give those of you who have been struggling a chance to improve your lab and term marks.
Mar 1st: The marks have been released for assignment #5.
Feb 24th: A sample solution has been posted for assignment #5.
Feb 22nd: Due to last week being reading week, I've extended the deadline for providing documentation if you missed the midterm for a valid reason. The deadline is now the end of class (11:25am) on Tue Feb 24th. No exceptions!! Your note can be given to me directly or turned in to the Systems and Computer Engineering Department office (ME4456) during their office hours. If you submit your note to the office, ask the staff to write the date and time on the note, or it will not be accepted. Notes slid under my office door will not be accepted.
Feb 22nd: The midterms will be returned in class on Tue Feb 24th. You must be present to get your midterm (i.e. you may not pick up a midterm for anyone else). If you wish to submit your midterm for remarking, please note the following:
- The deadline for submitting your midterm for remarking is the end of class on Tue Mar 3rd.
- All midterms submitted for remarking will be returned in class on Thu Mar 5th, not sooner!
- Midterms will not be remarked unless accompanied by a detailed written explanation of which questions you want remarked and why (e.g. comparing your answer to the marking scheme, what was marked incorrectly).
- Midterm remarking will be done by me, not by the TAs.
- I reserve the right to look at all questions, not just those you asked to have remarked, and thus your mark could go up, down or stay the same.
Feb 22nd: The sample solutions for the midterm have been posted on the "Assignments and Labs" web page.
Feb 22nd: Assignment #7 has been posted. You will be able to complete this assignment once we have covered recursion.
Feb 20th: The marks have been released for assignment #4.
Feb 18th: The "term at a glance" (above) has been updated with the date/time of the final exam: 9am-noon Thu Apr 23rd.
Feb 16th: The marks (as of 4pm Mon Feb 16th) have been posted in the "Marks" folder (see above) for the first three assignments and the first two lab tests.
Feb 13th: Anyone who missed the midterm due to illness must provide a doctor's note dated no later than today (the day after the midterm), and delivered to me (or my mailbox in the department office: ME4456) within five working days of the exam.
Feb 10th: The marks have been released for lab test #2 for D1 and D2.
Feb 10th: A sample solution has been posted for assignment #4.
Feb 10th: Assignment #6 has been posted. (In this assignment you redo #5 with linked lists instead of dynamically allocated arrays.)
Feb 6th: Lab test #3 will be held the week after reading week. Once we've covered the first part of chapter 10 (Tue Feb 10th), you will be able to do the sample lab test that is now posted. We will go over this in class on Tue Feb 24th.
Feb 6th: Both lab test #2s and their solutions have been posted.
Feb 5th: The marks for assignment #3 have been released. Along with the sample solution, you'll now find the file that the TA used to do his testing. Read "plsREADME.txt" to see how to run this with your code. This test program gave you a mark out of 8, which was translated to a mark out of 4 as follows:
- 4: 8/8 on the tests
- 3: 5-7/8 on the tests
- 2: 1-4/8 on the tests
- 1: 0/8 or doesn't compile
- 0: Doesn't compile and no comments and/or wrong file(s) submitted
Feb 5th: The room assignments for the midterm (Thu Feb 12th 10:05am) are as follows:
- TB210: Last Names starting with A through O.
- SA502: Last Names starting with R through Z.
Note that your last name (according to Carleton Central) is the name listed first in the lab lists posted on the Assignments and Labs web page.
Feb 3rd: A mistake in the posted sample solution for sample lab test #2 has been corrected.
Feb 3rd: A sample solution for assignment #3 has been posted.
Feb 3rd: Assignment #5 has been posted. While you already know most of the material required for Part I, you will need some material from Chapter #9 to complete Part II.
Feb 1st: As some students were told that they didn't need to put comments in lab test #1, the deductions for missing comments have been reversed. Note, however, that in future all programs (assignments, lab tests, and exams) without comments will have marks deducted.
Jan 31st: The marks have been released for assignment #2.
Jan 29th: Several students have pointed out that the main program for assignment #3 isn't very "robust", e.g. it doesn't handle things very well if you enter -2 for the number of forces, etc. However, as you are writing the Vector class (and not changing the main program), don't worry about the deficiencies of the main program, just ensure that your class works as per the description and comments given in the main program.
Jan 29th: If anyone is looking for a tutor for SYSC 2002, you can contact Alex Hudici.
Jan 29th: The midterm will be held during the regular lecture time (10:00-11:30am) on Thu Feb 12th. It will cover all material from the lectures and notes up to and including Chapter #8 (Pointers). It will also cover lab tests #1 and #2, as well as assignments #1 to #4. Note that doing the old midterm #1 near the end of the notes is good preparation, but that midterm did not cover Chapters #7 or #8.
Jan 27th: A sample lab test #2 has been posted on the "Assignments and Labs" page. We will do this in class on Tue Feb 3rd, so I recommend trying it on your own before then.
Jan 27th: Assignment #4 has been posted. You will be able to complete this assignment once we have covered Chapter 7 (IntBag).
Jan 27th: A sample solution to assignment #2 has been posted.
Jan 27th: If you have questions about the marking of any of your assignments or labs, you must contact the TA who did the marking. (From "view" click the "marker" button and it will give you the name and e-mail address of the TA who did the marking.) Please do not get me involved unless you and the TA have been unable to resolve your difficulties.
Jan 27th: The marks have been released for lab #1. Your marks are available by viewing your lab using the D1 or D2 lab section of the regular (non-lab) submit program. If you neglected to set up an account in this system, one has been created for you with your password equal to your student number. Please ensure that you change your password ASAP. For future reference, to get full marks you must always comment your code! (This is clearly stated in the marking guidelines and has been mentioned in class several times.) If you had any problems with the lab, ensure that you consult the sample solutions posted on the web site.
Jan 26th: The marks have been released for assignment #1.
Jan 22nd: The two questions and sample solutions for the first lab test have been posted.
Jan 20th: Please note that effective Mon Jan 26th, the open labs have been moved to MC5010.
Jan 20th: For assignment #2, you may not change the main program in the skeleton file unless you are adding extra functionality, and even then, you should make only additions, not changes.
Jan 20th: A sample solution for assignment #1 has been posted.
Jan 20th: Assignment #3 has been posted. You will be able to complete this assignment after we cover the second half of chapter #3. (I recommend focusing on the sample lab test #1 and assignment #2 until after you have written your first lab test.)
Jan 19th: The lab lists have been updated again (see the top of the "Assignments and Labs" web page). Please double check that your name is in the correct section.
Jan 15th: The lab schedule (showing open labs and formal labs and their dates) has been added near the top of this page. Students are reminded that open labs (for help with assignments, etc.) start on Monday (1-6pm), and the first lab test will also be next week (Wednesday or Thursday).
Jan 13th: A sample lab test #1 has been posted on the Assignments and Labs web page. We will go through this test in class on Tue Jan 20th. You should try it on your own (after we've covered the first half of Chapter 3) before then!
Jan 11th: The lab lists have been updated. See the top of the Assignments and Labs web page for the latest lists.
Jan 11th: Assignment #2 has been posted. You will be able to do this assignment once we have completed Part 1 of Chapter 3.
Jan 9th: I have a couple of students on the waiting list for lab D2, as they have a course conflict with lab D1. If anyone currently in D2 would like to switch to D1, I'd be happy to accommodate you. Just send me an e-mail! Thanks.
Jan 8th: The typo in the assignment #1 skeleton.cpp file has been corrected.
Jan 8th: Things to do for SYSC 2002 this week and next (we will talk about these in today's class):
- Buy the notes (preferably before today's class).
- Set up your Dev-C++ environment:
  - If you don't have Dev-C++ on your computer(s) of choice yet, the link for downloading it can be found near the top of the "Assignments and Labs" web page. (Dev-C++ is already installed on the lab machines.)
  - Set the Dev-C++ compiler options as per the instructions in Chapter 2 (2nd paragraph of page 2-8) of the notes.
- Set up the Submit program:
  - Read the "electronic assignment submission guidelines" by following the link near the bottom of the "Assignments and Labs" web page.
  - Download the SYSC 2002 submit program from that web page, and save it on your computer. (Or just run it from there.)
  - Set up an account for both SYSC 2002 Assignments and for SYSC 2002 Dx Lab (where x is 1 or 2, corresponding to the lab that you are in).
    - It is strongly recommended that you use the same password for both.
    - E-mail me if you forget your password. (Test your password at least a day before the due date/time.)
    - If you are on the waiting list for switching lab sections, you can set up accounts for both the lab section you are currently in and the one you want to switch to.
    - Note that you will also have to set up another submit lab account for use in the labs when you write the first lab test. (This is because the lab version of the submit system is different from the regular version.)
- Experiment with creating a Dev-C++ Project:
  - Create a folder to use for your project.
  - Go to the "Examples" web page and download the sample files (third bullet) into that folder.
  - Download a copy of the Dev-C++ version of "stdstuff.h" from the link near the bottom of the "Assignments and Labs" web page and put it into the same folder.
  - Follow the instructions in Chapter 2 (pages 2-8 and 2-9) to create your project, and to re-open it after exiting from Dev-C++.
  - For further practice using a Dev-C++ project (you will have to use one for the first lab test), use a Dev-C++ project for assignment #1 (see next point).
- Get started on assignment #1.
Jan 8th: The SYSC 2002 submit program is now available. You can also find a link to it from the bottom of the "Assignments and Labs" web page, where you will also find the submit program instructions.
Jan 6th: The lab lists have been posted on the Assignments and Labs web page. Note that these are the official lists (not the ones in Carleton Central). Please note that D2 is now full. I will start a waiting list, if required.
Jan 6th 1pm: Course notes are now available from the IEEE office (ME4238).
Jan 6th: The course notes for SYSC 2002 for Winter 2009 will be available from the IEEE office (ME4238) starting the evening of Tue Jan 6th. The price is $13 for IEEE members and $16 for non-members. The Winter 2009 notes are identical to the notes for Fall 2008. Note, however, that there have been some significant changes to the notes for 2008/2009, including the addition of questions at the end of many of the chapters. It's recommended that you have the notes for the second lecture (Thu Jan 8th). The other references listed in the course outline provide supplementary material, and are not required.
Dec 31st: Assignment #1 has been posted (see Assignments and Labs link above).
Dec 31st: A note will be posted here when the SYSC 2002 submit programs are available for download. Note that we will be using a sophisticated program to check for plagiarism among assignment solutions submitted by students. Remember that you may discuss concepts with your friends, but *not* the code itself. There will be a zero tolerance policy for plagiarized assignments! Here is the comment block from ECOR 1606 that you should put at the top of your files submitted for assignments and lab tests.
Dec 31st: A student e-mailed me asking for suggestions as to how to succeed in SYSC 2002. I thought it was a good idea to post the response here:
- Attend the lectures and ask questions (if you have a question, likely others have the same one).
- Do all the assignments and see the TAs during the help sessions if necessary.
- Do the exercises and sample exams in the notes.
- After each lab test, do the other one (they will both be posted on the web site).
- Come to my office hours if you need help.
- If you are finding programming to be a real challenge, find a tutor as some detailed 1-on-1 sessions can really help.
- Don't fall behind, as it will be very difficult to catch back up as all the material builds on previous material covered.
Dec 31st: Look over the "Term at a Glance" above for important dates, such as when lab tests will run, assignment due dates, midterm date, etc.
Dec 31st: A link to the course outline is given above. Note that to save trees, hard copies will not be distributed in class.

Updated April 15^th, 2009