Introduction to Programming (CS 1), AP/IB, and CS Place-Out Test Info


Which CS 1 should a student take?

Summary

If you have never programmed before, take CS 1110, 1112, 1113, or 1120. If you have programmed a little, take CS 1111 (or 1110 or 1113 if you can't get into 1111). If you have programmed a fair amount, you can probably get transfer credit or test out of CS 111x. More details follow.

  • CS 1110 - A basic introductory course that focuses on learning the basics of programming and computational thinking. No prerequisite required. Language: Python. Requires a lecture section and one of twelve labs. Final course size will be around 530 students. For more information, see http://cs1110.cs.virginia.edu
  • CS 1111 - Only students with some programming experience may take this course. This programming experience can be in any language. CS 1111 has the same assignments and tests as CS 1110, but does not require lab and moves slightly faster through some material since students are expected to have some exposure to basic concepts. Language: Python.
  • CS 1112 - Only students with no programming experience may take this course. Offered as a lecture + lab combination that meets three times a week. Language: Python. Students must submit a permission of instructor request  through SIS to request a seat in the course.
  • CS 1113 - CS1 special topics and can vary from semester to semester. In the past we have offered a version focused on a mathematical approach to computing and a version emphasizing uses of computing in engineering disciplines.
  • CS 1120 - A course designed as an introductory course for the BACS, it now counts the same for all majors and schools.

Note - You can only receive credit for 1 CS 111X or 1120 course.

Other Credit

Advanced Placement

http://records.ureg.virginia.edu/content.php?catoid=39&navoid=2365#Advanced_Placement_Program

  • For Computer Science - 4 or 5 gives credit for CS 1110
  • For CS Principles - 4 or 5 gives credit for CS 1000T and the student is encouraged to take the CS 1110 Placement Test

International Baccalaureate

http://records.ureg.virginia.edu/content.php?catoid=39&navoid=2365#the_inte_bacca

For Computer Science:

  • 5 on High Level gives credit for CS 1110
  • 6 or 7 on High Level gives credit for CS 1110 and CS 2110

Dual Enrollment

Please discuss with a CS advisor or the SEAS dean's office.

Place Out Tests

CS 1110 Place Out Test

The place out test allows a student to take a course that requires a CS 1 course as a prerequisite, but it does not grant course credit.

Place out tests are only available as follows:

One week prior to the beginning of the semester (fall and spring), through the first seven business days of the semester; then again seven business days prior to course registration for the following semester. Typically, this is around the middle of October in the fall semester, and around the last week of March/first week of April in the spring semester.

Students who wish to take the place out test can fill out this form to receive a link to the exam. The exam must be submitted within 48 hours of receiving the link. The student is allotted 90 minutes to take the exam, beginning when the exam is first opened. Students cannot use books, notes, computers, or help from other people while taking the exam. A student can only take the exam once, and students who have enrolled in CS 1110 are not allowed to take the place out exam beyond Wednesday of second week of the semester. The exam will be graded within a few days, and the results will be emailed to the student. Students who pass do not receive credit, and if CS 1110 was required as part of a degree program may be required to take some other course at UVA in lieu of CS111X; however, it does meet prerequisites. CS majors are required to take another math/technical course that is not already being counted toward their degree program.  Some examples include another APMA course, another CS elective, or a technical course in another SEAS department. 

The place-out test is made up of several multiple-choice, short answer, and coding questions. Students may use any of the following languages on the test: Java, Python, C++, C, Javascript, or C#.  Students interested in taking the test need to be familiar with:

  • variables (creation and manipulation)
  • functions/methods (creation and usage)
  • how to read and interpret code
  • if / else statements
  • various loop constructs (for, while)
  • string manipulation
  • input and output
  • arrays / lists

CS 2100 Place Out Test Information

Place out tests are only available as follows:

One week prior to the start of each semester (fall and spring), through the first seven business days of the semester; then again two weeks prior to course registration for the following semester; typically, this is around the middle of October in the fall semester, and around the last week of March/first week of April in the spring semester.

The place out test for CS 2100 MUST be taken in person, during scheduled times. It is available Monday-Friday at either 9:30am or 1:30pm. The student is allotted 120 minutes to take the test. Students cannot use books, notes, computers, or help from other people while taking the test. A student can only take the test once, and students who have enrolled in CS 2100 are not allowed to take the place out test, beyond the second week of the semester.

The test will be graded within a few days, and the results will be emailed to the student. Students who pass do not receive credit. Because CS 2100 is only a prerequisite to the BACS major, students pursuing the BACS major will NOT have to take some other CS Course in lieu of CS 2100. Students pursuing the BSCS major, or CS minor are REQUIRED to take some other CS course at UVA in lieu of CS 2100. Students should use the Java programming language on the test. The place out test is made up of several short-answer, implementation, and coding questions. Students interested in taking the test need to be familiar with:

Data Structures and Algorithms 1 (CS 2100)

University of Virginia

List of Topics

Learning Java

-Hello World Program

-Primitive Data Types and Sizes of Types

-Using Basic Objects from the Java API

-How to read and use the Java API

-Reading in Input

-Writing basic methods, parameter passing, static keyword, public / private, overloading methods

-Strongly Typed Language / Casting

-Arrays

-Exceptions

-If Statements, Switch Statements, For-Loops, For-Each Loops, While Loops, and other control structures, = vs == vs .equals() vs .compareTo(), etc.

-References to Objects, passing references as parameters, shared references, etc.

-Writing Classes and Enums

-The Java Virtual Machine and how compilation works in Java (high-level…basics). What is a compiler? What does it do? What is a JVM? What does it do? Advantages and Disadvantages.

-Using the Basic Data Structures that come with Java API (Most are covered in the respective section on the data structure itself)

  • Lists, ArrayList, Vector, LinkedList, etc.
  • TreeSet, TreeMap
  • HashSet, HashMap

 

Lists

-What is a list?

-Abstract Data Types versus implementation of those ADTs

-Using an interface in Java to describe an ADT without specific implementation

-Polymorphism and how interfaces allow for type substitution

-Vector

  • Array-Based implementation
  • How resizing method works. Size vs. Capacity
  • Insert / Delete / [] operator / etc.
  • Advantages and Disadvantages

-Java Generics and Wildcards

  • Implementing a Generic Vector
  • **All Data Structure implementations in course are generics
  • Type erasure and instantiating generic arrays in Java

-Linked Lists

  • Insert, Delete, etc.
  • Iterators
  • Advantages / Disadvantages
  • Java Generic Implementation

-Stacks and Queues

  • Array-Based Implementations
  • Linked-List bases Implementations
  • Applications

 

Big-Oh Notation / Analysis

-Formal definition of Big-Oh, Big-Omega, Big-Theta

-Comparing growth rates of functions using this notation

-Complexity Classes

-Common complexity classes (1,n,nlogn, etc.)

-Amortized Time Complexity

  • Return to Vector insert as an illustrative example

 

Trees

-Examples solved with trees / example trees

-Recursion

  • Base cases, making progress towards termination, etc.
  • Recursive implementations of simple methods like printing a list, seeing if a string is a palindrome, towers of Hanoi, etc..

-Using recursion to traverse trees

  • Pre, in, post-order traversals of trees.

-Binary Search Trees

  • Structure Property
  • Insert, Find, Remove, Find-Max, etc.
  • Generic implementation in Java
  • Ordered Set ADT vs. Binary Search Tree

-AVL Trees

  • Rotation methods
  • Maintaining balance.
  • Inheritance in Java:
    • Generic Implementation of AVL Tree using inheritance from Binary Search Tree to simplify implementation.

-Red-Black Trees

  • Overview, but not implementation details
  • Example of structure with same complexity (as AVL) but lower constants / overhead

-Examples of solving problems with Trees

 

Sorting Algorithms

-What is the sorting problem?

-Comparison sorts vs Adjacent Sorts, Java’s Comparable Interface

-Stable, in-place, etc.

-Using Collections.sort() or Comparable to sort in Java

-Adjacent Sorts:

  • Bubble Sort
  • Insertion Sort
  • Lower-Bound Proof on Adjacent Sorts

-Comparison Sorts:

  • MergeSort
  • QuickSort
  • Nlogn lower-bound argument

-Hybrid Sorts / Other Sorts:

  • TimSort (Java uses this), Radix Sort, etc.

 

Hash Tables

-Maps vs. Set ADT

-Hash Tables and HashSet / HashMap

  • Hash functions, HashCode() in java, etc.

-Implementation of Hash Table

  • Array Indexing
  • Hash Functions
  • Collision Resolution Strategies
    • Linear Probing
    • Separate Chaining
    • Quadratic Probing
    • Double Hashing
  • Rehashing
  • Find, Delete, etc.

 

Priority Queues

-Priority Queue ADT

-Binary Heaps

  • Structure Property, Ordering Property
  • Array Based Representation
  • Peek(), push(), Poll()
  • PercolateUp, percolateDown, Heapify, etc.
  • HeapSort

 

Basics of Concurrency

-Terminology (process, thread, deadlock, race conditions, etc.)

-Writing simple threads in Java

  • Runnable, Thread Class, etc.

-Interrupting threads

-Exception Handling in Java

  • In general
  • In the context of thread code

-Shared Resources and Race Conditions

-Basic locks / ideas behind locks

  • Reentrant lock

-Deadlocks

  • Avoiding deadlocks, etc.
  • Java condition objects
  • Await(), signalAll(), etc.

-Blocking Queue

  • Implementing a basic concurrent queue in Java