From CS111 to CS18

If you are thinking about taking CS18, please fill out this short form.

What is CS18 / What Does it Cover?

CS18 has two main goals: (1) to introduce you to object-oriented programming (which structures computations a bit differently than in CS111 and CS17), and (2) to deepen your knowledge of data structures and the key algorithms that work on them. You’ll learn how lists are implemented inside a language (and similarly for trees and hashmaps, the other two data structures we’ll do in CS111 this semester), learn some new data structures (including graphs), and do projects such as writing the core of a search engine and the core of a web browser.

Both CS17 and CS111 use a similar style of programming. CS18 will not assume a particular programming language. Everyone starts afresh with Java.

Bridge Topics and Workload

Here’s the set of topics and workload that we expect will be involved for those hoping to take CS18 in the spring. This doesn’t make up all of the content of CS17, but it makes up the content that we’ll directly depend on for CS18.

The extra work will be made available as a series of extension assignments that you can work on either later this semester or over winter (or Thanksgiving) break.

Sorting Lists

Three algorithms: insertion sort, merge sort, and quicksort. You’ll need to be able to implement these three algorithms, and be able to explain how efficiently each yields a sorted list.

Assignment Handout (updated 2/28 to include a description of mergesort)

Binary Search Trees

Trees are a shape of data structure where instead of having one flat sequence of values (as in a list), the data “branches”, with some structure to which items go into which branch. Binary search trees are a particular usage of tree. You’ll need to understand how the core algorithms work, and how their efficiency compares to doing related operations on lists.

Assignment Handout

Proofs of Algorithm Efficiency in the Worst Case

Different approaches to solving the same problem can have different characteristics in terms of how fast they execute or how much space they consume. In CS111, we will be discussing this concept intuitively, but we will not show you how to develop actual proofs that the time or space needed for an algorithm is limited to a certain bound. CS17 begins to teach students how to write proofs about efficiency, and we build on that skill in CS18.

Assignment Handout (posted 12/28)

Tackling larger programming problems

Part of what one learns in CS17 is just how to tackle problems that are more complex than those we have done in CS111. Many of these problems are best solved with recursion. Rather than give you another project (as originally suggested), we are giving you two such programming problems instead. These should help make sure that your programming instincts are more on par with the CS17 students.

Assignment Handout (posted 12/28)