CMPS 101, Winter 2002
Algorithms and Abstract Data Types

• Course description: (from the course catalog) Studies basic algorithms and their relationships to common abstract data types. Covers the notions of abstract data types and the distinction between an abstract data type and an implemetation of that data type. The complexity analysis of common algorithms using asymptotic (big "0") notation is emphasized. Topics include sorting and searching techniques, basic graph algorithms, and algorithm design techniques. Abstract data types covered include priority queues, dictionaries, disjoint sets, heaps, balanced trees, and hashing. Familiarity with C, Java, and Unix is assumed.
• Course goals:
  • Learn to work with abstract data types in a style of programming that supports abstraction by doing examples in C and Java.
  • Learn about several specific data structures by doing examples in written assignments and programs.
  • Master asymptotic comparisons of functions using big-O, big-Theta, big-Omega, little-o and little-omega notations.
  • Learn basic introductory techniques for analysis of algorithms, including how to set up recurrences for divide-and-conquer algorithms and introduction to solving recurrences, by doing examples in the analysis of some typical or well-known algorithms.
• Desireable by-products of course:
  • Be able to easily handle the CS 101 section of the Comp Exam.
  • Be able to easily handle the data structures and analysis of algorithms section of the CS Subject GRE.
  • Be able to easily handle job interview questions about data structures and analysis of algorithms.
  • Master some basic programming design and development methodologies such as design, coding standards, and (optionally) pair programming.
• Week-by-Week Course Plan: (Note: exact timing and sequence subject to change. Future project, homework and quiz schedule to be announced.)
  • Week 1 (Jan. 3): Review of basic math preparation material. Chapters in text: Summations, Counting and Probability.
  • Week 2 (Jan. 10): Quiz 1, Introduction to algorithmic analysis. Chapters in text: Growth of Functions, Recurrences.
  • Week 3 (Jan. 17): Asymptotic notations, analysis of algorithms, recurrences, sorting algorithms. Chapters in text: Growth of Functions, Recurrences, Introduction (sections on sorting).
  • Week 4 (Jan. 24): Analysis and comparison of sorting algorithms, lower bounds for sorting. Chapters in text: Quicksort, section on lower bounds for sorting.
  • Week 5 (Jan. 31): Hash tables. Chapter in text: Hash Tables.
  • Week 6 (Feb. 7): Tree balancing schemes. Chapters in text: Binary Search Trees, Red-Black Trees.
  • Week 7 (Feb. 14): Quiz 2, Introduction to graph representation.
  • Week 8 (Feb. 21): Depth-first search, breadth-first search. Chapters in text: Elementary Graph Algorithms.
  • Week 9: (Feb. 28)Kruskal's algorithm, Prim's algorithm, Dijkstra's algorithm. Chapters in text: Minimum Spanning Trees, Single-Source Shortest Paths.
  • Week 10 (Mar. 7): Heaps. Chapters in text: Heapsort, Binomial Heaps, Fibonacci Heaps.
  • Week 11 (Mar. 14): Final review. Chapters in text: Nothing new (time left for overflow from previous weeks).