From CS111 to CS18

If you are thinking about taking CS18, please click submit on this form (which collects your email address).

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.

These assignments serve two purposes: they prepare you for CS18, and they let the CS18 instructor (Professor Kathi Fisler) make sure you are ready for the increased pace and complexity of CS18. See the Logistics section at the bottom of the page for details on how you get admitted to 18 based on these assignments.

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

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

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

Logistics

Since you have not taken CS17, you will need an override code to take CS18. Kathi will provide you an override code if (a) your work on these assignments suggests that you are indeed ready to take 18, and (b) Doug agrees that you are ready for the jump (based on your work this semester).

We will create new submission areas for each of these assignments in your usual handin infrastructure. You will submit the files listed on each assignment via handin. For the couple of you who are not in 111 in Fall 2019, you can email your files directly to Kathi.

Please submit your files as you finish them, since Kathi needs time to review them (and things will get hectic for her as the semester gets closer).

All work on these assignments is due by January 15th. That will give us time to let you know whether you are clear for CS18 before the semester starts.

We will also set up a campuswire area for the bridge work (though Kathi is off-campus until Dec 19 and will be slow to reply before then). Kathi is running the bridge work, not the current CS111 staff, so route questions to her, please.