Popular Posts

Wednesday, July 9, 2014

time series

Time Series Analysis: The Basics
 


WHAT IS A TIME SERIES?

A time series is a collection of observations of well-defined data items obtained through repeated measurements over time. For example, measuring the value of retail sales each month of the year would comprise a time series. This is because sales revenue is well defined, and consistently measured at equally spaced intervals. Data collected irregularly or only once are not time series.

An observed time series can be decomposed into three components: the trend (long term direction), the seasonal (systematic, calendar related movements) and the irregular (unsystematic, short term fluctuations).


WHAT ARE STOCK AND FLOW SERIES?

Time series can be classified into two different types: stock and flow.

A stock series is a measure of certain attributes at a point in time and can be thought of as “stocktakes”. For example, the Monthly Labour Force Survey is a stock measure because it takes stock of whether a person was employed in the reference week.

Flow series are series which are a measure of activity over a given period. For example, surveys of Retail Trade activity. Manufacturing is also a flow measure because a certain amount is produced each day, and then these amounts are summed to give a total value for production for a given reporting period.

The main difference between a stock and a flow series is that flow series can contain effects related to the calendar (trading day effects). Both types of series can still be seasonally adjusted using the same seasonal adjustment process.


WHAT ARE SEASONAL EFFECTS?

A seasonal effect is a systematic and calendar related effect. Some examples include the sharp escalation in most Retail series which occurs around December in response to the Christmas period, or an increase in water consumption in summer due to warmer weather. Other seasonal effects include trading day effects (the number of working or trading days in a given month differs from year to year which will impact upon the level of activity in that month) and moving holidays (the timing of holidays such as Easter varies, so the effects of the holiday will be experienced in different periods each year).

WHAT IS SEASONAL ADJUSTMENT AND WHY DO WE NEED IT?

Seasonal adjustment is the process of estimating and then removing from a time series influences that are systematic and calendar related. Observed data needs to be seasonally adjusted as seasonal effects can conceal both the true underlying movement in the series, as well as certain non-seasonal characteristics which may be of interest to analysts.


WHY CAN'T WE JUST COMPARE ORIGINAL DATA FROM THE SAME PERIOD IN EACH YEAR?

A comparison of original data from the same period in each year does not completely remove all seasonal effects. Certain holidays such as Easter and Chinese New Year fall in different periods in each year, hence they will distort observations. Also, year to year values will be biased by any changes in seasonal patterns that occur over time. For example, consider a comparison between two consecutive March months i.e. compare the level of the original series observed in March for 2000 and 2001. This comparison ignores the moving holiday effect of Easter. Easter occurs in April for most years but if Easter falls in March, the level of activity can vary greatly for that month for some series. This distorts the original estimates. A comparison of these two months will not reflect the underlying pattern of the data. The comparison also ignores trading day effects. If the two consecutive months of March have different composition of trading days, it might reflect different levels of activity in original terms even though the underlying level of activity is unchanged. In a similar way, any changes to seasonal patterns might also be ignored. The original estimates also contains the influence of the irregular component. If the magnitude of the irregular component of a series is strong compared with the magnitude of the trend component, the underlying direction of the series can be distorted.

However, the major disadvantage of comparing year to year original data, is lack of precision and time delays in the identification of turning points in a series. Turning points occur when the direction of underlying level of the series changes, for example when a consistently decreasing series begins to rise steadily. If we compare year apart data in the original series, we may miss turning points occurring during the year. For example, if March 2001 has a higher original estimate than March 2000, by comparing these year apart values, we might conclude that the level of activity has increased during the year. However, the series might have increased up to September 2000 and then started to decrease steadily.

WHEN IS SEASONAL ADJUSTMENT INAPPROPRIATE?

When a time series is dominated by the trend or irregular components, it is nearly impossible to identify and remove what little seasonality is present. Hence seasonally adjusting a non-seasonal series is impractical and will often introduce an artificial seasonal element.

WHAT IS SEASONALITY?

The seasonal component consists of effects that are reasonably stable with respect to timing, direction and magnitude. It arises from systematic, calendar related influences such as:
        • Natural Conditions
            weather fluctuations that are representative of the season
            (uncharacteristic weather patterns such as snow in summer would be considered irregular influences)
        • Business and Administrative procedures
            start and end of the school term
        • Social and Cultural behaviour
            Christmas

It also includes calendar related systematic effects that are not stable in their annual timing or are caused by variations in the calendar from year to year, such as:
        • Trading Day Effects
            the number of occurrences of each of the day of the week in a given month will differ from year to year
            - There were 4 weekends in March in 2000, but 5 weekends in March of 2002
        • Moving Holiday Effects
            holidays which occur each year, but whose exact timing shifts
            - Easter, Chinese New Year

HOW DO WE IDENTIFY SEASONALITY?

Seasonality in a time series can be identified by regularly spaced peaks and troughs which have a consistent direction and approximately the same magnitude every year, relative to the trend. The following diagram depicts a strongly seasonal series. There is an obvious large seasonal increase in December retail sales in New South Wales due to Christmas shopping. In this example, the magnitude of the seasonal component increases over time, as does the trend.
Figure 1: Monthly Retail Sales in New South Wales (NSW) Retail Department Stores Graph - Monthly Retail Sales in New South Wales (NSW) Retail Department Stores

WHAT IS AN IRREGULAR?

The irregular component (sometimes also known as the residual) is what remains after the seasonal and trend components of a time series have been estimated and removed. It results from short term fluctuations in the series which are neither systematic nor predictable. In a highly irregular series, these fluctuations can dominate movements, which will mask the trend and seasonality. The following graph is of a highly irregular time series:
Figure 2: Monthly Value of Building Approvals, Australian Capital Territory (ACT) Graph - Monthly Value of Building Approvals, Australian Capital Territory (ACT)
WHAT IS THE TREND?

The ABS trend is defined as the 'long term' movement in a time series without calendar related and irregular effects, and is a reflection of the underlying level. It is the result of influences such as population growth, price inflation and general economic changes. The following graph depicts a series in which there is an obvious upward trend over time:
Figure 3: Quarterly Gross Domestic Product
Graph - Quarterly Gross Domestic Product


WHAT ARE THE UNDERLYING MODELS USED TO DECOMPOSE THE OBSERVED TIME SERIES?

Decomposition models are typically additive or multiplicative, but can also take other forms such as pseudo-additive.

Additive Decomposition

In some time series, the amplitude of both the seasonal and irregular variations do not change as the level of the trend rises or falls. In such cases, an additive model is appropriate.

In the additive model, the observed time series (Ot) is considered to be the sum of three independent components: the seasonal St, the trend Tt and the irregular
It.


That is



Each of the three components has the same units as the original series. The seasonally adjusted series is obtained by estimating and removing the seasonal effects from the original time series. The estimated seasonal component is denoted by The seasonally adjusted estimates can be expressed by:



In symbols,

The following figure depicts a typically additive series. The underlying level of the series fluctuates but the magnitude of the seasonal spikes remains approximately stable.
Figure 4: General Government and Other Current Transfers to Other Sectors
Graph - General Government and Other Current Transfers to Other Sectors

Multiplicative Decomposition

In many time series, the amplitude of both the seasonal and irregular variations increase as the level of the trend rises.In this situation, a multiplicative model is usually appropriate.

In the multiplicative model, the original time series is expressed as the product of trend, seasonal and irregular components.


or



The seasonally adjusted data then becomes:


or

Under this model, the trend has the same units as the original series, but the seasonal and irregular components are unitless factors, distributed around 1.

Most of the series analysed by the ABS show characteristics of a multiplicative model. As the underlying level of the series changes, the magnitude of the seasonal fluctuations varies as well.
Figure 5: Monthly NSW ANZ Job Advertisements Graph - Monthly NSW ANZ Job Advertisements
Pseudo-Additive Decomposition

The multiplicative model cannot be used when the original time series contains very small or zero values. This is because it is not possible to divide a number by zero. In these cases, a pseudo additive model combining the elements of both the additive and multiplicative models is used. This model assumes that seasonal and irregular variations are both dependent on the level of the trend but independent of each other.

The original data can be expressed in the following form:


The pseudo-additive model continues the convention of the multiplicative model to have both the seasonal factor St and the irregular factor It centred around one. Therefore we need to subtract one from St and It to ensure that the terms Tt x (St - 1) and Tt x (It - 1) are centred around zero. These terms can be interpreted as the additive seasonal and additive irregular components respectively and because they are centred around zero the original data Ot will be centred around the trend values Tt .

The seasonally adjusted estimate is defined to be:


where and are the trend and seasonal component estimates. In the pseudo-additve model, the trend has the same units as the original series, but the seasonal and irregular components are unitless factors, distributed around 1.

An example of series that requires a pseudo-additive decomposition model is shown below. This model is used as cereal crops are only produced during certain months, with crop production being virtually zero for one quarter each year.
Figure 6: Quarterly Gross Value for the Production of Cereal Crops
Graph - Quarterly Gross Value for the Production of Cereal Crops


Example: Shiskin Decomposition

The Shiskin decomposition gives graphs of the original series, seasonally adjusted series, trend series, residual (irregular) factors and the between month (seasonal) and within month (trading day) factors that are combined to form the combined adjustment factors. The residual (irregular) factors are found by dividing the seasonally adjusted series by the trend series. Figure 7 shows a Shiskin decomposition for the Australian Retail series.

Figure 7: Shiskin decomposition for Australian Total Retail Turnover, May 1990 to May 2000
Graph - Shiskin decomposition for Australian Total Retail Turnover, May 1990 to May 2000


HOW DO I KNOW WHICH DECOMPOSITION MODEL TO USE?

To choose an appropriate decomposition model, the time series analyst will examine a graph of the original series and try a range of models, selecting the one which yields the most stable seasonal component. If the magnitude of the seasonal component is relatively constant regardless of changes in the trend, an additive model is suitable. If it varies with changes in the trend, a multiplicative model is the most likely candidate. However if the series contains values close or equal to zero, and the magnitude of seasonal component appears to be dependent upon the trend level, then pseudo-additive model is most appropriate.

WHAT IS A SEASONAL AND IRREGULAR (SI) CHART?

Once the trend component is estimated, it can be removed from the original data, leaving behind the combined seasonal and irregular components or SIs. A seasonal and irregular or SI chart graphically presents the SI's for particular months or quarters in the series span.

The following graph is an SI chart for a monthly series, using a multiplicative decomposition model.
Figure 8: Seasonal and Irregular (SI) Chart - Value of Building Approvals, ACT
Graph - Seasonal/Irregular (S-I) Chart - Value of Building Approvals, ACT

The points represent the SIs obtained from the time series, while the solid line shows the seasonal component. The seasonal component is calculated by smoothing the SI's, to remove irregular influences.

SI charts are useful in determining whether short-term movements are caused by seasonal or irregular influences. In the graph above, the SIs can be seen to fluctuate erratically, which indicates the time series under analysis is dominated by its irregular component.

SI charts are also used to identify seasonal breaks , moving holiday patterns and extreme values in a time series.

Bookmark and Share. Opens in a new window

Sunday, June 29, 2014

         
Degree Fields
State Portals
Industry Options
Precollege Ideas
Academic DegreesCareer Planning
University Choice
Diversity & WomenCornerstone News
Site Search / A -Z

Bookmark and Share

Computer Science Overview - Preparation - Specialty Areas - Day In The Life - Earnings - Employment - Career Path Forecast - Professional Organizations -  Profiles of Computer Scientists - Overview PowerPoint


Specialty Areas
Algorithms and Theory - Artificial Intelligence - Architecture, Parallel Computing and Systems - Bioinformatics and Computational Biology - Database and Information Systems - Graphics, Visualization and Human-Computer Interface - Systems and Networking - Programming Languages, Formal Systems, and Software Engineering - Scientific Computing
Algorithms and Theory
Research in this area focuses on the design and analysis of algorithms and data structures for problems arising in several areas of computer science, including automatic software verification, computational geometry, data mining, and machine learning.
Artificial Intelligence
This specialty area focuses on a broad range of topics that include knowledge representation, learning, vision, reasoning, robotics, information systems, and planning. Application areas include molecular biology, manufacturing, control theory, and scheduling.

Architecture, Parallel Computing and Systems
Those focusing on the specialty area of architecture develop hardware designs, programming languages, and their compilers for next-generation computers and computing components.  The specialty area of parallel computing area focuses on projects of varying size and investigates the software aspects of computation on computers composed of multiple processors.
Bioinformatics and Computational Biology
Research in this area includes developing efficient and scalable algorithms for biomolecular simulation and applying data mining, statistical machine learning, natural language processing, and information retrieval to analyze and mine all kinds of biological data, including DNA sequences, protein sequences and structures, microarray data, and biology literature, for the purpose of facilitating biology discovery.

Database and Information Systems
Individuals working in this area would conduct fundamental and cutting-edge research in databases, data mining, web mining, information retrieval, and natural language processing. Current areas of focus might include data integration, exploring and integrating the "Deep Web;" schema matching; security; mining data streams and sequential and semi-structured data; operating systems support for storage systems; text retrieval and mining; bio-informatics; database support for high performance computing; and top-k query processing.
Graphics, Visualization and the Human Computer Interface
Graphics and visualization research includes modeling and animation of natural phenomena, computational topology, graphics hardware utilization, image based rendering, implicit surfaces, mesh processing and simplification, procedural modeling and texturing, shape modeling, surface parameterization, and visibility processing. Human-Computer Interface research involves user interface tools that better support early design tasks, systems and environments that help users maintain information awareness, tools for multimedia authoring and design, interfaces that foster social interaction, and, more generally, human-computer interaction.

Systems and Networking
Networking and distributed systems group research includes a broad range of topics that include mobile systems, wireless protocols, ad-hoc networks, Quality of Service management, multimedia networking, peer-to-peer networking, routing, network simulations, active queue management, and sensor networks.

Operating system research focuses on distributed resource management, management of ubiquitous computing environments, reflective middleware, middleware "meta-operating systems," object-oriented operating system design, user interfaces that allow single users to interact with multi-computers, peer-to-peer operating system services, and context-sensitive distributed file systems, power management for data centers, file/storage systems, autonomic computing, system support for software robustness, and system support for databases.

Security research includes dynamic security architectures; security for active networks; privacy, authentication, authorization, access control, and trust in ubiquitous computing environments that have mobile users; authentication in sensor networks; specification and validation of security access control policies; simulation of network security problems and solutions including denial of service; and next generation phone security.

Real-time and embedded systems research areas include open real-time systems QoS driven real-time scheduling and communication protocols, integrated design of controllers and real-time schedulers, the integration between real-time, fault tolerant and security protocols, and robust dynamic real-time architecture for networked devices and smart spaces.

Programming Languages, Formal Systems,
and Software Engineering

Those working in this specialty area study the design and implementation of computer languages, with the goal of improving both programmer productivity and program quality. The topics of study range from abstract theories of computer languages to practical questions about the use and implementation of high-level languages.

Scientific Computing

Individuals working in the specialty area of scientific computing conduct research on the development and analysis of numerical techniques for approximating mathematical models of physical systems and on algorithms for solving the resulting equations on high performance computer systems. Specific scientific and engineering applications considered include biological molecular dynamics, materials science, semiconductor si

Computer Science

LISA MEEDEN, Professor and Chair
TIA NEWHALL, Associate Professor
RICHARD WICENTOWSKI, Associate Professor and Associate Provost
ANDREW DANNER, Assistant Professor
AMEET SONI, Assistant Professor
KEVIN WEBB, Assistant Professor
JOSHUA BRODY, Visiting Assistant Professor
JASON WATERMAN, Visiting Assistant Professor
BENJAMIN YLVISAKER, Visiting Assistant Professor
FRANCES RUIZ, Academic Support Coordinator
JEFFREY KNERR, System Administrator and Visiting Instructor
BRIDGET M. ROTHERA, Administrative Assistant
Computer science is the study of algorithms and their implementation. This includes the study of computer systems; methods to specify algorithms (for people and computer systems); and the formulation of theories and models to aid in the understanding and analysis of the properties of algorithms, computing systems, and their interrelationship.
The computer science curriculum is designed to provide students with a flexible set of computing choices that can be tailored to satisfy various interests and depths of study. All courses emphasize the fundamental concepts of computer science, treating today’s languages and systems as current examples of the underlying concepts. The computer science laboratory provides up-to-date software and hardware facilities.

The Academic Program

The Computer Science Department offers course majors and minors and honors majors and minors. Students interested in any of these options are encouraged to meet with the chair of the Computer Science Department as early as possible in their college career. Students who are interested in a computer science major or minor are encouraged to take CPSC 021, CPSC 031 and CPSC 035 sometime in their first four semesters at Swarthmore. The minor in computer science is designed for students who desire a coherent introduction to the core topics in the field. Students completing the minor will possess intellectual skills that are useful in many disciplines.

First course recommendations

CPSC 021: Introduction to Computer Science presents fundamental ideas in computer science while building skill in software development. No previous experience with computers is necessary. This course is appropriate for all students who want to write programs. It is the usual first course for computer science majors and minors. Students with Advanced Placement credit or extensive programming experience may be able to place out of this course.
CPSC 031: Introduction to Computer Systems assumes that the student has completed CPSC 021 or its equivalent. It is the best entry point for students intending to be Computer Science majors or minors who already have extensive computing experience.
CPSC 035: Data Structures and Algorithms assumes that the student has completed CPSC 021 or its equivalent. It is an appropriate entry point for students with extensive computing experience.
Students who think they may qualify for CPSC 031 or CPSC 035 and have not taken CPSC 021 should see the instructor or department chair. Students or advisers who want more advice on placement in computer science courses should feel free to contact any computer science faculty member by phone or in person.

Interdisciplinary recommendations

The department recommends that students with an interest in computer science should consider using MATH 027 (Linear Algebra) and/or MATH 029 (Discrete Math) to satisfy the math requirement for the major and minor. Statistics courses at the level of STAT 031 (Data Analysis and Visualization) or above can also be used to satisfy the math requirement.
The Computer Science department offers three courses approved as cognitive science courses: CPSC 063 (Artificial Intelligence), CPSC 065 (Natural Language Processing) and CPSC 081 (Adaptive Robotics). Students with an interest in Cognitive Science are encouraged to consider COGS 001 (Introduction to Cognitive Science).
In addition to courses offered by computer science faculty, the department recommends that students with an interest in computer engineering consider courses offered by the Engineering department, including three courses that are cross-listed by the Computer Science department: CPSC 052 (Computer Architecture), CPSC 072 (Computer Vision) and CPSC 082 (Mobile Robotics).

Course Major

The following are the requirements for a major in computer science:
  1. Nine courses in computer science:
    1. CPSC 021. (If exempted from CPSC 021 without AP credit, substitute one course from any Group listed below.)
    2. CPSC 031 or CPSC 033.
    3. CPSC 035 and CPSC 097.
    4. One course from each of the following three groups:
      1. Group 1: CPSC 041 or CPSC 046.
      2. Group 2: CPSC 043, CPSC 044, CPSC 045, CPSC 075, or CPSC 087.
      3. Group 3: CPSC 037, CPSC 040, CPSC 063, CPSC 065, CPSC 068, CPSC 071, CPSC 081
    5. Two CPSC courses numbered above CPSC 035 (must be different than the choices in part c).
  2. Two MATH/STAT courses at the level of Linear Algebra or above (Discrete Math and Linear Algebra are recommended).
Students graduating in or prior to 2016 may use the requirements found in older editions of the course catalog. See the Computer Science department for more information.

Course Minor

The minor in computer science provides students with a well-rounded background in computer science sufficient to develop significant, creative applications and to keep up with the rapid changes in the field.
The following are the requirements for a minor in computer science:
  1. Six courses in computer science.
    1. CPSC 021. (If exempted from CPSC 021 without AP credit, substitute one course from any Group listed below.)
    2. CPSC 031 or CPSC 033.
    3. CPSC 035.
    4. Two upper-level courses drawn from different groups:
      1. Group 1: CPSC 041 or CPSC 046.
      2. Group 2: CPSC 043, CPSC 044, CPSC 045, CPSC 075, or CPSC 087.
      3. Group 3: CPSC 037, CPSC 040, CPSC 063, CPSC 065, CPSC 068, CPSC 071, CPSC 081
    5. One CPSC course numbered above CPSC 035 (must be different than the choices in part c).
  2. One MATH/STAT course at the level of Linear Algebra or above (Discrete Math recommended).
Students graduating in or prior to 2016 may use the requirements found in older editions of the course catalog. See the Computer Science department for more information.
Honors Major
An honors major in computer science will consist of completion of the course major, two 2-credit preparations, one 2-credit research report or thesis.
The following will be submitted to external examiners for evaluation:
Two 2-credit preparations to be selected from the combinations of courses listed under Approved Preparations. Each of these 2-credit preparations will be examined by a 3-hour written examination and an oral examination.
The two 2-credit preparations must include four distinct courses. In certain circumstances, the Computer Science Department may be willing to consider other groupings of courses, seminars, or courses with attachments. If the required courses and preparations would not satisfy a course major, additional computer science courses must be taken to meet course major requirements. In all cases, the Computer Science Department must approve the student’s plan of study.
One research report or thesis to be read by an external examiner and examined in an oral examination.
At a minimum, this will involve a review of scholarly papers from the primary literature of computer science and the writing of a scholarly, scientific paper. The paper will report on a research experience involving the student and faculty (here or elsewhere). It is expected that most of the research or scholarly groundwork will be completed before the fall semester of the senior year, either by 1 credit of work in the spring semester of the junior year or full-time summer work. Students will register for at least 1 credit of thesis work to complete the work and write the paper in the fall of the senior year. It is recommended that the paper be completed by the end of the fall semester.

Acceptance Criteria

To be eligible for an honors major in computer science, students must complete the following:
  1. Have a B+ average in all computer science courses completed by the end of junior year. These must include CPSC 021 and CPSC 035, and at least two of, CPSC 031, CPSC 037, CPSC 041, CPSC 046 or CPSC 075.
  2. Have demonstrated proficiency in mathematical argument and reasoning by the end of the junior year. Ordinarily, this proficiency will be assumed if the student has done one of the following:
    1. Completed Discrete Mathematics and Linear Algebra with a grade of B+ or better
    2. Completed Linear Algebra Honors with a grade of B or better
    3. Completed Introduction to Real Analysis or Introduction to Modern Algebra with a grade of B- or better
  3. Completed by the end of the senior year a set of courses that would qualify for an ordinary computer science major as well as CPSC 180 (Thesis).

Honors Minor

An honors minor in computer science will consist of completion of the course minor and one 2-credit preparation.
The following will be submitted to external examiners for evaluation:
One 2-credit preparation to be selected from the combinations of courses listed under Approved Preparations. This 2-credit preparation will be examined by a 3-hour written examination and an oral examination.
The 2-credit preparation must include two distinct courses. In certain circumstances, the Computer Science Department may be willing to consider other groupings of courses, seminars, or courses with attachments. If the required courses and preparations would not satisfy a course minor, additional computer science courses must be taken to meet course minor requirements. In all cases, the Computer Science Department must approve the student’s plan of study.

Acceptance Criteria

To be eligible for an honors minor in computer science, a student must satisfy course requirements for a regular minor in computer science and in addition:
  1. Have a B+ average in all computer science courses completed by the end of the junior year.
  2. Take one 2-credit preparation to be selected from the combinations of courses listed under Approved Preparations. An examiner will set both a 3-hour written examination and an oral examination for the preparation.

Approved Preparations for the Honors Major and Minor

The following are the approved preparations. These may not all be available to all students because of the faculty’s schedules.

Preparation
Course Combinations
Algorithms and Theory
CPSC 041. Algorithms
CPSC 046. Theory of Computation
Intelligent Systems
CPSC 063. Artificial Intelligence
CPSC 081. Adaptive Robotics
Parallel and Distributed Systems
CPSC 045. Operating Systems
CPSC 087. Parallel and Distributed Computing
Natural Language Models
CPSC 063. Artificial Intelligence
CPSC 065. Natural Language Processing
High-performance Computing
CPSC 40. Computer Graphics
CPSC 87. Parallel and Distributed Computing
Network Systems   CPSC 43. Computer Networks
CPSC 45. Operating Systems
Distributed Computing CPSC 43. Computer Networks
CPSC 87. Parallel and Distributed Computing
Data Systems CPSC 44. Database Systems
CPSC 45. Operating Systems
Statistical Machine Learning CPSC 65. Natural Language Processing
CPSC 68. Bioinformatics
Bioinformatics CPSC 63. Artificial Intelligence
CPSC 65. Natural Language Processing
Programming Languages and Compilers
CPSC 037. Structure and Interpretation of Computer Programs
CPSC 075. Compiler Design and Construction
Parallel Systems and Algorithms
CPSC 041. Algorithms
CPSC 087. Parallel and Distributed Computing

Thesis / Culminating Exercise

Senior Conference is the comprehensive requirement for computer science course and honors majors. It provides an opportunity to delve more deeply into a particular topic in computer science, synthesizing material from previous courses.

Application Process and Acceptance Criteria for Majors/Minors

In addition to the process described by the Dean’s Office and the Registrar’s Office for how to apply for a major, we also ask that students complete a departmental form outlining how they intend to fulfill the requirements for their intended major, minor, honors major or honors minor. Successful completion of at least two computer science courses including CPSC 035 is ordinarily required to be admitted as a computer science major or minor. If after applying a student is deferred, he or she will be re-evaluated upon completion of additional computer science courses.

Advanced Placement

Students who receive a 4 or 5 on the computer science Advanced Placement exam will be awarded one credit upon successful completion of one computer science course taken at Swarthmore. Students must notify the department after completion of one computer science course in order to receive AP credit. Students should consult with any computer science faculty member about placement. Students who are placed out of CPSC 021 with AP credit need to take only 8 additional courses in computer science to complete the major, and 5 additional courses in computer science to complete the minor.

Off-Campus Study

Students planning to major or minor in computer science may opt to study abroad for one semester or a whole year. Because some advanced courses in computer science are offered in only alternate years, some selections will be unavailable to some students. The chair of the Computer Science Department should preapprove all courses of study abroad in advance of the student’s departure. The department will credit appropriate courses based on sufficient evidence of work completed presented by the student upon returning to Swarthmore.

Life After Swarthmore

Graduate School

Students interested in graduate study in computer science will be well prepared with a computer science major. Some graduate programs will also accept students who have majored in mathematics or engineering and completed a sufficient number and selection of computer science courses. The choice of the appropriate major and computing courses will depend on the student’s interests and should be made in consultation with the chair of the Computer Science Department. Other majors are also reasonable for students with special interests. For example, a major in linguistics or psychology might be appropriate for a student interested in artificial intelligence or cognitive science. In such cases, students should consult with the chair of the department as early as possible to ensure that they take the necessary mathematics and computing courses for graduate work in computer science.

Courses

CPSC 021. Introduction to Computer Science
This course presents fundamental ideas in computer science while building skills in software development. Students implement algorithms as programs in a high-level programming language. Introducing object-oriented programming and data structures allows students to construct correct, understandable, and efficient algorithms. CPSC 031 and CPSC 035 present a deeper coverage of these topics. CPSC 021 is appropriate for all students who want to be able to write programs. It is the usual first course for computer science majors and minors. Students with Advanced Placement credit or extensive programming experience may be able to place out of this course. Students who think that they may fall into this latter category should consult with any computer science faculty member.
Lab work required, programming intensive. No prerequisites.
Natural sciences and engineering practicum.
1 credit.
Each semester. Staff.
CPSC 031. Introduction to Computer Systems
This course is a broad introduction to computer science that focuses on how a computer works and how programs run on computers. We examine the hardware and software components required to go from a program expressed in a high-level programming language like C or Python to the computer actually running the program. This course takes a bottom-up approach to discovering how a computer works. Topics include theoretical models of computation, data representation, machine organization, assembly and machine code, memory, I/O, the stack, the operating system, compilers and interpreters, processes and threads, and synchronization. This course also introduces parallel and distributed computing with a specific focus on shared memory parallelism for multicore and SMP systems.
Prerequisites: CPSC 021 or equivalent.
Lab work required.
Natural sciences and engineering practicum.
1 credit.
Each semester. Staff.
CPSC 035. Data Structures and Algorithms
This course completes the broad introduction to computer science begun in CPSC 021. It provides a general background for further study in the field. Topics to be covered include object-oriented programming in C++, advanced data structures (trees, priority queues, hash tables, graphs, etc.) and algorithms, and software design and verification. Students will be expected to complete several programming projects illustrating the concepts presented.
Prerequisite: CPSC 021 or equivalent. Discrete Mathematics is recommended.
Lab work required.
Natural sciences and engineering practicum.
1 credit.
Each semester. Staff.
CPSC 037. Structure and Interpretation of Computer Programs
This course is a serious introduction to the study of computer programs and, through programs, some central ideas in computer science. By studying programs that make repeated and deep use of abstraction, students will learn how to generate precise specifications from vaguely formulated and perhaps partially understood descriptions. Topics to be covered include programming idioms and paradigms, recursion, information retrieval, binding and scope, interpreters, and compilers.
Prerequisite: CPSC 035.
Lab work required.
1 credit.
Not offered 2013–2014.
CPSC 040. Computer Graphics
(Cross-listed as ENGR 026)
Computer graphics focuses on the creation and manipulation of digital imagery. We cover the modeling, rendering, and animating of geometric object in two (2D) and three (3D) dimensions. Topics include drawing algorithms for 2D geometric primitives (points, lines, polygons), geometric matrix transformations, projective geometry, geometric object representations, hidden surface removal, hierarchical modeling, shading, lighting, shadows, ray-tracing, procedural (non-geometric) modeling, texture mapping, and animation. Labs will explore various tools for rendering graphics, including pixel buffers, OpenGL, shading languages, and general purpose GPU computing.
Prerequisites: CPSC 031, CPSC 035 and Linear Algebra required or permission of the instructor. (Linear Algebra may be taken concurrently.)
Lab work required.
Natural sciences and engineering practicum.
1 credit.
Spring 2015. Danner.
CPSC 041. Algorithms
The study of algorithms is useful in many diverse areas. As algorithms are studied, considerable attention is devoted to analyzing formally their time and space requirements and proving their correctness. Topics covered include abstract data types, trees (including balanced trees), graphs, searching, sorting, NP complete optimization problems, and the impact of several models of parallel computation on the design of algorithms and data structures.
Prerequisites: CPSC 035 required. Mathematics background at the level of Linear Algebra or higher is required (may be taken concurrently).
Lab work required.
1 credit.
Fall 2013. Brody.
CPSC 043. Computer Networks
This course covers the design, implementation and applications of computer networks, primarily focused on the protocols that enable the Internet and network applications. Additionally, this course will cover network security, such as viruses, worms, and botnets. Topics will include: data communication theory; packet-switched routing; the Internet and its protocols; socket and network application programming; overlays and P2P networks; and network security.
Prerequisite: CPSC 031 and CPSC 035 required.
Lab work required.
1 credit.
Fall 2013. Webb.
CPSC 044. Database Systems
This course provides an introduction to relational database management systems. Topics covered include data models (ER and relational model); data storage and access methods (files, indices); query languages (SQL, relational algebra, relational calculus, QBE); query evaluation; query optimization; transaction management; concurrency control; crash recovery; and some advanced topics (distributed databases, object-relational databases). A project that involves implementing and testing components of a relational database management system is a large component of the course.
Prerequisite: CPSC 031 and CPSC 035 required.
Lab work required.
1 credit.
Spring 2014. Soni.
CPSC 045. Operating Systems
(Cross-listed as ENGR 022)
This course is an introduction to the theory, design, and implementation of operating systems. An operating system is the software layer between user programs and the computer hardware. It provides abstractions of the underlying hardware that are easier to program, and it manages the machine’s resources. The following topics will be covered: processes (including synchronization, communication, and scheduling); memory (main memory allocation strategies, virtual memory, and page replacement policies); file systems (including naming and implementation issues); I/O (including devices, drivers, disks, and disk scheduling); and security.
Prerequisite: CPSC 031 and CPSC 035 required.
Lab work required.
Natural sciences and engineering practicum.
1 credit.
Spring 2014. Newhall.
CPSC 046. Theory of Computation
(Cross-listed as MATH 046)
This study of various models of computation leads to a characterization of the kinds of problems that can and cannot be solved by a computer. Solvable problems will be classified with respect to their degree of difficulty. Topics to be covered include formal languages and finite state devices; Turing machines; and other models of computation, computability, and complexity.
Prerequisite: CPSC 035 required. Mathematics background at the level of Linear Algebra or higher is required (may be taken concurrently).
Lab work required.
1 credit.
Spring 2014. Danner.
CPSC 052. Principles of Computer Architecture
(See ENGR 025)
Natural sciences and engineering practicum.
1 credit.
Next offered when staffing permits.
CPSC 063. Artificial Intelligence
Artificial intelligence (AI) can be defined as the branch of computer science that is concerned with the automation of intelligent behavior. Intelligent behavior encompasses a wide range of abilities; as a result, AI has become a very broad field that includes game playing, automated reasoning, expert systems, natural language processing, modeling human performance (cognitive science), planning, and robotics. This course will focus on a subset of these topics and specifically on machine learning, which is concerned with the problem of how to create programs that automatically improve with experience. Machine learning approaches studied will include neural networks, decision trees, genetic algorithms, and reinforcement techniques.
Prerequisites: CPSC 035 required.
Lab work required.
Natural sciences and engineering practicum.
1 credit.
Fall 2013. Meeden.
CPSC 065. Natural Language Processing
(Cross-listed as LING 020)
This course is an introduction to the fundamental concepts in natural language processing, the study of human language from a computational perspective. The focus will be on creating statistical algorithms used in the analysis and production of language. Topics to be covered include parsing, morphological analysis, text classification, speech recognition, and machine translation. No prior linguistics experience is necessary.
Prerequisite: CPSC 035 required.
Lab work required.
1 credit.
Fall 2014. Wicentowski.
CPSC 068. Bioinformatics
This course is an introduction to the fields of bioinformatics and computational biology, with a central focus on algorithms and their application to a diverse set of computational problems in molecular biology. Computational themes will include dynamic programming, greedy algorithms, supervised learning and classification, data clustering, trees, graphical models, data management, and structured data representation. Applications will include genetic sequence analysis, pairwise-sequence alignment, phylogenetic trees, motif finding, gene-expression analysis, and protein-structure prediction. No prior biology experience is necessary.
Prerequisite: CPSC 035 required.
Lab work required.
1 credit.
Spring 2015. Soni.
CPSC 071. Software Engineering: iOS Development
This course is an introduction to software engineering, with a focus on iOS development. iOS is the name of the operating system that runs on many of Apple’s products including the iPhone, iPod Touch, and iPad. In this course, students will learn how to write iOS apps in Objective C using Apple’s Xcode IDE (integrated development environment). Topics will also include readings on user interface design, project implementation and unit testing. Students do not need to own an iOS device to take the course.
Prerequisite: CPSC 035 required.
Lab work required.
1 credit.
Spring 2015.
CPSC 072. Computer Vision
(See ENGR 027)
Natural sciences and engineering practicum.
1 credit.
Spring 2015. Zucker.
CPSC 075. Principles of Compiler Design and Construction
(Cross-listed as ENGR 023)
This course introduces the design and construction of language translators for imperative, procedure-oriented programming languages. Topics covered include formal grammars, lexical analysis and finite automata, syntax analysis and pushdown automata, LL and LR parsing, semantic analysis and table handling, error detection and recovery, code generation and optimization, and compiler writing tools.
Prerequisite: CPSC 031 and CPSC 035 required. CPSC 031 may be taken concurrently.
Lab work required.
Natural sciences and engineering practicum.
1 credit.
Fall 2013. Waterman.
CPSC 081. Adaptive Robotics
This seminar addresses the problem of controlling robots that will operate in dynamic, unpredictable environments. In laboratory sessions, students will work in groups to program robots to perform a variety of tasks such as navigation to a goal, obstacle avoidance, and vision-based tracking. In discussion sessions, students will examine the major paradigms of robot control through readings from the primary literature with an emphasis on adaptive approaches.
Eligible for Cognitive Science credit.
Prerequisite: CPSC 035 required. CPSC 063 is recommended.
Lab work required.
Natural sciences and engineering practicum.
1 credit.
Spring 2014. Meeden.
CPSC 082. Mobile Robotics
(See ENGR 028)
Natural sciences and engineering practicum.
1 credit.
Fall 2014. Zucker.
CPSC 087. Parallel and Distributed Computing
This course covers a broad range of topics related to parallel and distributed computing, including parallel and distributed architectures and systems, parallel and distributed programming paradigms, parallel algorithms, and scientific and other applications of parallel and distributed computing. In lecture/discussion sections, students examine both classic results as well as recent research in the field. The lab portion of the course includes programming projects using different programming paradigms, and students will have the opportunity to examine one course topic in depth through an open-ended project of their own choosing. Course topics may include: multi-core, SMP, MPP, client-server, clusters, clouds, grids, peer-to-peer systems, GPU computing, scheduling, scalability, resource discovery and allocation, fault tolerance, security, parallel I/0, sockets, threads, message passing, MPI, RPC, distributed shared memory, data parallel languages, MapReduce, parallel debugging, and parallel and distributed applications
Prerequisites: CPSC 031 and CPSC 035 required. CPSC 045 is recommended.
Lab work required.
1 credit.
Not offered 2013–2014.
CPSC 091. Special Topics in Computer Science
Subject matter for CPSC 091 is generally dependent on group need or individual interest. The course is normally restricted to upper-level students and offered only when interest and staff availability make it practicable to do so.
Lab work required.
1 credit.
Staff.
CPSC 093. Directed Reading and/or Research Project
A qualified student may undertake a program of extra reading and/or a project in an area of computer science with the permission of a staff member who is willing to supervise.
CPSC 097. Senior Conference
This course provides honors and course majors an opportunity to delve more deeply into a particular topic in computer science, synthesizing material from previous courses. Topics have included sensing for healthcare (2012), data management systems (2010, 2011), computer perception (2008, 2009), computational geometry and geographic information systems (2006, 2007), computer security (2005), natural language processing (2004); advanced algorithms (2003); networking (2001, 2002); distributed computing (2000); evolutionary computation (1998 and 1999); complexity, encryption, and compression (1996); and parallel processing (1995). CPSC 097 is the usual method used to satisfy the comprehensive requirement for a computer science major and the senior honors study requirement for a computer science honors major.
Lab work required.
Writing course.
1 credit.
Fall 2013. Ylvisaker.
CPSC 180. Thesis
CPSC 199. Senior Honors Study
Swarthmore College, 500 College Avenue, Swarthmore, PA 19081 Phone: 610-328-8000 Email:
© 2014 Swarthmore Col