BU CAS CS 113 - Spring 2001

Teaching Fellow

Joni Alon, jalon@cs.bu.edu
Office hours: Wednesday 4-6pm, room MCS B46 or undergraduate lab when assignments are due the following day.
Office phone: 353-5227 (room MCS 207)

Lab Meeting Times

Labs

This section contains materials related to lab sections. Reading this material is not considered a substitute for attending labs. In some cases, there will be material that you must read before ("Prerequisites") or after ("Postrequisite") labs.

Lab 1: 1/22, 1/29

• Prerequisite:
  1. Getting an Account
  2. Using your Account
• Lab: Intro to UNIX
• Postrequisite: Learn all commands and concepts in the UNIX Reference except gdb and make.

Lab 2: 2/5

• Lab: Functions (slides) (solution)

Lab 3: 2/12

• Lab: Classes (solution)

Lab 4: 4/20

• Prerequisite:
  1. Compiler, Linker and Run-Time Errors
  2. Compiling inside Emacs (only that section of that web page)
• Lab: Debugging with the GDB debugger

Lab 5: 2/26

• Lab: Modules, Separate Compilation, Using Make Files (slides)

Lab 6: 3/12

• Background: The C String Library - string.h (slides)
• Lab: A String Class: Part I (slides) (solution: mystring.h and mystring.cpp)

Lab 7: 3/19

• Lab: Deleting from a linked list

Lab 8: 3/26

• Prerequisite: Pointers
• Lab: Dynamic memory in C++

Lab 9: 4/2

• Prerequisite: Deleting from a singly-linked list
• Lab: Deleting from a doubly-linked list
• Lab: Program Arguments

Lab 10: 4/9, 4/18

• Lab: Templates (slides) (solution: list.h, list.tem, and listtest.cpp)

Lab 11: 4/23

• Lab: Search by hashing

Lab 12: 4/30

• Prerequisite: Graphical Sorting Algorithms Demo
• Lab: Heap Sort

Sample Solutions

For each assignment I will post solutions of two or three students who did a great job on their assignments (typically a score of 100).

• p4 source code: the following are solutions of Tara Marie and Marna Eckels:
  Tara Marie: rational.cpp
  Marna Eckels: ratioanl.cpp
  Driver program used for testing: rationalDriver.cpp
  Makefile used: Makefile
• p5 source code: the following are solutions of Sumeet Tewani and Sonya Johnson:
  Sumeet Tewani: list.h, list.cpp, main.cpp
  Sonya Johnson: list.h, list.cpp, main.cpp
  Test files: test1, test2, test3, test4, test5
  Correct answers: ANSWERS
  Makefile used: Makefile
• p6 source code: the following are solutions of Likai Liu and Matthew Evans
  Likai Liu: list.h, list.cpp, polynomial.h, polynomial.cpp, main.cpp
  Matthew Evans: list.h, list.cpp, polynomial.h, polynomial.cpp, main.cpp
  Test files: test1, test2, test3, test4, test5, test1.extra, test2.extra
  Correct answers: test1.result, test2.result, test3.result, test4.result, test5.result, test1.extra.result, test2.extra.result
  Makefile used: Makefile

Other Useful Links

p8:

• Sorting - You may use the simpler quadratic sorting algorithms such as selection sort, bubble sort, or insertion sort to sort your strings. For small input size there is little difference between the simple quadratic algorithms and the more sophisticaetd n*log(n) algorithms. In our case the input size is the string length which is typically only a few characters.
• The first 10,000 primes - for the final version you submit select a prime close to 10,000. Since there are ~25,000 words in /usr/dict/words, the load factor alpha ~= 25,000/10,0000 = 2.5. This means that on average there will be 2.5 collisions, or the average size of a list in the hash table is 2.5.
  Q: How do we know how many words there are in /usr/dict/words ?
  A: We use the UNIX command wc that stands for word count
  wc /usr/dict/words
  By default wc returns the number of words, the number of lines, and the number of bytes in the file.
• Interpreting strings as natural numbers. ASCII codes.
• hash function - takes a string represented with a character array and returns an integer value in the range [0..TABLE_SIZE-1]. If you represent your string with the string class you will have to modify this function, but the idea remains the same.

Grades