Carnegie Mellon University Website Home Page
  
Course Information
General Information
Meeting Times
Course Staff
Academic Integrity
Course Work
Course Grades
Lecture Schedule
Calendar
Assignments
Java Resources
Spring 2018

General Information

About the Course

15-121 is a continuation of the process of program design and analysis for students with prior programming experience (functions, loops, and arrays, not necessarily in Java). The course reinforces object-oriented programming techniques in Java and covers data aggregates, data structures (e.g., linked lists, stacks, queues, trees, and graphs), and an introduction to the analysis of algorithms that operate on those data structures.

Learning Objectives

Upon the successful completion of this course, students will be able to:

  • write medium-sized (couple-hundred line) programs in Java to implement a solution to a specified problem by using a Java IDE (such as Eclipse or Dr.Java)
  • further develop and hone a sense of proper idiomatic programming style in Java
  • decompose the solution into appropriate classes and implement those classes with appropriate fields and methods
  • write a class that implements a specified interface
  • choose between and implement a recursive or iterative approach to solving a problem as appropriate
  • understand and implement the following data structures: dynamic array, linked list, binary search tree, heap, hash table
  • be able to implement (or choose the appropriate Java implementation) of the following Abstract Data Types: list (array, ArrayList, LinkedList), stack, queue, priority queue, tree, set (HashSet, TreeSet), map (HashMap, TreeMap) or graph (adjacency list/matrix) to solve a specified problem
  • analyze the Big O running time of an algorithm or method

Topic Outline

This course will cover the following topics:

  • Introduction to the Java programming language
  • Object-Oriented Programming
  • Arrays and ArrayLists
  • Efficiency and O-notation
  • Linked Lists
  • Recursion
  • Java Interfaces and Iterators
  • Stacks and Queues
  • Searching and Sorting
  • Trees (including Binary Search Trees)
  • Priority Queues and Heaps
  • Sets, Maps and Hashing
  • Graphs and Graph Algorithms (if time permits)

For a detailed sequence, see the lecture schedule.

Prerequisite

15-112, Fundamentals of Programming and Computer Science

Textbooks

I do not require any specific textbook. There are numerous online Java resources, including ones on the course Resources page.