Error: no such theme PatternSkinTheme
You are here: Foswiki>Faculty Web>CourseGoalsAndObjectives (revision 8)EditAttach

Course Goals and Objectives

Goals and objectives are under development for each course within the Department of Computer Science. Draft statements for each course may be found on separate pages, available through the following links.


The following material is being moved to separate course pages. When this transition is completed, the following material will be deleted.

CSC 151, Functional problem solving

CSC 161, Imperative problem solving and data structures

CSC 161 provides foundational coverage of topics related to imperative problem solving, Unix/Linux programming environments, and data structures. Topics covered will include:

  • Low-level, imperative problem solving and elements of C
    • Macros
    • Compiling, linking
    • Preprocessing
    • Assignment
    • Conditionals: if , switch
    • File I/O
    • Arrays
    • Loops
    • Pointers and memory management
    • Header files
    • Strings
    • Command-line arguments
    • Structs
    • Unions
  • General topics
    • Assert
    • Binary representation of data (twos-complement, IEEE floating-point)
    • Recursion
    • Loop invariants
  • Linux
    • Elementary make files
    • Permissions
    • I/O redirection
    • grep
    • Editing with emacs or vi
  • Abstract data types and data structures
    • Linked lists (and doubly-linked-lists and circular lists)
    • Stacks and queues

CSC 207, Algorithms and object-oriented design

CSC 207 introducts object-orient problem solving, the Java programming language, and associated algorithms. An approximate list of topics follows:

  • Java
    • Basics
    • Interfaces and classes
    • Exceptions
    • Strings
    • Arrays vs. vectors
    • Comparators; sorting
    • Generics
    • Java type system
    • Iterators
    • Negotiating the Java class libraries
  • OOP
    • Inheritance
    • Polymorphism
  • Abstract data types, data structures, and algorithms
    • Dictionaries
    • Hash tables
    • Binary search trees
    • Priority queues
    • Heaps
    • Formalize upper-bound efficiency analysis; big- O notation
    • Contrast results for small and large data sets
    • Prove negligible role of lower-order terms
  • Program development
    • Integrated development environments
    • Unit testing
    • Integration testing
  • Possible additional topics
    • Introspection
    • Swing
    • Introduction of tight-bound analysis (big Θ)
CSC 301, Analysis of Algorithms

CSC 301 examines the design, implementation, and efficiency of algorithms, extending the study begun in CSC 151 and continued in CSC 161, CSC 207, and MAT 218. The course has four main foci:
  • Alternative strategies in the design of algorithms,
  • Relationships between algorithms and data structures:
    • Some algorithms (e.g., numerical methods) solve problems with little need for extensive data structures.
    • Some algorithms evolve to support abstract data types (e.g., dictionaries) and their underlying data structures (e.g., arrays and linked lists), and
    • Some algorithms require careful record keeping, requiring the design and use of their own internal data structures (e.g., adjacency matrices for graphs).
  • Careful analysis of the efficiency of these algorithms, regarding both run-time performance and resource use
  • Techniques for establishing algorithm correctness.
More specifically, CSC 301 has these high-level goals:
  • to gain proficiency in the use of fundamental strategies for algorithm development
  • to understand and apply fundamental algorithms to a range of problems
  • to learn representative algorithms that are largely independent of data structures, algorithms that support abstract data types and data structures, and algorithms that utilize their own data structures for record keeping
  • to learn techniques for analyzing algorithms, such as instruction counts, recurrence relations, probability theory
  • to understand and apply methods for showing the correctness of algorithms to solve sample problems
The objectives of CSC 301 include these capabilities:
  • Students should be able to identify and explain at least five distinct strategies for algorithm development and provide at least one example illustrating each strategy.
  • Students should be able to explain, implement, and analyze fundamental algorithms from several application domains, such as trees, graphs, strings, and dictionaries.
  • When several different algorithms are available for a task, students should be able to apply careful analysis to determine conditions when one algorithm may be better, worse, or about the same effectiveness as another.
  • Since algorithms are normally designed to help solve problems, students should be able to provide formal arguments regarding why an algorithm correctly addresses specified requirements.
Since the subject of algorithms and algorithmic analysis is vast, each offering of CSC 301 must select illustrative strategies, techniques, structures, and analyses. CSC 301 is not meant to be encyclopedic, but rather to lay a foundation that will enable students to develop, implement, and analyze algorithms that may address future problems that might be encountered.

The following topic listing suggests some possible topics for CSC 301. Time constraints preclude any offering of the course from covering all of these topics, and the evolution of the discipline may suggest alternative topics.
  • strategies for algorithm development: possible approaches may include:
    • greedy algorithms
    • divide-and-conquer algorithms
    • dynamic programming
    • approximation algorithms
    • local search
    • randomized algorithms
    • simulated annealing
    • genetic algorithms
    • multi-threaded algorithms
  • Problems with algorithms that have little need for extensive data structures: possible problem domains for consideration may include:
    • random number generation
    • finding roots of functions
      • log n algorithms (e.g., bisection method)
      • self-correcting algorithms (e.g., Newton's method)
    • finding greatest common divisors (e.g., Euclid's algorithm)
    • primality testing
    • generating permutations, combinations, and partitions
    • geometric determinations
      • intersection of line segments
      • convex hulls
      • closet pair of points
  • Algorithms supporting data structures: Possible data structures may include:
    • Sorting array data
      • quicksort, merge sort and/or heap sort
      • linear-time sorting methods
    • Tree structures
      • Tree balancing
      • Decision trees
      • Analysis using trees
        • efficiency limits on sorting algorithms
      • Optimal binary search trees
      • Red-black trees
      • Interval trees
      • Huffman algorithm
      • File compression
      • Multi-way search trees
    • Graphs
      • Undirected graphs
        • Spanning trees
        • Graph connectivity
      • Directed graphs
        • Adjacency graphs
        • Hamiltonian circuits
        • Topological sort
        • Single source shortest path
  • Algorithms requiring auxiliary data structures: representative topics may include:
    • String Processing
    • Maps/Dictionaries/Hashing
      • Open hash tables
      • Closed hash tables
      • Collision resolution
      • Analysis
    • Heaps and priority queues
Edit | Attach | Print version | History: r11 | r9 < r8 < r7 < r6 | Backlinks | View wiki text | Edit WikiText | More topic actions...
Topic revision: r8 - 2011-01-25, HenryWalker
 

This site is powered by FoswikiCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding Foswiki? Send feedback