General topics: Formal methods of syntactic specification of programming languages. Various semantic aspects of modern programming languages: scoping, binding, and parameter passing. Modularity and abstraction mechanisms of modern programming languages. Typing and polymorphism. Exception handling. Declarative programming languages. Comparison of modern programming languages and paradigms. (General introductory reading: Sebesta, Ch. 1-2; Sethi, Chs. 1-2; Bal and Grune, Ch. 1; for functional programming, Paulson, Ch. 1.)

Specific topics:

Syntax (Sebesta, Ch. 3-4; Sethi, Ch. 2).
1. Context-free grammars; BNF/EBNF; regular and non-regular grammars and languages; regular expressions.
2. Ambiguous context-free grammars; disambiguating context-free grammars; expressing precedence and associativity.
3. Prefix, postfix, and infix notation.
Imperative programming (Sebesta, Chs. 5-10, 14; Sethi, Chs. 1, 4-5; Bal and Grune, Ch. 2).
1. Syntax and semantics of simple statements and control structures.
2. Run-time storage: activation records; global, stack, and heap allocation; dangling pointers.
3. Use of names: bound, free, and binding occurrences; static and dynamic scope.
4. Parameter-passing semantics: by value, by reference, by value-result, by name, and macro expansion.
5. Type checking; strongly-typed languages.
6. Implementation issues: compilers vs. interpreters, phases of a compiler, tail recursive subroutines and their implementation optimization.
7. Non-local control flow: exceptions.
Functional programming (Paulson, Chs. 1-5; Sebesta, Ch. 15; Sethi, Chs. 8-10; Bal and Grune, Ch. 4).
1. The functional style of programming, recursion.
2. Functional data structures: lists and tuples, data constructors, pattern matching.
3. Parametric polymorphism; type inference.
4. Functions as `first-class': as parameters; as results; anonymous functions; curried functions, partial applications; functional types; standard higher-order library functions, especially list functions (composition, map, filter, the fold functions, etc.).
5. Evaluation rules and parameter-passing semantics: eager (a.k.a. call-by-value, strict), by name, lazy (a.k.a. call-by-need).
Objects (Sebesta, Ch. 12; Sethi, Chs. 8-10; Bal and Grune, Ch. 4).
1. Classes and objects; stack vs. heap allocation.
2. Inheritance.
3. Method polymorphism: static vs. dynamic dispatch.

Sample code: Candidates should be able to read and write C++, ML, and Java sample code. Code may also be presented using standard constructs with a description of intended language properties (three examples: `an object-oriented language with static scope and dynamic dispatch'; `a functional language with monomorphic types and by-name parameter passing'; `an imperative language with dynamic scope and, by default, by-reference parameter-passing semantics, or by-value semantics when a parameter is declared with the keyword cbv'.

References. Currently Sebesta's and Paulson's texts are used in teaching CSC447. However there are several acceptable and good references for the material of this core examination; candidates are encouraged to use the study material which best suits them. Some recent texts include:

Henri Bal and Dick Grune, Programming Language Essentials (Addison-Wesley, 1994).

Lawrence C. Paulson, ML for the Working Programmer (Cambridge University Press, second edition, 1996).

Robert W. Sebesta, Concepts of Programming Languages (Addison-Wesley, fifth edition, 2002).

Ravi Sethi, Programming Languages: Concepts and Constructs (Addison-Wesley, 1996).

SE 455 Software Development Methods

Topics

object-oriented analysis and modeling
- principles and concepts (Booch Chapters 1-4)
- notations (Booch Chapter 5)
- case studies (Booch Chapters 8-9)
design patterns
- creational patterns (Gamma Chapter 3)
- structural patterns (Gamma Chapter 4)
- behavioral patterns (Gamma Chapter 5)
implementation techniques in C++
- assertions, exceptions, templates, reference count, memory management
testing and debugging techniques
other related issues
- programming style
- incremental development
- configuration management

Commonly used Texts

Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides, Design Patterns - Elements of Reusable Object-Oriented Software, Addison-Wesley, 1995.

Grady Booch, Object-Oriented Analysis and Design with Applications, 2/ed. Benjamin/Cummings. 1994.

References

Stanley B. Lippman, C++ Primer, 2/ed. Addison-Wesley, 1991.

Taligent's Guide to Designing Programming - Well-Mannered Object-Oriented Design in C++, Addison-Wesley, 1994.

Syllabus

CSC 491 Design and Analysis of Algorithms

Course Description

Methods of designing algorithms including divide-and-conquer, the greedy method, dynamic programming, and backtracking. Emphasis on efficiency issues. NP-completeness and approximation algorithms. (Prerequisites: CSC 416 and 417 or instructor consent.)

Topics

1. Big-oh, omega, theta notations; mergesort and analysis; divide-and-conquer design method, recurrence relations for divide-and-conquer algorithms (Chapters 2, 3, 4)

2. Dynamic programming: matrix chain multiplication, longest common subsequence (Chapter 15)

3. Greedy algorithms: activity-selection problem, Huffman codes (Ch 16)

4. Backtracking: n-queens, graph coloring, sum of subsets (supplementary material).

5. NP-completeness (Chapter 34)

6. Approximation algorithms: vertex-cover problem, traveling-salesman problem (Ch 35)

Reference

Cormen, Leiserson, Rivest, and Stein; Introduction to Algorithms, 2nd edition; MIT Press, 2001.

SE450 Object-Oriented Software Development

Primary References:

Gamma, et al, Design Patterns
Fowler, UML Distilled

Secondary References:

Shalloway and Trott, Design Patterns Explained: A New Perspective on Object-Oriented Design
Booch, Rumbaugh and Jacobson, The Unified Modeling Language User Guide
Martin, Principles and Patterns

Topics:

OO Concepts and their manifestation in Java.
- Basics:
  - Abstraction and Encapsulation
  - Visibility and Packages
  - Object versus Class
  - Instance Methods versus Class Methods versus Constructors
- Values and References:
  - Value versus Reference (Base Types versus Wrapper Classes)
  - Deep versus Shallow Copying/Equality
  - Inner Class Idiom and Anonymous Inner Classes
- Subtyping:
  - Subtype Polymorphism (Subtyping)
  - Late (Dynamic) Binding versus Early (Static) Binding
  - Static Overloading and Coercion versus Dynamic Casting
  - Use of this and super
- Code reuse:
  - Inheritance (subclassing)
  - Overriding versus Hiding (Shadowing)
  - Subtyping versus subclassing
  - Single versus multiple inheritance
  - Interface (pure abstract) versus Abstract versus Concrete versus Final
  - Composition versus Inheritance
Design concepts
- Process
  - Iterative Development Process
  - Refactoring
  - Testing: Black/White box, Unit/System testing
- Class Design Principles
  - Coupling and Cohesion
  - Principle of Least Knowledge (Law of Demeter)
  - Dependency Inversion Principle - depend upon abstractions, not concretions - design to interface
  - Principle of Substitutivity (Liskov Substitution Principle)
  - Design by Contract versus Defensive Programming
- Package/Framework Design Principles
UML
- Class Diagrams
- Object Diagrams
- Sequence Diagrams
Design Patterns
- Creational Patterns
  - Static Factory Method
  - (Polymorphic) Factory Method
  - Static Class (class with only static members)
  - Singleton
- Behavioral Patterns
  - Command
  - Iterator
  - Observer
  - Strategy
  - Template Method
  - Visitor
- Structural Patterns
  - Adapter
  - Composite
  - Decorator
- System Patterns
  - Model-View-Controller (MVC)