CS Core Topics

The following lists define the core topics that are covered in each required course. Additional topics may be covered according to the interests and inclinations of the particular instructor.

CS122 | CS126 | CS136 | CS249 | CS286 | CS381 | CS315 | CS386 | CS396 | CS412 | CS465 | CS486

CS 122

  • Algorithms
    • Elements of an algorithm: sequencing, selection, iteration, accumulation of knowledge
    • Solution styles: specialized linear, brute force search, convergence
    • Specialized vs generalized problem sets and solutions
    • Deriving generalized solutions from specialized solutions

  • Programming languages
    • Matlab and C++
    • Commands, data types, variables, input and output
    • Operators: arithmetic, relational, logical
    • Conditionals: if, switch
    • Loops: while, for
    • Functions: defining, calling, parameters
    • Arrays and matrices
    • OOP basics: classes, objects, abstraction, encapsulation

  • Basic Unix
    • File system
    • Basic applications (ssh, sftp, vim)
    • Compiling C++ programs

CS 126

  • Current language is Java
  • Problem Solving and Algorithms
    • Sequencing, selection, iteration, memory
    • Discovering patterns
  • Program Design
    • Requirements
    • Top-Down Design
    • UML Basics
    • Documentation
    • Stepwise Refinement
    • Testing & debugging
  • Unix
    • Command Line
    • Filesystem
    • Editor
    • Piping
  • Data Types
    • Variables, reserved words, and identifiers
    • Primitive and object types
    • Type casting and type coercion
  • Object-Oriented Programming (OOP) Basics
    • Abstract Data Types (ADT's)
    • Classes, objects, references
    • Instance members and static members
    • Information hiding & implementation independence
    • Class invariants
    • Aggregate types and the "has-a" relationship
    • Methods & message passing (by-value, by-reference)
    • Inheritance and the "is a" relationship
    • Polymorphism
    • Abstract classes & Interfaces
  • Common Java
    • Standard I/O
    • Applets (AWT & Swing)
    • Strings
    • Vectors
    • Generics
  • Control Structures
    • if, switch
    • while, for, do-while, "for each"
    • Loop invariants
  • Arrays
    • Primitive & object arrays
    • Single and multidimensional
    • Sequential search
    • Bubble sort
  • Thread basics

CS 136

  1. Object-Oriented Design
    • Abstraction
    • Interface
    • Extensibility
    • Modularity
    • Scalability
    • Metrics of Good Design
      Coupling
      Cohesion
    • Packages
  2. Testing & Debugging
  3. Interfaces & Polymorphism
  4. Inheritance
  5. Event-Driven Programming
    • Model-View-Controller Design Pattern
    • AWT
    • Swing
  6. Exception Handling
  7. I/O
    • Binary file I/O
    • Text file I/O
    • Directory and File Manipulations
  8. Recursion
    • Stack vs. Heap Allocation
  9. Sorting & Searching
    • Selection sort, insertion sort, and quicksort
    • Binary Search
    • Runtime efficiency
  10. Data Structures
    • Linked lists
    • Stacks
    • Queues
  11. Concurrency
    • Implementation of concurrency
    • Implications of concurrency and countermeasures

CS 249

  • Big-O notation.
  • Basic analysis of algorithms.
  • Linked lists.
  • Stacks.
  • Queues.
  • Trees
    • Preorder, inorder, postorder traversals.
    • Binary search trees.
    • Balanced search trees.
  • Priority Queues
  • Hash tables.
  • Graphs.
    • Graph representations.
    • Minimum spanning trees and their algorithms.
    • Shortest path algorithms.
  • Searching and Sorting.
    • Insertion sorts . straight insertion sort and shell sort.
    • Exchange sorts . bubble sort and quick sort.
    • Selection sorts . straight selection sort and heap sort.
    • Merge sort.
  • Advanced problem solving and program design.

CS 286

  • Soft Skills
  • GUI design and implementation.
  • Software/hardware interface.
  • Self-initiated learning and independent exploration.
  • Software engineering.
    • Production stages.
    • Incremental developmental processes.
    • Requirements acquisition.
    • Requirements analysis.
    • Real world, production-oriented context.
  • C++ (Current object-oriented language.)
  • Soft skills.
    • Production stages.
    • Team design.
    • Working in teams.
    • Interdisciplinary collaboration.
    • Individual oral presentations.
    • Individual essay writing.
    • Technical report writing.
    • Project management.

CS 301 - Social and Ethical Issues in Computer Science

  1. Classical concepts of ethics and morality
  2. Ethical dilemmas, accountability
  3. Social implications of information technology
  4. Professional ethics
  5. Ethical use of the internet
  6. Privacy issues
  7. Property rights of software

CS 315
The topics covered in CS 315 generally follow the development of computational models and corresponding state machine categories from simple to complex.

  • Intro to CS Theory (1.5 weeks)
    • What is the purpose of all language?
    • Concept of formality versus natural language
    • Notion of complexity differences in languages; the need to study/articulate.
    • Relation of formal language theory to real world problems, computation, CS
  • Basics (2 weeks)
    • Review of Discrete Math
    • Sets, set theory, set operations
    • Origins of Kleene star, Kleene plus
    • Equivalence relations, equivalence classes
    • Proving equivalence of sets
    • Induction as a proof technique, application in set theory
    • Concept of sets as .languages.
  • Regular Langs, FAs (5 weeks)
    • Introduction to regular sets, criteria for regularity
    • Proving sets/langs regular
    • Regular Expressions; Use of to describe regular sets
    • Intro to finite automata as language recognizers
    • Extensive coverage of DFAs, NFAs, proofs of equivalence DFA=NFA=other variants
  • Context Free Languages 3 weeks)
    • Concept of CFLs, examples from real life
    • Contrast to Regular Langs, Inadequacy of FA to handle, subsumption of Regular in CFL
    • Intro to CFGs, use of CFGs to describe languages, language generation
    • Normal Forms: Chomsky, Greibach, including motivations for each
    • Intro to PDAs as machine models for CFLs.
    • PDA: deterministic, non-deterministic, use as language recognizers
  • Turing Machines (3 weeks)
    • Contrast to Regular Langs, CFLs; Inadequacy of PDAs for some probs
    • Intro to Recursive Enumerable langs, Turing machines, subsumption of Reg, CFL within Recursive Enumerable langs
    • Use of basic TMs to model various langs.
    • Extensions of basic TM: n-tape, bi-directional, multiple read heads
    • Proofs of equivalence of various TM varieties
  • Review of Basics (0.5 weeks)
    • Retrospective revisitation of BIG PICTURE; re-establish relation/value of theory to real-world computation

CS 386 - Advanced Software Engineering

  1. Overview and concepts: software engineering and software engineering technologies
  2. The Rational Unified Process and its phases, people and their roles in this process
    • Inception, Elaboration, Construction, Transition
    • Manager, Analyst, Architect, Developer etc.
  3. Soft skills:
    • Project management
    • Technical analysis and writing
    • Time management and resource scheduling
    • Teaming and communication skills
    • Optional: Internationalization

CS 396
The topics covered in CS396 can be roughly grouped into three overall topical areas.

  • History of Programming Languages (4 weeks)
    • Goals of purposes of high-level language in general
    • Principles of Language Design: A framework for critique and eval
    • Historical evolution of languages covering:
      • historical design context for each
      • main features of each; new ideas and concept pioneered in various langs
      • Critique: pros and cons
      • Influences on design on PLs in general
  • Syntax, Semantics (6 weeks)
    • Formal Syntax specification issues; plus coverage of CFGs, BNF, EBNF, Syntax Diagrams
    • Parsing, parse trees, dealing with ambiguity
    • Semantic Grammars
    • Formal Semantics including strong coverage, critique, pro/cons of
      • Operational semantics
      • Axiomatic semantics
      • Denotational semantics
    • Language Design and Implementation
    • Naming, Scoping, Binding and related design options/decisions
    • Typing: Weak versus Strong; pros/cons
    • Management of namespaces; introduction to system stack
    • Storage allocation models: static, stack-dynamic, heap
    • Subprograms, including
      • Parameter Passing . various possible modes, pro/cons for each
      • Allocation/management of sys stack space
      • Implementation: Variable access under static versus dynamics scoping
      • Implementation: Use of display to speed access
  • Language Paradigms: Exploration and Evaluation (5 weeks, about 1+ apiece)
    • Procedural Paradigm
      • Relation to Von Neuman Machine
      • Block-structuring
      • Pros/Cons; appropriate application contexts
    • Functional Paradigm
      • Relation to functional mathematics
      • Concepts of stateless programming; contrast to procedural
      • Introductory overview of fn. Languages: scheme, ml, haskell
    • OOP Paradigm
      • Abstraction encapsulation
      • Design issues: inheritance, multiple inheritance, polymorphism, strong typing
      • Overview of functional languages: Smalltalk, implementation of
    • Logic Paradigm
      • Concepts of declarative programming
      • Theory: Horne clauses, FOPL, closed-world assumption
      • Unification, Rules, Facts
      • Flow of Satisfaction in Prolog; backtracking
      • parallelism in logic languages

CS 412 - Enterprise Web Computing

  1. Introduction to Markup Languages
  2. XML Basics
    • Schema
    • Parsing XML, DOM, SAX, StAX
    • Style sheets
    • XML Queries, XQuery, XPath
  3. XML Technologies and their applications
    • RSS
    • XML-RPC
    • WSDL/SOAP
    • RDF
    • SQL/XML
    • Jabber
  4. Advanced XML Technologies
  5. Soft skills: in this student-centered and student-driven class, students will considerably advance in their ability to present to, interact and argue with other students in a semi-professional environment.

CS 465 - Distributed Systems

  1. The student will get in-depth knowledge about fundamental concepts of distributed systems, e.g.:
    • Time
    • Consensus
    • Mutual exclusion
    • Concurrency
    • Transactions
    • Replication
    • Load distribution etc.
  2. The student will know about the limitations of distributed systems
  3. The student will be able to choose among and to turn abstract algorithms pertaining to high-level concepts into concrete software implementations for typical application scenarios
  4. Soft skills: in this student-centered and student-driven class, students will considerably advance in their ability to present to, interact and argue with other students in a semi-professional environment.

CS 486

  • Project Management: Team organization/roles, task allocation and monitoring, conflict resolution, team morale and motivation
  • Task decomposition; composite solution integration
  • Technical Analysis and Writing
  • Time management and resource scheduling
  • Technical presentation skills
  • Formal project reporting and documentation
  • Professional communication/ client-contractor interaction
  • Advanced Software Engineering: responding to RFPs, Feasibility and Risk Analysis, Requirements Analysis and Acquisition, Cost estimation, Proposal development and presentation, Functional Specification, Project Planning and monitoring, Functional and Performance Testing and Analysis
 
 

Refer this page to a friend

© 2009 Arizona Board of Regents.
Northern Arizona University, South San Francisco Street, Flagstaff, Arizona 86011