CS 234 lecture notes

Reference materials and sample programs are often copyrighted may be used only by the participants of the class.
  • 09/11 Introduction, goals of the course, Efficiency and Complexity, Reading: text chapters 1-2, Big-O Exercises, UNIX Intro Exercise
  • 09/13 UNIX help session (by Chris Ingram)
  • 09/18 ADT and data structures Imperative Programming Languages (or why does it not matter which one do I use), Naomi Nishimura's CS240 notes on why do we use simplified syntax to describe algorithms/data structures.
  • 09/20 Lists and Stacks, Recursion vs. Iteration, Lists with insertions, notes on the use of Pointers, Reading: text chapter 3, Assignment 1.
  • 09/25 Trees Reading: text chapters 4.1-2, 4.6.
  • 09/27 Search Trees and AVL Trees Reading: text chapters 4.3-4.
  • 10/02 Splay Trees Reading: text chapter 4.5.
  • 10/04 B-Trees, External storage considerations Reading: text chapter 4.7.
  • 10/09 Digital Search, Assignment 2.
  • 10/11 Priority Queues (Heaps) Reading: text chapters 6.1-4.
  • 10/16 Hashing, Reading: text chapters 5.1-4.
  • 10/18 Sorting, Reading: text chapters 7.1-7.
  • 10/23 More Sorting, Reading: text chapters 7.9-11.
  • 10/25 Assignment 1 and 2 solutions, review for midterm
  • 10/30 MIDTERM 4:30-6:20; click to find the room
  • 11/01 Graphs: Representations and Applications, Reading: text chapter 9.1. Assignment 3
  • 11/06 Graph Algorithms, Reading: text chapters 9.2, 9.6.1.
  • 11/08 Algorithm Design: Greedy Algorithms, Reading: text chapters 9.3, 9.5.
  • 11/13 Network Flow Algorithms, Reading: text chapter 9.4.
  • 11/15 Algorithm Design: Divide and Conquer, Reading: text chapter 10.2.
  • 11/20 Algorithm Design: Dynamic Programming, Reading: text chapter 10.3.
  • 11/22 Algorithm Design: Hard Problems, Reading: text chapters 9.7, 10.5.
  • 11/27 Introduction to NP-completeness,
  • 11/29 slack, review for final, etc.
    • To print the slides 4-on-a-page download the file and then use psnup -n4 infile.ps outfile.ps.