15-211 Fall '97 Home Page

Welcome to the WWW homepage for CMU 15-211, ``Fundamental Structures of Computer Science I.'' The course is being taught by Professor Avrim Blum and Professor Seth Goldstein. The TA's for the course are Carl Burch, and Craig Damon, and Sam Perman. The course secretary is Dorothy Zaborowski.

Lecture is Tues, Thurs 12:00-1:00 in DH2315. Recitations are Mon, Wed in SC203.

How to access the course staff:

• Prof. Avrim Blum: avrim+@cs.cmu.edu, 4107 Wean Hall, Office hour: Tue 2:00-3:00
• Prof. Seth Goldstein: seth+@cs.cmu.edu, 7122 Wean Hall, Office hour: Wed 4:00-5:00
• Carl Burch, TA: cburch+@cs.cmu.edu, 4617 Wean Hall, Office hour: Fri 9:00-10:00
• Craig Damon, TA: cdamon+@cs.cmu.edu, 8205 Wean Hall, Office hour: Fri 11:00-12:00
• Sam Perman, TA: sp4b+@cs.cmu.edu, 4615-26 Wean Hall, Office hour: Mon 12:30-1:30
• Dorothy Zaborowski, Course Secretary: x8-3779, 4116 Wean Hall.

Newsgroups:

• cmu.cs.class.cs211.announce (for announcements by course staff).
• cmu.cs.class.cs211.discuss (for general discussion).

Handouts in PostScript format:

1. 15-211 Course Information guide
2. C++ programming style guidelines
3. C++ language basics I
4. C++ language basics II
5. Lab 1
6. Assignment 1
7. Debugging with Purify
8. Assignment 2
9. Old quiz 1
10. Assignment 3
11. Old midterm
12. Assignment 4
13. Assignment 5
14. Old quiz 2
15. Assignment 6
16. Assignment 7
17. Old quiz 3

Handouts in HTML format:

1. 15-211 Course Information guide, including
   • Electronic handin procedures
   • Cheating/collaboration policy
   • Who to see about problems
   • Course schedule
2. C++ programming style guidelines
3. C++ language basics I
4. C++ language basics II
5. Debugging with Purify
6. Midterm answers

Outlines for the lectures and recitations:

• Lecture 8/26: Intro to 15-211
• Rec 8/27: C++ I/O, arrays, strings
• Lecture 8/28: C++ programming and recursion. (program 1, program 2)
• Lecture 9/2: call stack, recursion, C++ classes. (stack.h, stack.C, main.C)
• Recitation 9/3: .C vs .h, Makefiles, the programming process
• Lecture 9/4: Stacks, Classes, Stacks with linked lists
• Recitation 9/8: Linked lists, ptrs, recursion, constructors, destructors. More notes
• Lecture 9/9: Inheritance, derived classes, ADTs
• Recitation 9/10: Inheritance, virtual functions, dynamic and static types, pure virtuals
• Lecture 9/11: depth-first search, breadth-first search, stacks and queues
• Recitation 9/15: more on queues and breadth-first search, friend classes, char **'s
• Lecture 9/16: analyzing correctness of programs, Loop Invariants
• Recitation 9/17: More examples of analyzing code, loop invariants
• Lecture 9/18: Program testing
• Recitation 9/22: Go over quiz
• Lecture 9/23: Analyzing running times, asymptotic analysis, order notation
• Recitation 9/24: Examples of order notation, analyzing running times
• Lecture 9/25: Dynamic Programming and Memoizing
• Recitation 9/29: More examples of DP and Memoizing
• Lecture 9/30: Trees, Tree traversals (inorder, preorder, postorder), Binary search trees
• Recitation 10/1: BSTs: examples, sorting, deletions
• Lecture 10/2: Sorting: selection sort, insertion sort, the qsort library function
• Recitation 10/6: Sorting lower bounds
• Lecture 10/7: Divide-and-Conquer Sorting: mergesort, quicksort. Intro to recurrences
• Recitation 10/8: Review for midterm
• Lecture 10/14: Heaps and Heapsort (PostScript)
• Recitation 10/15: Data compression and Ziv-Lempel, Median-finding with QuickSelect
• Lecture 10/16: Priority queues, bucket sort, radix sort
• Recitation 10/20: Recurrences, heaps
• Lecture 10/21: Hashing
• Recitation 10/22: destructors and memory
• Lecture 10/23: Hashing, contd. Different collision-resolution methods
• Recitation 10/27: Game tree search and hashing examples
• Lecture 10/28: Growing a hash table, intro to balanced search trees: 2-3 trees
• Recitation 10/29: Quiz review (here are more notes)
• Lecture 10/30: AVL trees - maintaining height O(log n)
• Recitation 11/3: Recurrences, Alpha-Beta search
• Lecture 11/4: Finish up search trees: 2-3 tree examples, tree rotations, and "tries"
• Recitation 11/5: Finish up search trees
• Lecture 11/6: Graphs: definitions, modeling problems, representations, planar graphs
• Recitation 11/10: About assignment 6
• Lecture 11/11: Graphs searching: DFS, BFS, and intro to priority-first search
• Recitation 11/12: Adjacency matrices, BFS, DFS
• Lecture 11/13: Shortest paths in weighted graphs, priority queues
• Recitation 11/17: More priority-first search
• Lecture 11/18: Min Spanning Trees, Shortest paths with negative edges, Min cost matching
• Recitation 11/19: Floyd's and Warshall's algorithms, MSTs
• Lecture 11/20: Finite Automata (Finite State Machines)
• Recitation 11/24: Old quiz + FSMs
• Lecture 11/25: KMP string matching
• Recitation 12/1: KMP string matching, cont.
• Lecture 12/2: Regular expressions and regular languages
• Lecture 12/4: Review and 2-player zero-sum games

Other relevant information sources:

• An intro to using gdb within Emacs by Doug Rohde.
• An Introduction to UNIX and the Andrew system.
• More help on all sorts of topics for the SUNs, HPs, and DECstations.
• The DDD manual with pictures and without pictures.
• The DDD Home Page.
• FTP site for Standish, "Data Structures, Algorithms, and Software Principles in C" including errata and source code.
• Helpful newsgroups:
  • Comp.Std.C
  • comp.Lang.C
  • Comp.Std.C++
  • Comp.Lang.C++