Correlate Topics to Readings from Textbooks

Intros to topics: Levitin; The Design and Analysis of Algorithms; [intros to chapters]

Theory of computation

• automata theory and languages: Appleby/!VandeKopple; Programming Languages: Paradign and Practice; Formal Languages 6 (245-282)

• finite state automata, regexps
  • DFSMs
  • NFSMs
  • REs
  • Equivalence of DFSM/NFSM
  • Equivalence of RE/FSM
  • Pumping Lemma

  • Sipser; Intro to the Theory of Computation; Regular Languages 1 (31-83)

  • Kinber/Smith; Theory of Computing: A Gentle Introduction; Finite Automata 2 (14-52)

  • Lewis/Papadimitriou; Elements of the Theory of Computation; Finite Automata 2 (55-111)

• context-free grammars, pushdown automata
  • CFGs
  • PDAs
  • Equivalence
  • (somewhere) BNF, ?CNF

    • BNF: in Friedman/Wand/haynes; Essentials of Programming Languages; Inductive Sets of Data 1 (1-38)

    • CNF: in Appleby/!VandeKopple; Programming Languages: Paradigm and Practice; Logic Programming 7 (285-323)

  • Sipser; Intro to the Theory of Computation; Context-Free Languages 2 (91-119)

  • Kinber/Smith; Theory of Computing: A Gentle Introduction; Context-Free Languages 3 (70-109)

  • Lewis/Papadimitriou; Elements of the Theory of Computation; Context-Free Grammars 3 (113-177)

• turing machines

  • Rawlins; Compared to What?; Turing Machines 7.3 (424-428)

  • Kinber/Smith; Theory of Computing: A Gentle Introduction; Turing Machines 4 (122-150)

  • Lewis/Papadimitriou; Elements of the Theory of Computation; Turing Machines 4 (179-244)

P, NP

• Definitions
• Sample problems
• Reductions (NP-complete, NP-hard)
• "Short certificates"

• Rawlins; Compared to What?; Infeasibility 7 (415-459)

Logic

• Propositional Logic
• Truth tables
• Karnaugh Maps
• Circuits
• Universality of NAND
• Predicate Logic

  • Sowa; Knowledge Representation; Predicate Calculus Appendix A.1 (467-476)

• Godel
• Knowledge Representation
• unification

• Truth tables, Karnaugh maps, circuits, NAND: http://cs-people.bu.edu/jconsidi/teaching/notes/cs210/node3.html Logic Design

• Winston; Artificial Intelligence; Logic and Theorem Proving 7 (205-249)

Data structures

• ADTs

  • Baase/Gelder; Computer Algorithms; Data Abstraction and Basic Data Structures 2 (70-100)

  • Johnsonbaugh/Schaefer; Algorithms; Data Structures 3 (99-111, 130, or 147)

• hash, bintree, union, heap

  • Aho/Hopcroft/Ullman; The Design and Analysis of Computer Algorithms; Data Structures for Set Manipulation Problems 4 (108-163)

• hash

  • Lewis/Denenberg; Data Structures and their Algorithms; Hashing techniques - Hashing Functions 8.3-8.5 (p265-290)

• graph

  • Lewis/Denenberg; Data Structures and their Algorithms; Graphs 12 (424-464)

  • Rawlins; Compared to What?; Graphs 5 (305-351)

• stack, queue ADT
• list, array (insert, member?, delete)
• binary tree for linear data storage
• tree traversal (pre-, in-, post-order)
• backtracking
• heap
• self-balancing trees

Algorithms

• search

  • Rawlins; Compared to What?; Searching 2 (81-144)

• select/rank

  • Rawlins; Compared to What?; Selecting 3 (159-217)

• sort

  • Rawlins; Compared to What?; Sorting 4 (231-287)

  • Baase/Gelder; Computer Algorithms; Sorting 4 (150-206)

  • Aho/Hopcroft/Ullman; The Design and Analysis of Computer Algorithms; Sorting and Order Statistics 3 (76-102)

  • just lower bounds

    • Lewis/Denenberg; Data Structures and their Algorithms; The Information-Theoretic Lower Bound 11.5 (393-396)

• "Analysis" (upperbounds, lowerbounds)

  • Rawlins; Compared to What?; Overview: Analysis 1.4 (16-26)

• Map-filter-reduce

  • Manis/Little; The Schematics of Computation; Mapping, Filtering, and Reduction 4.4 (206-220)

Orders of growth, O, theta notations

Logic Programming & Prolog

• Appleby/!VandeKopple; Programming Languages: Paradigm and Practice; Logic Programming 7 (285-323)

• Tucker/Noonan; Programming Languages: Principles and Paradigms; Logic Programming 9 (254-289)

• Louden; Programming Languages: Principles and Practice; Logic Programming 12 (539-578)

Lisp (Scheme)

• General how to

  • SICP 1.1, 1.3

• Cons, car, cdr; Lisp lists

  • SICP 2.2(thru 2.2.3)

• Lambda and higher order procedures
• Tail recursion
• Interpreters

• Friedman/Wand/haynes; Essentials of Programming Languages; Inductive Sets of Data 1 (1-38)

• Scheme, some func'l programming: Tucker/Noonan; Programming Languages: Principles and Paradigms; 8-8.5 (206-233)

Functional Programming as an approach

• Delayed evaluation

  • Louden; Programming Languages: Principles and Practice; Delayed Evaluation 11.5 (507-512)

• mathematics of func.programming; Y

  • Louden; Programming Languages: Principles and Practice; 11.7, 11.8 (520-529)

• Appleby/!VandeKopple; Programming Languages: Paradigm and Practice; Functional(Applicative) Programming 8 (325-374)

• Louden; Programming Languages: Principles and Practice; Functional Programming 11 - 11.2 (471-481)

The idea of Abstract Data Types (possibly with examples)

Lex/YACC