CSC 425 (Discrete Mathematics, Data Structures and Algorithms)

CAM Ph.D. Qualifying Exam
Computer Science portion for September 2004 (Q044)

Syllabus:

The exam will cover material presented and material related to CSC 425, and 437. The following lists provide topics that will be covered.

CSC 425 (Discrete Mathematics, Data Structures and Algorithms)

·  Complexity Measures

·  Asymptotic notation

-  O (Big Oh), Θ (Theta), ω(Omega)

·  Recurrence relations – solving recurrence relations

-  Substitution method

-  Iteration Method

·  Recursion

·  Data Structures

-  Stacks,

-  Queues,

-  Dequeue,

-  List,

-  Linked Lists,

-  Binary trees

§  Complete binary trees and incomplete,

§  Formulae for expressing the height ‘h’ of tree in terms of number of nodes ‘n’

§  Storing a binary tree

-  Binary search trees

§  Inorder,

§  Preorder,

§  Postorder traversals,

§  Deletion,

§  Insertion operations

·  Sorting algorithms

§  Mergesort,

§  Quicksort,

§  Insertion sort,

§  Binary sort(using binary search trees)

·  Hashing

§  choosing hash function

§  hashing techniques – open addressing, chaining, Random probing

§  Analysis of hash functions

·  Priority queues

§  Heap,

§  Atomic heap operations,

§  Basic heap operations,

§  Extra heap operations,

§  Bad heap operations,

§  and time complexities of above operations

·  Heap sort

·  Huffman tree

§  Application of Huffman tree in merging sorted files

·  Disjoint set structures, equivalence classes

·  Graphs

§  Definitions of node, graph, directed graph, undirected graph, subgraphs, degree, path

§  Adjacency matrix, Adjacency list.

§  Cycle, wheel, mobius wheel, grid, bipartite graph

·  Graph Traversals

§  Depth First traversal

§  Breadth First traversal

For any data structure, know the algorithms for operations on these structures. For any algorithm covered, know the asymptotic behaviors.

References: Fundamentals of Sequential Parallel Algorithms by Kenneth A. Berman and Jerome L. Paul.

CSC 437 (Programming Language Paradigms and Software Development)

A: Programming Languages

1. Introduction to Programming Languages

·  History and evolution of programming languages.

·  Different vies of programming: Procedural, Functional, Logical and Object Oriented View.

·  Programming languages constructs

2. Lexical analysis of languages.

3. Syntax analysis of languages.

4. Generative Grammar

4.1 Regular Grammar (Type 3 grammar),

4.2 Context Free Grammar (Type 2 grammar),

4.3 Context Sensitive Grammar (Type 1 grammar),

4.4 Unrestricted Grammar (Type 0 grammar).

5. Backus Naur Form (BNF) and Extended Backus Naur Form (EBNF).

6. Parse trees

6.1 Ambiguous Grammar

6.1.1 Dangling-else problem

6.1.2 Associativity of Operators

6.1.3 Operator Precedence

7. Attribute Grammars: static Semantics.

9. Variables: Name, Address, Value, Types, Lifetime, Binding, Scope.

9.1 Storage Bindings: Static Variables, Stack-dynamic, heap-dynamic.

9.2 Scope of variables: Static scoping, dynamic scoping.

9.3 Types of variables: Type checking, Strongly typed, Type Compatibility.

10. Data Types

10.1 Primitive data types

10.2 Pointer types: Garbage collection, dangling pointer.

10.3 Array Types: Static, fixed stack-dynamic, static-dynamic, heap-dynamic.

10.4 Multidimensional Array.

10.5 Ordinal Types: Record, Union.

11. Expression and Assignment Statements.

12. Control Statements.

13. Functions and Subprograms

13.1 Parameter passing methods: by-name, by-value, by-value-results, by-reference.

13.2 Static chaining and dynamic chaining.

14. Object Oriented Languages (C++ as an example)

B: Software Engineering

15.  Definition of Software Engineering

16.  Software Engineering versus Process Management

17.  The Waterfall Model

a.  Explanation and significance of model

b.  Merits of model

c.  Demerits of model

18.  Cohesion

a.  Coincidental Cohesion

b.  Logical Cohesion

c.  Temporal Cohesion

d.  Procedural Cohesion

e.  Communicational Cohesion

f.  Functional Cohesion

g.  Informational Cohesion

19.  Coupling

a.  Content Coupling

b.  Control Coupling

c.  Common Coupling

d.  Stamp Coupling

e.  Data Coupling

20.  Object Oriented Design

a.  Use Cases

b.  State Diagrams

c.  Interaction Diagram

d.  Class diagram

21.  Software Project Planning (Chapter 5 from textbook)

22.  Risk Management (Chapter 6 from textbook)

23.  Project Scheduling and Tracking (Chapter 7 from textbook)

24.  Software quality assurance (Chapter 8 from textbook)

References: Programming Languages, Concepts and Constructs by Ravi Sethi; and lecture notes.

Software Engineering: A Practitioner's Approach by Roger S. Pressman,
Publisher: McGraw-Hill Science/Engineering/Math; ISBN: 0072496681; 5th edition;