Test
edit SideBar
|
ACM Body of Knowledge map for CISC 108
Discrete Structures
- DS/GraphsAndTrees [core][1 of 4 hours]
- Topics
- Learning objectives:
- Relate trees to data structures.
Programming Fundamentals
- PF/FundamentalConstructs [core] [5 of 9]
- Topics:
- Basic syntax and semantics of a higher-level language
- From BSL (Basic Student Language) through ASL (Advanced Student Language), each a highly reduced Racket/Scheme subset.
- Semantics limited to (intro in this order):
define, cond, define-struct, local, lambda, set!, begin.
- Variables, types, expressions, and assignment (mutation)
- Atomic types: numbers, strings, symbols, booleans, images, chars.
- Compound Types glue other data types together (including other compounds) with a finite number of fields: structures using
define-struct
- Mixtures (variant records/type unions): both simple enumerated types (set of symbols), and arbitrary mixtures of other atomic or compound types, explicit dispatch-on-type
- data types of arbitrary size (lists, trees), thought of as mixtures. [cover arrays/vectors???]
- mutually referent data types (e.g. filesystems: files, directories, lists-of-directories, lists-of-files)
- [NOT Simple I/O] [not covered: all I/O via high-level APIs: file I/O, event-driven GUI]
- Conditional and iterative control structures
- Functions and parameter passing
- Structured decomposition
- Learning objectives:
- Analyze and explain the behavior of simple programs involving the fundamental programming constructs covered by this unit.
- Modify and expand short programs that use standard conditional and iterative control structures and functions.
- Design, implement, test, and debug a program that uses each of the following fundamental programming constructs: basic computation, [not simple I/O], standard conditional and iterative structures, and the definition of functions.
- Choose appropriate conditional and iteration constructs for a given programming task.
- Apply the techniques of structured (functional) decomposition to break a program into smaller pieces.
- Describe the mechanics of parameter passing.
- PF/AlgorithmicProblemSolving [core][2 of 6]
- Topics:
- Problem-solving strategies
- The role of algorithms in the problem-solving process [introduction]
- The concept and properties of algorithms [introduce termination, space-time efficiency, that they don't necessarily follow from the data representation]
- Learning objectives:
- Discuss the importance of algorithms in the problem-solving process.
- Identify the necessary properties of good algorithms.
- PF/DataStructures [core][3 of 10]
- Topics:
- Arrays/vectors [???]
- Strings and string processing [no coverage of underlying representation]
- Linked structures [no explicit pointer manipulation]
- Strategies for choosing the right data structure [few choices in 108]
- Learning objectives:
- Discuss the use of primitive data types and built-in data structures.
- Compare alternative implementations of data structures with respect to performance. [vectors vs. lists]
- Write programs that use each of the following data structures: arrays/vectors, strings, lists, trees.
- Choose the appropriate data structure for modeling a given problem. [simple data structures]
- PF/Recursion [core][3 of 4]
- Topics:
- The concept of recursion
- Recursive mathematical functions
- Simple recursive functions
- Divide-and-conquer strategies
- [Recursive backtracking NOT CURRENTLY COVERED REGULARLY]
- Learning objectives:
- Describe the concept of recursion and give examples of its use.
- Identify the base case and the general case of a recursively defined problem.
- Compare iterative and recursive solutions for elementary problems such as factorial.
- Describe the divide-and-conquer approach.
- Implement, test, and debug simple recursive functions and procedures.
- PF/EventDriven [core][1 of 4]
- Topics:
- Learning objectives:
- Design, code, test, and debug simple event-driven programs that respond to user events.
- PF/ObjectOriented [core][1 of 8]
- Topics:
- Encapsulation and information-hiding
- Separation of behavior and implementation
- Learning objectives:
- Describe concepts of encapsulation, abstraction, and polymorphism. [No Inheritance, so no subtype polymorphism, only Java Interfaces]
- Design, implement, test, and debug simple programs in an object-oriented programming language. [ONE program only]
- Describe how the class mechanism supports encapsulation and information hiding.[NO Inheritance]
Algorithms and Complexity
- AL/BasicAnalysis [core][1 of 4]
- Topics:
- Big O, little o, omega, and theta notation {Big O only: constant, log n, linear, polynomial, exponential]
- Empirical measurements of performance
- Time and space tradeoffs in algorithms
- Learning objectives:
- Determine the time and space complexity of simple algorithms.
- AL/AlgorithmicStrategies [core][1 of 6]
- Topics:
- Divide-and-conquer
- [Backtracking] [Not usually covered]
- Learning objectives:
- Implement a divide-and-conquer algorithm to solve an appropriate problem.
- AL/FundamentalAlgorithms [core][1 of 12]
- Topics:
- Quadratic sorting algorithms (selection, insertion)
- O(N log N) sorting algorithms (Quicksort, heapsort, mergesort) [QUICKSORT ONLY]
- Binary search trees [LOOKUP AND INSERT, NO REBALANCING]
- Learning objectives:
- Implement the most common quadratic and O(NlogN) sorting algorithms. [Insertion, Selection, Quicksort]
- Discuss the computational efficiency of the principal algorithms for sorting, searching, and hashing. [NO HASHING]
Programming Languages
Note that there is currently a proposal to create a separate Functional Programming Core in the CS-BOK (the change is neutral in the total number of core hours).
- PL/Overview [core][1 of 2]
- Topics:
- Brief survey of programming paradigms [Discussed very briefly at start, and in more detail towards the end of the course]
- Procedural languages
- Object-oriented languages
- Functional languages
- Scripting languages
- Learning objectives:
- Identify at least one distinguishing characteristic for each of the programming paradigms covered in this unit.
- PL/AbstractionMechanisms [core][1 of 3]
- Topics:
- Procedures, functions, and iterators as abstraction mechanisms [No Iterators in the strongly-typed sense (but functions on parametric types)
- Type parameters and parameterized types
- Learning objectives:
- Explain how abstraction mechanisms support the creation of reusable software components.
- Defend the importance of abstractions, especially with respect to programming-in-the-large.
- PL/ FunctionalProgramming [elective]
- Topics:
- Overview and motivation of functional languages
- Recursion over lists, natural numbers, trees, and other recursively-defined data
- Pragmatics (debugging by divide and conquer; persistency of data structures)
- Closures and uses of functions as data (infinite sets, streams)
- Learning objectives:
- Outline the strengths and weaknesses of the functional programming paradigm.
- Design, code, test, and debug programs using the functional paradigm.
- Explain the use of functions as data, including the concept of closures.
- PL/TypeSystems [elective][5 hours]
- Topics:
- Data type as set of values with set of operations
- Data types
- Elementary types
- Algebraic types
- Arrow (function) types
- Parameterized types
- Abstract data types
- Parametric polymorphism
- Learning objectives:
- Describe each of the elementary data types.
- Explain the concept of an abstract data type.
- Recognize the importance of typing for abstraction and safety.
Social and Professional Issues
- SP/HistoryOfComputing [core][0.5 of 1]
- Topics:
- Prehistory—the world before 1946 [Primarily the Jaquard loom, Babbage & Lovelace, tabulating devices]
- [NOT History of computer hardware, software, networking] [Currently, there is no attempt to create cohesive coverage of all computer history: just anecdotes from here and there]
- [NOT Pioneers of computing] [Anecdotally only]
- Learning objectives: [should we do some of this?]
- [NOT List the contributions of several pioneers in the computing field.]
- [NOT Compare daily life before and after the advent of personal computers and the Internet.]
- SP/SocialContext [core][0.5 of 3]
- Topics:
- Public policy issues (e.g. electronic voting) [may include: electronic voting, privacy, IP, censorship, internet economy, etc.]
- Learning objectives:
- [Analyze] the role and risks of computing in the implementation of public policy and government (e.g. electronic voting). [Discussion, no deep analysis]
Software Engineering
- SE/SoftwareDesign [core][1 of 8]
- Topics:
- Fundamental design concepts and principles
- The role and the use of contracts
- Structured design
- Learning objectives:
- Discuss the properties of good software design including the nature and the role of associated documentation.
- SE/UsingAPIs [core][0.5 of 3]
- Topics:
- Programming using APIs [In particular, the Universe event-driven API, but also the image libraries, etc.]
- Learning objectives:
- Explain the value of application programming interfaces (APIs) in software development.
- SE/SoftwareEvolution [core][0.5 of 3]
- Topics:
- Software maintenance
- Characteristics of maintainable software [Primarily we focus on refactoring with abstractions: removing duplicate code]
- Refactoring
- Learning objectives:
- Identify weaknesses in a given simple design, and highlight how they can be removed through refactoring. [i.e. creating an abstraction to replace several similar pieces of code]
Recent Syllabus
- Follow and explain an explicit Design Recipe to go from an idea to a working, tested final program
- Data Definitions, examples (of data), templates (for code that operates on this data)
- Contract, Purpose and Header for each function
- Function Examples
- Template Instantiation
- Programming
- Test (using examples from step 3)
- Develop abstract, computational data models for representing problem domain-level information
- Choose from appropriately, and write programs over:
- atomic data, [in BSL atomic data types are: numbers, strings, characters, symbols, booleans, and images]
- structures [compound data, including nested structures],
- mixtures of data [i.e. type unions/variant records],
- data of arbitrary size (lists, trees),
- mutually referent data (e.g. filesystems: files, directories, lists-of-directories, lists-of-files)
- Use function composition correctly
- Use conditional statements correctly
- Develop test procedures for programs [unit testing, test-driven development]
- Write recursive and mutually recursive programs
- Write iterative programs using common forms of iteration (including structural recursion and tail-recursive accumulation)
- Explain when state and mutation is needed in programming (and why we try to avoid it when possible!)
- Abstract over and analyze simple programming patterns (higher-order programming; refactoring)
- simple abstraction by adding parameters
- parametric polymophism (e.g.
map: [X-->Y] (listof X) --> (listof Y))
- map, filter, foldr/l (reduce)
- lambda, closures
- Recognize basic time/space behavior of simple programs (constant, log, linear, polynomial, exponential)
- Familiarity with a few basic algorithms:
- searching in lists, trees, binary search trees
- sorting: insertion, selection, quicksort (all on lists)
- Event-driven programming (using World/Universe)
- Model-View separation
- clock tick events
- keyboard events
- mouse events
- display View based on current Model
- test for termination of simulation/game
- Some basic Unix command line stuff
- Basic transition to Java (no inheritance)
- [??? suggest trying to do arrays and FOR loops in Java to ease transition to 181]
- [Optional: some HTML]
|
